Algorithm:树相关算法(BBT/BST/B树/R树)简介(二叉查找树、二叉查找树的插入节点、二叉查找树的删除、二叉树的遍历、平衡二叉树)C 语言实现-阿里云开发者社区

开发者社区> 一个处女座的程序猿> 正文

Algorithm:树相关算法(BBT/BST/B树/R树)简介(二叉查找树、二叉查找树的插入节点、二叉查找树的删除、二叉树的遍历、平衡二叉树)C 语言实现

简介: Algorithm:树相关算法(BBT/BST/B树/R树)简介(二叉查找树、二叉查找树的插入节点、二叉查找树的删除、二叉树的遍历、平衡二叉树)C 语言实现
+关注继续查看

一、二叉树


1、CBT—FBT一定是CBT


参考文章:Algorithm:【Algorithm算法进阶之路】之数据结构基础知识https://yunyaniu.blog.csdn.net/article/details/94663836#2、树Tree结构


2、BST—二叉查找树BST的增删改查


1、BST的查找节点

image.png



查找某节点p的过程如下:


n 将当前节点cur赋值为根节点root;

n 若p的值小于当前节点cur的值,查找cur的左子树;

n 若p的值不小于当前节点cur的值,查找cur的右子树;

n 递归上述过程,直到cur的值等于p的值或者cur为空;

o 当然,若节点是结构体,注意定义“小于”“不小于”“等于”的具体函数。

2、BST的插入节点

image.png



原理要符合二叉树的建立。


n若当前的二叉查找树为空,则插入的元素为根节点,

n若插入的元素值小于根节点值,则将元素插入到左子树中,

n若插入的元素值不小于根节点值,则将元素插入到右子树中,

n递归上述过程,直到找到插入点为叶子节点。

3、BST的删除节点


记待删除的节点为p,分三种情况进行处理


待删除点为叶子节点:p为叶子节点,直接删除该节点,再修改p的父节点的指针

待删除点只有一个孩子:若p为单支节点(即只有左子树或右子树),则将p的子树与p的父亲节点相连,删除p即可。

待删除点只有一个孩子:若p的左子树和右子树均不空,则找到p的直接后继d(p的右孩子的最左子孙),因为d一定没有左子树,所以使用删除单支节点的方法:删除d,并让d的父亲节点dp成为d的右子树的父亲节点;同时,用d的值代替p的值;

(1)、对偶的,可以找到p的直接前驱x(p的左孩子的最右子孙),x一定没有右子树,所以可以删除x,并让x的父亲节点成为x的左子树的父亲节点。

image.png

   


3、BBT—平衡二叉树BBT→AVL/RBT


image.png


       平衡二叉树(Balanced Binary Tree)是二叉查找树的一个变体,也是第一个引入平衡概念的二叉树。1962年,G.M. Adelson-Velsky 和E.M. Landis发明了这棵树,所以它又叫AVL树。

       平衡二叉树要求对于每一个节点来说,它的左右子树的高度之差不能超过1,如果插入或者删除一个节点使得高度之差大于1,就要进行节点之间的旋转,将二叉树重新维持在一个平衡状态。这个方案很好的解决了二叉查找BST树退化成链表的问题,把插入、查找、删除的时间复杂度最好情况和最坏情况都维持在O(logN)。


1、BBT的动机


       对一棵查找树(search tree)进行查询/新增/删除 等动作, 所花的时间与树的高度h 成比例, 并不与树的容量 n 成比例。如果可以让树维持矮矮胖胖的好身材, 也就是让h维持在O(lg n)左右, 完成上述工作就很省时间。能够一直维持好身材, 不因新增删除而长歪的搜寻树, 叫做balanced search tree(平衡树)。


2、BBT的特点:


BBT是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

BBT常用算法有红黑树、AVL、Treap、伸展树、SBT等。

最小BBT的节点的公式: F(n)=F(n-1)+F(n-2)+1,这个类似于一个递归的数列,可以参考Fibonacci数列,1是根节点,F(n-1)是左子树的节点数量,F(n-2)是右子树的节点数量。

0、AVL和RBT红黑树


0、AVL和红黑树对比


两者都属于自平衡二叉树。

两者查找,插入,删除的时间复杂度相同。

1、AVL树—可理解为BBT


         AVL树查找的时间复杂度为O(logN),因为树一定是平衡的。但是由于插入或删除一个节点时需要扫描两趟树,依次向下查找插入点,依次向上平衡树,AVL树不如红黑树效率高,也不如红黑树常用。


AVL树是平衡二叉搜索树的鼻祖:AVL树是最先发明的自平衡二叉查 找树。

AVL树有两个性质

它或者是一颗空二叉树,或者是具有下列性质的二叉树:

(1)、其根的左右子树,高度之差的绝对值不能超过1;

(2)、其根的左右子树,都是二叉平衡树。

AVL应用 1、Windows NT内核中广泛存在。

2、红黑树


image.png



       红黑树的平衡是在插入和删除的过程中取得的。对一个要插入的数据项,插入程序要检查不会破坏树一定的特征。如果破坏了,程序就会进行纠正,根据需要更改树的结构。通过维持树的特征,保持了树的平衡。


红黑树 并不追求“完全平衡 ”:它只要求部分地达到平衡要求,降低了对旋转的要求,从而提高了性能。

红黑树能够以 O(log2 n)  的时间复杂度进行搜索、插入、删除操作。

任何不平衡都会在三次旋转之内解决。

红黑树有两个特征

1、节点都有颜色

2、在插入和删除过程中,要遵循保持这些颜色的不同排列的规则。

红黑规则 1、每一个节点不是红色的就是黑色的。

2、根总是黑色的

3、如果节点是红色的,则它的子节点必须是黑色的(反之不一定成立)。

4、从根到叶节点或空子节点的每条路径,必须包含相同数目的黑色节点。

  (空子节点是指非叶节点可以接子节点的位置。换句话说,就是一个有右子节点的节点可能接左子节点的位置,或是有左子节点的节点可能接右子节点的位置)

红黑树的应用

1、广泛用于C++的STL中,map和set都是用红黑树实现的。

(1)、JDK的TreeMap是一个红黑树的实现,能保证插入的值保证排序。

2、IO多路复用epoll的实现采用红黑树组织管理sockfd,以支持快速的增删改查。

1、BBT的旋转


高度不平衡节点的两颗子树的高度差2,只考虑该不平衡节点本身,分四种情况分别讨论。

(1)、四种分类:左左、左右、右左、右右;

(2)、四种旋转:对称与旋转,左左和右右对称;左右和右左对称

左左和右右两种情况是对称的,这两种情况的旋转算法是一致的,只需要经过一次旋转就可以达到目标,称之为单旋转。

左右和右左两种情况也是对称的,这两种情况的旋转算法也是一致的,需要进行两次旋转,称之为双旋转。


a、高度不平衡之左左

6节点的左子树3节点高度比右子树7节点大2,左子树3节点的左子树1节点高度大于右子树4节点,这种情况成为左左。


b、高度不平衡之左右

6节点的左子树2节点高度比右子树7节点大2,左子树2节点的左子树1节点高度小于右子树4节点,这种情况成为左右。


c、高度不平衡之右左

2节点的左子树1节点高度比右子树5节点小2,右子树5节点的左子树3节点高度大于右子树6节点,这种情况成为右左。


d、高度不平衡4之右右

2节点的左子树1节点高度比右子树4节点小2,右子树4节点的左子树3节点高度小于右子树6节点,这种情况成为右右。


(1)、BBT的左左—单旋转

如图,假设K2不平衡:为使树恢复平衡,把K1变成根节点。K2大于K1,所以,把K2置于K1的右子树上。K1右子树Y大于K1,小于K2,所以,把Y置于k2的左子树上。

左旋:就是让左边的孩子K1去提到上边,升级作为爸爸,自己K2变成儿子。


(2)、BBT的左右双旋转

对于左右和右左这两种情况,单旋转不能使它达到一个平衡状态,要经过两次旋转。

以左右为例:节点K3不满足平衡特性,它的左子树K1比右子树D深2层,且K1子树更深的是右子树K2。


2、BBT的插入


      BBT插入的方法和BST基本一致。区别是,插入完成后需要从插入的节点开始,维护一个到根节点的路径,每经过一个节点都要维持树的平衡。维持树的平衡要根据高度差的特点选择不同的旋转算法。


3、BBT的查找


      BBT查找的方法和BST完全一样。不过根据高度基本平衡存储的特性,BBT能保持O(logN)的稳定时间复杂度,而BST则相当不稳定。


4、BBT的删除


      BBT删除的方法和BST基本一致。区别是,删除完成后,需要从删除节点的父亲开始,向上维护树的平衡一直到根节点。


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
《数据结构和算法分析》具有O(logN)对数特点的三个基本算法
对分查找 给定一个整数X和整数A0,A1,…,AN-1,后者已经预先排序并存在内存中,求使得Ai=X的下标i,如果X不在数据中,则返回i=-1。 int BinarySearch (const ElementType A[], ElementType x, int N)...
633 0
Algorithm:树相关算法(BBT/BST/B树/R树)简介(二叉查找树、二叉查找树的插入节点、二叉查找树的删除、二叉树的遍历、平衡二叉树)C 语言实现
Algorithm:树相关算法(BBT/BST/B树/R树)简介(二叉查找树、二叉查找树的插入节点、二叉查找树的删除、二叉树的遍历、平衡二叉树)C 语言实现
27 0
Algorithm:树相关算法(BBT/BST/B树/R树)简介(二叉查找树、二叉查找树的插入节点、二叉查找树的删除、二叉树的遍历、平衡二叉树)C 语言实现
Algorithm:树相关算法(BBT/BST/B树/R树)简介(二叉查找树、二叉查找树的插入节点、二叉查找树的删除、二叉树的遍历、平衡二叉树)C 语言实现
13 0
Spring Security笔记:使用BCrypt算法加密存储登录密码
在前一节使用数据库进行用户认证(form login using database)里,我们学习了如何把“登录帐号、密码”存储在db中,但是密码都是明文存储的,显然不太讲究。这一节将学习如何使用spring security3新加入的bcrypt算法,将登录加密存储到db中,并正常通过验证。
1539 0
kubeadm高可用master节点部署文档
kubeadm的标准部署里,etcd和master都是单节点的。 但上生产,至少得高可用。 etcd的高可用,用kubeadm微微扩散一下就可以。 但master却官方没有提及。 于是搜索了几篇文档,过几天测试一下。
1704 0
经典算法面试题目-矩阵旋转90度(1.6)
题目 Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place? 一张图像表示成NxN的矩阵,图像中每个像素是4个字节,写一个函数把图像旋转90度。
2209 0
经典算法面试题目-置矩阵行列元素为0(1.7)
题目 Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0. 写一个函数处理一个MxN的矩阵,如果矩阵中某个元素为0,那么把它所在的行和列都置为0. 解答 简单题。
840 0
+关注
一个处女座的程序猿
国内互联网圈知名博主、人工智能领域优秀创作者,全球最大中文IT社区博客专家、CSDN开发者联盟生态成员、中国开源社区专家、华为云社区专家、51CTO社区专家、Python社区专家等,曾受邀采访和评审十多次。仅在国内的CSDN平台,博客文章浏览量超过2500万,拥有超过57万的粉丝。
1701
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载