<返回更多

一文搞懂二叉搜索树、B树、B+树、AVL树、红黑树

2023-08-29    做好一个程序猿
加入收藏

我们假设B+树一个节点可以有100个关键字,那么3层的B树可以容纳大概1000000多个关键字(100+101100+101101*100)。而红黑树要存储这么多至少要20层。所以使用B树相对于红黑树和AVL可以减少IO操作

大纲

在了解 B树、B+树、AVL树、红黑树 之前,我们先看一下各种树型结构的大致实际应用场景:

B和B+树:主要用在文件系统以及数据库中做索引等AVL树:平衡二叉树之一,应用相对其他数据结构比较少,windows对进程地址空间的管理用到了AVL红黑树:平衡二叉树,广泛应用在C++STL中,比如map和set,JAVA的TreeMap

树结构已经有了很多种形式,为何出现 B树、B+树、AVL树、红黑树?下面我们按照这个大纲来看一下这些问题?

二叉搜索树

概念

二叉搜索树 (平衡二叉树) 是采用二分法思维把数据按规则组装成一个树形结构的数据,用这个树形结构的数据减少无关数据的检索,大大的提升了数据检索的速度。

我们在二叉搜索树的深度遍历过程中,使用中序遍历,就能获取得到有序的序列。

特点

存在的局限

对于一个节点分布相对均衡 的二叉查找树来说,如果节点总数是n,那 么搜索节点的时间复杂度就是O(logn) ,和树的深度是一样的。 这种依靠比较大小来逐步查找的方式,和二分查找算法非常相似。

出现一些特殊的情况的时候,会导致搜索节点的时间复杂度变高。什么特殊情况呢?下面请试着在二叉查找树中依次插入10、11、9、8、7、6、5、4,看看会出现什么 ? 好好的一个二叉树,变成“跛脚”啦!

不只是外观看起来变得怪异了,查询节点的时间复杂度也退化成了O(n)。 怎么解决这个问题呢?这就涉及二叉树的自平衡 了。二叉树自平衡的方式有多种,如红黑树、AVL树等,这两种我们在后面会介绍到,我们先来看一下B树和B+树。

B树

概念

B树又名平衡多路查找树(也把B树称为B-树)查找路径不只两个,不同于常见的二叉树,它是一种多叉树,我们常见的使用场景一般是在数据库索引技术里,大量使用者B树和B+树的数据结构。

B树大多用在磁盘上用于查找磁盘的地址。因为磁盘会有大量的数据,有可能没有办法一次将需要的所有数据加入到内存中,所以只能逐一加载磁盘页,每个磁盘页就对应一个节点,而对于B树来说,B树很好的将树的高度降低了,这样就会减少IO查询次数,虽然一次加载到内存的数据变多了,但速度绝对快于AVL或是红黑树的。

特点:

查询分析

B+树

概念

特点

B+Tree与B-Tree 的区别

1)B树的关键字和记录是放在一起的,叶子节点可以看作外部节点,不包含任何信息;B+树的非叶子节点中只有关键字和指向下一个节点的索引,记录只放在叶子节点中。

2)在B树中,越靠近根节点的记录查找时间越快,只要找到关键字即可确定记录的存在;而B+树中每个记录的查找时间基本是一样的,都需要从根节点走到叶子节点,而且在叶子节点中还要再比较关键字。

思考:为什么说B+tree比B-tree更适合实际应用中操作系统的文件索引和数据库索引?

1) B+树的磁盘读写代价更低

  B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。

2) B+树的查询效率更加稳定

  由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。

3)范围查找更快

MySQL是关系型数据库,经常会按照区间来访问某个索引列,B+树的叶子节点间按顺序建立了链指针,加强了区间访问性,所以B+树对索引列上的区间范围查询很友好。而B树的数据有一部分存在在非叶子节点上面,而且默认的B树的相邻的叶子节点之间是没有指针的,所以范围查找相对更慢。

 

AVL树(平衡二叉树)

概念

AVL、红黑树是对二叉搜索树的改进版本。

平衡因子:某个节点的左右子树深度之差。在一棵平衡二叉树中,节点的平衡因子只能取 0 、1 或者 -1 ,分别对应着左右子树等高,左子树比较高,右子树比较高。

AVL树是带有平衡条件的二叉查找树,一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡,左右子树树高不超过1,和红黑树相比,它是严格的平衡二叉树,平衡条件必须满足(所有节点的左右子树高度差不超过1)。

不管我们是执行插入还是删除操作,只要不满足上面的条件,就要通过旋转来保持平衡,而旋转是非常耗时的,由此我们可以知道AVL树适合用于插入删除次数比较少,但查找多的情况。

如上图所示:任意节点的左右子树的平衡因子差值都不会大于1

AVL保持平衡的四种操作

增删改查操作和二分搜索树类似,但是要多考虑的就是对节点的平衡考虑,如果一串数字的插入顺序为3,4,5。那么这棵树结构就会退化为一个链表。而这时候AVL就会对这个树进行旋转操作来达到平衡,所以,我们就知道旋转的操作会在增加,删除,修改这三个地方进行旋转。旋转操作分为下面四种情况

1 LL右单旋转

如图,8的左子树已经退化为链表,并且5,8这两个节点不再平衡,这时我们先找到深度最深的不平衡节点5,对节点5进行LL旋转操作,在如图的这种情况下,得到右图的结构

2 RR左单旋转

如图,当插入顺序为当插入顺序为8,3,10,13,15的时候,树的结构变成左边的样子,这时10节点和8节点已经不平衡,为了保持AVL的平衡,我们要对10节点进行RR旋转,如右图所示

3 LR先左后右

如图。5,8节点已经不平衡,这时要对5节点做平衡处理,首先将5进行RR左旋转,7的左节点也变为5的右节点。

这时7,8还是不平衡的,对8进行右旋转,8的右节点也变为8的左节点,如图。

4 RL先右后左

如左图,8,13节点不平衡,对13节点进行LL右旋转,得到右图

这时8,10是不平衡的,对8节点进行RR左旋转,得到右图。

红黑树

概念

一种二叉查找树,但在每个节点增加一个存储位表示节点的颜色,可以是red或black(非红即黑)。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制,红黑树确保没有一条路径会比其它路径长出两倍。它是一种弱平衡二叉树,相对于要求严格的AVL树来说,它的旋转次数少,所以对于插入、删除操作较多的情况下,我们就用红黑树。

特点

红黑树的自平衡操作

红黑树插入

两个操作:旋转+变色

在红黑树的结点上添加20,刚开始作为50的左子结点,这样不符合红黑树的规则,并且这样的情况满足上面说的情况5,因此50结点会变成黑色,根结点右旋。先完成右旋,再完成变色。

旋转旋转

变色变色

继续添加结点200,首先会作为100的右结点添加,因此父结点和叔叔结点都变成黑色,祖父结点50变成红色,然后根节点不能为红色,因此继续变色,最后根节点变成黑色。需要注意的是红色节点的子结点必须为黑色节点,但是没有规定黑色节点的子结点必须为红色,说明黑色节点下面子结点什么颜色都可以。

变色变色

 

继续变色继续变色

继续添加结点300,首先会作为子结点添加到200的右子结点,因此首先以插入结点的祖父结点100为支点发生左旋,然后变色,父结点200变成黑色,原祖父结点变成红色。

左旋左旋

变色变色

继续添加结点150,首先会作为子结点添加到100的右子结点,因此父结点和叔叔结点变成黑色,祖父结点200变成红色,变完色后发现符合黑红树规则,无需再旋转或变色。

变色变色

继续添加元素160,会先作为右结点挂在150下面,然后这种情况符合上面第五种,因此先按照祖父结点100为支点左旋,然后父结点变成黑色,原祖父结点变成红色,完后发现符合黑红树规则,无需再选择或变色。

左旋左旋

变色变色

添加320到子结点,会首先挂在350下面,父结点是红色,叔叔结点(null)为黑色,由于当前结点在父结点的左边,因此先以父结点350为支点右旋,右旋后变成上面的第五种情况,因此先以祖父结点300左旋,然后父结点320变色为黑色,原祖父结点300变色为红色。

右旋右旋

左旋变色左旋变色

最后添加180到结点中,首先添加到160的右子结点,父结点和叔叔结点都变色为黑色,祖父结点150变成红色。

变色变色

右旋变成红色后,这种为第四种情况,即150结点的父结点是红色,叔叔结点是黑色,因此本例中需要右旋,由于右旋后200和160会碰撞,因此160结点的子树将作为200结点的左子树。

左旋需要以200结点的祖父结点50为支点左旋,由于左旋后,50和100会发生碰撞,因此100将挂在50结点的右边。并且父结点150变成黑色,祖父结点50会变成红色。

变色变色

红黑树插入自平衡总结

红黑树的删除

红黑树的删除情况相对插入会复杂一些,这这里先不过多的介绍了,肝不动了。如果感兴趣的话,我们在来一起探讨~~

二叉搜索树、B树、B+树、AVL树、红黑树的常见面试题

1 为什么设计红黑树

红黑树通过它规则的设定,确保了插入和删除的最坏的时间复杂度是O(log N) 。

红黑树解决了AVL平衡二叉树的维护起来比较麻烦的问题,红黑树,读取略逊于AVL,维护强于AVL,每次插入和删除的平均旋转次数应该是远小于平衡树。

因此:相对于要求严格的AVL树来说,红黑树的旋转次数少,所以对于插入、删除操作较多的情况下,我们就用红黑树。但是,只是对查找要求较高,那么AVL还是较优于红黑树.

2 B树、B+树和红黑树的区别

3 AVL树和红黑树的区别

红黑树的算法时间复杂度和AVL相同,但统计性能比AVL树更高。

红黑树和AVL树都能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。 2、由于设计,红黑树的任何不平衡都会在三次旋转之内解决。AVL树增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

在查找方面: 红黑树的性质(最长路径长度不超过最短路径长度的2倍),其查找代价基本维持在O(logN)左右,但在最差情况下(最长路径是最短路径的2倍少1),比AVL要略逊色一点。 AVL是严格平衡的二叉查找树(平衡因子不超过1)。查找过程中不会出现最差情况的单支树。因此查找效率最好,最坏情况都是O(logN)数量级的。

所以,综上: AVL比RBtree更加平衡,但是AVL的插入和删除会带来大量的旋转。 所以如果插入和删除比较多的情况,应该使用RBtree, 如果查询操作比较多,应该使用AVL。

4 数据库为什么使用B树,而不使用AVL或者红黑树

我们假设B+树一个节点可以有100个关键字,那么3层的B树可以容纳大概1000000多个关键字(100+101100+101101*100)。而红黑树要存储这么多至少要20层。所以使用B树相对于红黑树和AVL可以减少IO操作

5 为什么B+树比B树更为友好

关键词:搜索树      点击(8)
声明:本站部分内容来自互联网,如有版权侵犯或其他问题请与我们联系,我们将立即删除或处理。
▍相关推荐
更多搜索树相关>>>