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

大纲

在了解 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+树的值只分部在叶子节点上）
• 任何关键字出现且只出现在一个节点中（区别与B+树）
• 搜索有可能在非叶子节点结束（区别与B+树，因为值都在叶子节点上，只有搜到叶子节点才能拿到值）
• 在关键字全集内做一次查找，性能逼近二分查找算法

查询分析

• 如果要查找数据项29，那么首先会把磁盘块1由磁盘加载到内存，此时发生一次IO，在内存中用二分查找确定29在17和35之间，锁定磁盘块1的P2指针，内存时间因为非常短（相比磁盘的IO）可以忽略不计，
• 通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存，发生第二次IO，29在26和30之间，锁定磁盘块3的P2指针，
• 通过指针加载磁盘块8到内存，发生第三次IO，同时内存中做二分查找找到29，结束查询，总计三次IO。

B+树

概念

特点

• 所有叶子节点连接成为一个单链表，且这个链表是有序的。
• 所有关键字都在叶子节点出现，因此不可能在非叶子节点命中。
• 内节点不存数据，只存key。
• 非叶子节点相当于是叶子节点的索引，叶子节点相当于是存储数据的数据层。

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树来说，它的旋转次数少，所以对于插入、删除操作较多的情况下，我们就用红黑树。

特点

• 每个节点非红即黑；
• 根节点是黑的；
• 每个叶节点(叶节点即树尾端NULL指针或NULL节点)都是黑的；
• 如果一个节点是红的,那么它的两儿子都是黑的；
• 对于任意节点而言，其到叶子点树NULL指针的每条路径都包含相同数目的黑节点；
• 高度始终保持在h = logn
• 一般插入的是红色结点

红黑树的自平衡操作

红黑树插入

两个操作：旋转+变色

在红黑树的结点上添加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会变成红色。

变色

红黑树插入自平衡总结

• N为根：涂黑完事；
• 父黑：啥事不用管；
• 父红叔红：父/叔涂黑，祖父涂红，然后把祖父当成新的平衡节点递归处理（我们下面平衡了，让他老人家和上面沟通吧）；
• 父红叔黑：父节点和新插入节点同一边的话，扭一下就完事了（同左右旋，同右左旋，顺便涂色）；不在同一边的话，先扭到同一边吧。

红黑树的删除

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

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

1 为什么设计红黑树

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

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

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

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

• 最大的区别就是树的深度较高，在磁盘I/O方面的表现不如B树。
• 在大规模数据存储的时候，红黑树往往出现由于树的深度过大而造成磁盘IO读写过于频繁，进而导致效率低下。在这方面，B树表现相对优异，B树可以有多个子女，从几十到上千，可以降低树的高度。
• 红黑树多用在内部排序，即全放在内存中的，STL的map和set的内部实现就是红黑树。
• 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树更为友好

• 磁盘读写代价更低 树的非叶子结点里面没有数据，这样索引比较小，可以放在一个blcok（或者尽可能少的blcok）里面。避免了树形结构不断的向下查找，然后磁盘不停的寻道，读数据。这样的设计，可以降低io的次数。
• 查询效率更加稳定 非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
• 遍历所有的数据更方便 B+树只要遍历叶子节点就可以实现整棵树的遍历，而其他的树形结构 要中序遍历才可以访问所有的数据。