二叉搜索树、B树、B 树、AVL树、红黑树

数据结构动态添加演示图

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

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

树结构已经有了很多种形式，为何出现 B树、B+树、AVL树、红黑树，首先要了解一下二叉搜索树

特殊树的定义

• 二叉树：一种特殊的树，二叉树的每个节点最多只能有2个子节点
• 二叉搜索树：一种特殊的二叉树，要求它的每个节点都不比它左子树的任意元素小，而且不比它的右子树的任意元素大
• 平衡二叉树：一种特殊的二叉树，任意节点的子树的高度差都小于等于1
• 完全二叉树：一种特殊的二叉树，叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部
• 满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树，是完全二叉树特殊情况
• 红黑树：一种二叉查找树，但在每个节点上增加一个存储位表示节点的颜色，可以是red或black。通过对任何一条从根到叶子的路径上的各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的
• B树(B-树不读减号)：平衡多路查找树(查找路径不只两个)，不同于常见的二叉树，它是一种多叉树 (粗略描述)
• B+树：B树的一种升级版本，数据都保存在叶子节点 ，其他节点存储索引 (粗略描述)

1. 二叉搜索树

1 概念

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

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

2) 特点

• 任意节点左子树不为空,则左子树的值均小于根节点的值.
• 任意节点右子树不为空,则右子树的值均大于于根节点的值.
• 任意节点的左右子树也分别是二叉查找树.
• 没有键值相等的节点. (教科书上的)

3) 二叉搜索树存在的局限

二叉树在查找数据时，时间复杂度最好情况是O(logn) ，最坏情况下时间复杂度O(n)，如a图所示，二叉树退化成一个链表了，恰好选择了最小或者最大的节点做root，节点排在了一条直线上。

因此,在二叉查找树的基础上,又出现了AVL树,红黑树,它们两个都是基于二叉查找树,只是在二叉查找树的基础上又对其做了限制.

2. AVL树(平衡二叉树)

1) 概念

AVL、红黑树是对二叉搜索树的改进版本。
定义：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

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

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

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

由上图所知：任意节点的左右子树的平衡因子差值都不会大于1

2) 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左旋转，得到右图。

以上就是保持平衡的方式。

3) AVL存在的局限性

由于维护这种高度平衡所付出的代价比从中获得的效率收益还大,故而实际的应用不多，

更多的地方是用追求局部而不是非常严格整体平衡的红黑树.当然,如果应用场景中对插入删除不频繁,只是对查找要求较高,那么AVL还是较优于红黑树.

3. 红黑树

1) 概念

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

2) 特征

1、每个节点非红即黑；
2、根节点是黑的；
3、每个叶节点(叶节点即树尾端NULL指针或NULL节点)都是黑的；
4、如果一个节点是红的,那么它的两儿子都是黑的；
5、对于任意节点而言，其到叶子点树NULL指针的每条路径都包含相同数目的黑节点；
6、高度始终保持在h = logn
7、红黑树的查找、插入、删除的时间复杂度最坏为O(log n)

3) 红黑树的自平衡操作

但插入、或者删除红黑树的数值时，为了重新符合红黑树的规则，需要对红黑树进行旋转、变色操作。

当在对红黑树进行插入和删除等操作时，对树做了修改可能会破坏红黑树的性质。为了继续保持红黑树的性质，可以通过对结点进行重新着色，以及对树进行相关的旋转操作，即通过修改树中某些结点的颜色及指针结构，来达到对红黑树进行插入或删除结点等操作后继续保持它的性质或平衡的目的。

树的旋转分为左旋和右旋，下面借助图来介绍一下左旋和右旋这两种操作。

• 左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。

使用动图更好理解：【由动图可知，红黑树并不是简单的旋转，需要伴随着子树的转换】

• 右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。

使用动图更好理解：

我们先忽略颜色，可以看到旋转操作不会影响旋转结点的父结点，父结点以上的结构还是保持不变的。左旋只影响旋转结点和其右子树的结构，把右子树的结点往左子树挪了。右旋只影响旋转结点和其左子树的结构，把左子树的结点往右子树挪了。

所以旋转操作是局部的。另外可以看出旋转能保持红黑树平衡的一些端详了：当一边子树的结点少了，那么向另外一边子树“借”一些结点；当一边子树的结点多了，那么向另外一边子树“租”一些结点。

• 变色：结点的颜色由红变黑或由黑变红。

Java TreeMap实现了SortedMap接口，也就是说会按照key的大小顺序对Map中的元素进行排序，key大小的评判可以通过其本身的自然顺序(natural ordering)，也可以通过构造时传入的比较器(Comparator)。*_TreeMap底层通过红黑树(Red-Black tree)实现_

看一下红黑树插入一个数值，红黑树自平衡的一个过程：

4. B树(B-树)

B树与B+树的解释

1) 概念

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

有些教材中，也把B树称为B-树, -只是一个符号，无需太在意命名形式。

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

2) 特点

1)定义任意非叶子结点最多只有M个儿子；且M>22)所有节点关键字是按递增次序排列，并遵循左小右大原则3)位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间 4)其它节点至少有M/2个子节点 [M/2,M-1] 5)所有叶子节点都在同一层

3) B树查询流程

这里使用字母来表示：

如上图我要从上图中找到E字母，查找流程如下：

(1)获取根节点的关键字进行比较，当前根节点关键字为M，E (2)拿到关键字D和G，D (3)拿到E和F，因为E=E 所以直接返回关键字和指针信息(如果树结构里面没有包含所要查找的节点则返回null)；

搜索B树时，很明显，访问节点(即读取磁盘)的次数与树的高度呈正比，而B树与红黑树和普通的二叉查找树相比，虽然高度都是对数数量级，但是显然B树中log函数的底可以比2更大，因此，和二叉树相比，极大地减少了磁盘读取的次数。

5.B+树

1) 概念

B+树时B树的一种升级版本，B+树查找的效率要比B树更高、更稳定。

B+树是应文件系统所需而产生的一种B树的变形树(文件的目录一级一级索引,只有最底层的叶子节点(文件)保存数据.),非叶子节点只保存索引,不保存实际的数据,数据都保存在叶子节点中.

这不就是文件系统文件的查找吗?我们就举个文件查找的例子:有3个文件夹,a,b,c, a包含b,b包含c,一个文件yang.c, a,b,c就是索引(存储在非叶子节点), a,b,c只是要找到的yang.c的key,而实际的数据yang.c存储在叶子节点上.所有的非叶子节点都可以看成索引部分

2) 特点

B+树和B树类似，但多了几条规则

• 非叶子结点的子树指针个数与关键字(节点中的元素个数)个数相同
• 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树(B-树是开区间)
• 所有叶子结点有一个链指针
• 所有关键字都在叶子结点出现
• 只有叶子节点有Data域

3) B+树与B树对比

1、B+树的层级更少：相较于B树，B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；

2、B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;

3、B+树天然具备排序功能：_B+树所有的_叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。

4、B+树全节点遍历更快：_B+树遍历整棵树只需要遍历所有的_叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。

B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。

B+树相对于B树的最主要的优点：

1. B+树只有叶子节点存放数据，而其他节点只存放索引，而B树每个节点都有Data域。所以相同大小的节点B+树包含的索引比B树的索引更多(因为B树每个节点还有Data域)
2. B+树的叶子节点是通过链表连接的，所以找到下限后能很快进行区间查询，比B树中序遍历快

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

1) 为什么设计红黑树

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

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

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

2) B树的作用

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

3) B树和 B+树的区别

B/B+树用在磁盘文件组织、数据索引和数据库索引中。其中B+树比B 树更适合实际应用中操作系统的文件索引和数据库索引，因为：
1、B+树的磁盘读写代价更低B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。

举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+ 树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。

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

3、B树在元素遍历的时候效率较低
由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引。在数据库中基于范围的查询相对频繁，所以此时B+树优于B树。

4) B树和红黑树的区别

最大的区别就是树的深度较高，在磁盘I/O方面的表现不如B树。

要获取磁盘上数据，必须先通过磁盘移动臂移动到数据所在的柱面，然后找到指定盘面，接着旋转盘面找到数据所在的磁道，最后对数据进行读写。磁盘IO代价主要花费在查找所需的柱面上，树的深度过大会造成磁盘IO频繁读写。根据磁盘查找存取的次数往往由树的高度所决定。

所以，在大规模数据存储的时候，红黑树往往出现由于树的深度过大而造成磁盘IO读写过于频繁，进而导致效率低下。在这方面，B树表现相对优异，B树可以有多个子女，从几十到上千，可以降低树的高度。

5) AVL树和红黑树的区别

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

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

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

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

AVL是一种高度平衡的二叉树，维护这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树。当然，如果场景中对插入删除不频繁，只是对查找特别有要求，AVL还是优于红黑的。

6) 数据库为什么使用B树，而不使用AVL或者红黑树

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

7) mysql的Innodb引擎为什么采用的是B+树的索引方式

B+树只有叶子节点存放数据，而其他节点只存放索引，而B树每个节点都有Data域。所以相同大小的节点B+树包含的索引比B树的索引更多(因为B树每个节点还有Data域)

还有就是B+树的叶子节点是通过链表连接的，所以找到下限后能很快进行区间查询，比B树中序遍历快

8) 红黑树 和 b+树的用途有什么区别？

1. 红黑树多用在内部排序，即全放在内存中的，STL的map和set的内部实现就是红黑树。
2. B+树多用于外存上时，B+也被成为一个磁盘友好的数据结构。

9) 为什么B+树比B树更为友好

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

参考：
https://www.cnblogs.com/carpenterlee/p/5503882.html
https://www.jianshu.com/p/86a1fd2d7406
https://juejin.im/post/6844903859974848520#heading-16
https://blog.csdn.net/whoamiyang/article/details/51926985
https://marian5211.github.io/2018/03/09/B树、B-树、AVL树、Trie树及其应用场景/