二叉树、红黑树、B树、B+树

╰半橙微兮° 2022-03-07 05:54 224阅读 0赞

# **一、二叉查找树**  #

二叉搜索树（BST）又称二叉查找树或二叉排序树。一棵二叉搜索树是以二叉树来组织的，可以使用一个链表数据结构来表示，其中每一个结点就是一个对象。一般地，除了key和卫星数据（文末附注1）之外，每个结点还包含属性lchild、rchild和parent，分别指向结点的左孩子、右孩子和双亲（父结点）。如果某个孩子结点或父结点不存在，则相应属性的值为空（NIL）。根结点是树中唯一父指针为NIL的结点，而叶子结点的孩子结点指针也为NIL。

在二叉搜索树中：

*  **① 若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值；**
 *  **② 若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值；**
 *  **③ 任意结点的左、右子树也分别为二叉搜索树。**

![20190316114416513.JPG][]

在二叉查找树中，对于任意单个操作我们不保证O（logN）的时间复杂度，但是可以证明任意连续M次操作在最坏的情形下花费的时间为O（MlogN）。

# 二、平衡二叉查找树 #

平衡二叉搜索树：它是一棵空树或它的左右两个子树的**高度差的绝对值不超过1**，并且左右两个子树都是一棵平衡二叉树。常用算法有红黑树、AVL、Treap、伸展树等。在平衡二叉搜索树中，我们可以看到，其高度一般都良好地维持在O（log2n），大大降低了操作的时间复杂度。

调整平衡的基本思想：  
       当在二叉排序树中插入一个节点时，首先检查是否因插入而破坏了平衡，若破坏，则找出其中的最小不平衡二叉树，在保持二叉排序树特性的情况下，调整最小不平衡子树中节点之间的关系，以达到新的平衡。所谓最小不平衡子树，指离插入节点最近且以平衡因子的绝对值大于1的节点作为根的子树。

先插入指定节点，记录下当前节点的信息，LH，EH或者RH。  
    **1. 若左子树高LH，查看其左子树根节点的信息，若是LH，则一次右旋；若是RH，则一次左旋+一次右旋  
    2. 若右子树高RH，查看右子树根节点的信息，若是RH，则一次左旋；若是LH，则一次右旋+一次左旋  
    3. 调整改变的节点信息**

追求绝对的高度平衡，随着树的高度的增加，动态插入和删除的代价也随之增加

# 三、红黑树 #

红黑树（Red Black Tree） 是一种自平衡二叉查找树。

红黑树和平衡二叉树区别如下：

*  1、红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。
 *  2、平衡二叉树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知。

二叉平衡树的严格平衡策略以牺牲建立查找结构(插入，删除操作)的代价，换来了稳定的O(logN) 的查找时间复杂度，它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n是树中元素的数目。

(1) 每个节点或者是黑色，或者是红色。
    (2) 根节点是黑色。
    (3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点]
    (4) 如果一个节点是红色的，则它的子节点必须是黑色的。
    (5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

RBT 的操作代价分析：  
        (1) 查找代价：由于红黑树的性质(最长路径长度不超过最短路径长度的2倍)，可以说明红黑树虽然不像AVL一样是严格平衡的，但平衡性能还是要比BST要好。其查找代价基本维持在O(logN)左右，但在最差情况下(最长路径是最短路径的2倍少1)，比AVL要略逊色一点。  
        (2) 插入代价：RBT插入结点时，需要旋转操作和变色操作。但由于只需要保证RBT基本平衡就可以了。因此插入结点最多只需要2次旋转，这一点和AVL的插入操作一样。虽然变色操作需要O(logN)，但是变色操作十分简单，代价很小。  
        (3) 删除代价：RBT的删除操作代价要比AVL要好的多，删除一个结点最多只需要3次旋转操作。  
RBT 效率总结 : 查找 效率最好情况下时间复杂度为O(logN)，但在最坏情况下比AVL要差一些，但也远远好于BST。  
        插入和删除操作改变树的平衡性的概率要远远小于AVL（RBT不是高度平衡的）。因此需要的旋转操作的可能性要小，而且一旦需要旋转，插入一个结点最多只需要旋转2次，删除最多只需要旋转3次(小于AVL的删除操作所需要的旋转次数)。虽然变色操作的时间复杂度在O(logN)，但是实际上，这种操作由于简单所需要的代价很小。

红黑树能够以O(log2(N))的时间复杂度进行搜索、插入、删除操作。此外,任何不平衡都会在3次旋转之内解决。这一点是AVL所不具备的。

插入操作：  
          1.插入根节点（不需要操作）  
          2.父节点为黑色(不需要操作)  
          3.父节点和兄弟节点为红色，祖父节点为黑色，只需要变色，将祖父节点递归检查（原本检查自己）  
          4.父节点为红色，兄弟节点为黑色，祖父节点为红色，先两次旋转再调整颜色（左旋+右旋）

删除操作：  
         1.删除只有一个新的根节点（直接删除）  
         2.父节点为黑色，兄弟节点为红色（先旋转成左左，再删除）  
         3.父节点为黑色，兄弟节点为黑色（先将兄弟节点换成红色，变成情况2）  
         4.父节点为红色，自己和兄弟节点为黑色（将父节点变成黑色，兄弟节点变成红色，变成情况2）  
         5.兄弟节点为黑色，兄弟节点左子树根节点为红色（交换颜色，旋转成为左左）  
        6.情况2和情况5，调整性质5（将N删掉，用子节点顶替，若子节点为红色，则重绘为黑色）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70][]

[参考链接][Link 1]

# 四、 B树     #

二叉查找树的查找的时间复杂度是Ｏ(log N)，其查找效率已经足够高了，那为什么还有Ｂ树和Ｂ＋树的出现呢？难道它两的时间复杂度比二叉查找树还小吗？  
       答案当然不是，Ｂ树和Ｂ＋树的出现是因为另外一个问题，那就是磁盘ＩＯ；众所周知，ＩＯ操作的效率很低，那么，当在大量数据存储中，查询时我们不能一下子将所有数据加载到内存中，只能逐一加载磁盘页，每个磁盘页对应树的节点。造成大量磁盘ＩＯ操作（最坏情况下为树的高度）。平衡二叉树由于树深度过大而造成磁盘IO读写过于频繁，进而导致效率低下。  
所以，我们为了减少磁盘ＩＯ的次数，就你必须降低树的深度，将“瘦高”的树变得“矮胖”。一个基本的想法就是：

*  （1）、每个节点存储多个元素
 *  （2）、摒弃二叉树结构，采用多叉树

这样就引出来了一个新的查找树结构 ——多路查找树。 根据AVL给我们的启发，一颗平衡多路查找树(B~树)自然可以使得数据的查找效率保证在O(logN)这样的对数级别上。

示例：三阶B树（实际中节点中元素很多）

![这里写图片描述][70]

**查询**

以上图为例：若查询的数值为５：

*  第一次磁盘ＩＯ：在内存中定位（与17、35比较），比17小，左子树；
 *  第二次磁盘ＩＯ：在内存中定位（与８、12比较），比８小，左子树；
 *  第三次磁盘ＩＯ：在内存中定位（与3、5比较），找到5，终止。

整个过程中，我们可以看出：比较的次数并不比二叉查找树少，尤其适当某一节点中的数据很多时，但是磁盘IO的次数却是大大减少。比较是在内存中进行的，相比于磁盘IO的速度，比较的耗时几乎可以忽略。所以当树的高度足够低的话，就可以极大的提高效率。相比之下，节点中的元素多点也没关系，仅仅是多了几次内存交互而已，只要不超过磁盘页的大小即可。

**对于m阶B树，其具有如下性质：**

*  根结点至少有两个子女；
 *  每个结点的值的个数为 1 <= n < m；
 *  所有的叶子结点都位于同一层；
 *  除根结点以外的所有结点（不包括叶子结点）的孩子正好是值个数的加1；
 *  每个结点中的值都按照从小到大的顺序排列，每个值的左子树中的所有的值都小于它，而右子树中的所有的值都大于它。

***B树的插入***

如果插入的结点只有一个数值，直接在该结点插入即可。例如，在上图中插入9，则直接在10结点前面插入9即可。但如果插入44，此时便需要通过结点的向上分裂来完成插入。

插入44：

![20190316112209216.png][]

发现此结点有3个值，不满足3阶B树，因此要进行分裂，将中间的40向上结点移动：

![20190316112217244.png][]

分裂后此B树变成了4阶B树，不满足3阶B树条件，原因是40移动到上结点所致，因此继续向上结点移动，将50移动到上节点：

![20190316112230198.png][]

此时发现又出现3个值的结点，继续进行分裂：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 1][]

此时便满足条件，完成。

B树的删除按照插入的方法反过来操作即可，即父结点(如果不符合父结点大于左结点小于右结点的条件，则与上层父节点位置调换，直到符合条件为止)不断下移合并，知道符合条件为止。

# 五、B+树 #

B+树是B树的一种变体，有着比B树更高的查询性能，B+树和B树除了有一些共同特点外，还有一些新的特点：

*  有k个子树的中间结点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
 *  所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
 *  所有的中间结点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

下面我们使用数值来表示一棵B+树：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 2][]

由上图可以看到，B+树的每个结点的最大或最小元素都出现在下一个结点的首或尾。在B+树中，只有叶子节点存储数据，其它中间结点全部是索引。在数据库的聚集索引中，叶子节点直接包含数据库中某一行数据。在非聚集索引中，叶子节点带有指向数据库行的指针。

### ***B+树的查找*** ###

B+树的查找有两种方式：从最小值进行顺序查找；从根结点开始，进行随机查找。在查找时，若非终端结点上的关键值等于给定值，并不终止，而是继续向下直到叶子结点（因为叶子结点才存数据）。因此，在B+树中，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。其余同B-树的查找类似。

**与B树的不同：**

*  Ｂ＋树中间节点没有数据（索引元素所指向的数据记录），只有索引，而Ｂ树每个结点中的每个关键字都有数据；这就意味着同样的大小的磁盘页可以容纳更多节点元素，在相同的数据量下，Ｂ＋树更加“矮胖”，ＩＯ操作更少。
 *  其次，因为数据的不同，导致查询过程也不同；Ｂ树的查找只需找到匹配元素即可，最好情况下查找到根节点，最坏情况下查找到叶子结点，所说性能很不稳定，而Ｂ＋树每次必须查找到叶子结点，性能稳定。
 *  在范围查询方面，B+树的优势更加明显。B树的范围查找需要不断依赖中序遍历。首先二分查找到范围下限，在不断通过中序遍历，知道查找到范围的上限即可。整个过程比较耗时。而B+树的范围查找则简单了许多。首先通过二分查找，找到范围下限，然后同过叶子结点的链表顺序遍历，直至找到上限即可，整个过程简单许多，效率也比较高。

由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引，而B树则常用于文件索引。

**B树的查找过程:**

![这里写图片描述][70 1]

** B+树的查找过程：**

![这里写图片描述][70 2]

### ***B+树的插入***                       ###

![20190316113059446.png][]

**假设我们要向上图插入0，发现没有破坏B+树结构，直接在1，2结点处插入即可。**

**    如果在结点的中间插入并破坏了B+树的结构：**

但是如果我们要插入12，则发现破坏了B+树的结构，则：

![2019031611315872.png][]

分裂破坏了结构的结点，并将12移到上结点：

![20190316113218644.png][]

插入完毕。

如果在端点处插入并破坏了B+树的结构：

假如插入16：

![20190316113254256.png][]

分裂后，父结点要配合子结点的端点值：

![20190316113310171.png][]

删除操作，只需将插入操作进行反向操作即可。读者可以想想如何删除16。

***B+树的优势：***

*  **单一节点存储更多的元素，使得查询的IO次数更少。（应用于文件系统、数据库系统）**
 *  **所有查询都要查找到叶子节点，查询性能稳定。**
 *  **所有叶子节点形成有序链表，便于范围查询。**

### 为什么说B+树比B树更适合实际应用中数据库的索引？ ###

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

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

### 红黑树和平衡二叉树区别如下： ###

1、红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。  
   2、平衡二叉树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知。

### 小结 ###

B树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中。

此博客参考网上信息：

[https://blog.csdn.net/qq\_17612199/article/details/50944413][https_blog.csdn.net_qq_17612199_article_details_50944413]

[http://www.cnblogs.com/skywang12345/p/3624343.html][Link 1]

[20190316114416513.JPG]: /images/20220307/b9ba55cae67f434c9359e14b892f2098.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70]: /images/20220307/3e2641919b2b4618b0b3397da36d5c5f.png
[Link 1]: http://www.cnblogs.com/skywang12345/p/3624343.html
[70]: /images/20220307/dce81c87c18c4e22b0bd12592dd072a7.png
[20190316112209216.png]: /images/20220307/7be4225290d64ca7895b7909411228bd.png
[20190316112217244.png]: /images/20220307/c3a40db48e374b919e3994ff49271fb3.png
[20190316112230198.png]: /images/20220307/1107f8ee458049c79725cbf484d275a5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 1]: /images/20220307/a7b343b20ce5437d942eb5b8191a7884.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 2]: /images/20220307/9048d507cf07486aab6fb3f112d4effe.png
[70 1]: /images/20220307/4f43fad712154faa81b4df8f2a4a7f48.png
[70 2]: /images/20220307/d246caca27f947f7af785168083be1f1.png
[20190316113059446.png]: /images/20220307/c7554a8b12f840afa6923f513f4947fe.png
[2019031611315872.png]: /images/20220307/686645a547904c68b8bce3bcab99fa12.png
[20190316113218644.png]: /images/20220307/375764dff6614d39a2dc4c5b4c42ee83.png
[20190316113254256.png]: /images/20220307/d50d48ad37054cc5ba26f142ad59fbee.png
[20190316113310171.png]: /images/20220307/9ac0a6bf1dac4b02b7bc82c1062b5ea1.png
[https_blog.csdn.net_qq_17612199_article_details_50944413]: https://blog.csdn.net/qq_17612199/article/details/50944413