红黑树，B树基本概念

朴灿烈づ我的快乐病毒、 2022-04-24 07:46 253阅读 0赞

(6)常见数据结构  
        A:栈 先进后出  
        B:队列 先进先出  
        C:数组 查询快，增删慢  
        D:链表 查询慢，增删快

> 二叉树

特点：

<table> 
 <tbody> 
 <tr> 
 <td> <h1>前戏</h1> 红黑树，对很多童鞋来说，是既熟悉又陌生。熟悉是因为在校学习期间，准备面试时，这是重点。然后经过多年的荒废，如今已经忘记的差不多了。如果正在看文章的你，马上快要毕业，面临着找工作的压力；又或者你觉得需要将这块知识重新复习一遍；又或者只是看看，那么恭喜你，赚到了。那么我将带领大家重新认识下红黑树，用简单的语言，搞懂红黑树。 在学习红黑树之前，咱们需要先来理解下二叉查找树（BST） 1， 查找到根节点9，看下图： &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<img alt="五分钟搞懂什么是红黑树（全程图解）" height="181" src="https://imgconvert.csdnimg.cn/aHR0cDovL2ltYWdlMTA5LjM2MGRvYy5jb20vRG93bmxvYWRJbWcvMjAxOC8wOS8wNDE5LzE0MzI1Mjk2M18yXzIwMTgwOTA0MDc1OTA1MzY0" width="322"> 2， 由于10大于9的，所以查找到右孩子13，看下图： &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<img alt="五分钟搞懂什么是红黑树（全程图解）" height="177" src="https://imgconvert.csdnimg.cn/aHR0cDovL2ltYWdlMTA5LjM2MGRvYy5jb20vRG93bmxvYWRJbWcvMjAxOC8wOS8wNDE5LzE0MzI1Mjk2M18zXzIwMTgwOTA0MDc1OTA1Njky" width="329"> 3， 又因为10是小与13的，所以查找到左孩子11，看下图： &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;<img alt="五分钟搞懂什么是红黑树（全程图解）" height="197" src="https://imgconvert.csdnimg.cn/aHR0cDovL2ltYWdlMTA5LjM2MGRvYy5jb20vRG93bmxvYWRJbWcvMjAxOC8wOS8wNDE5LzE0MzI1Mjk2M180XzIwMTgwOTA0MDc1OTA1NzU0" width="363"> 4， 这一步相比不用说了大家也都知道了，找到了左孩子，然后发现正好是10 。恰好是正要寻找的值。 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<img alt="五分钟搞懂什么是红黑树（全程图解）" height="206" src="https://imgconvert.csdnimg.cn/aHR0cDovL2ltYWdlMTA5LjM2MGRvYy5jb20vRG93bmxvYWRJbWcvMjAxOC8wOS8wNDE5LzE0MzI1Mjk2M181XzIwMTgwOTA0MDc1OTA1OTI2" width="381"> 可能又有童鞋会问，这不是二分查找的思想吗？确实，查找所需的最大次数等同于二叉查找树的高度。当然在插入节点的时候，也是这种思想，一层一层的找到合适的位置插入。但是二叉查找树有个比较大的缺陷，而且这个缺陷会影响到他的性能。我们先来看下有一种情况的插入操作： 如果初始的二叉查找树只有三个节点，如下图： &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;<img alt="五分钟搞懂什么是红黑树（全程图解）" height="112" src="https://imgconvert.csdnimg.cn/aHR0cDovL2ltYWdlMTA5LjM2MGRvYy5jb20vRG93bmxvYWRJbWcvMjAxOC8wOS8wNDE5LzE0MzI1Mjk2M182XzIwMTgwOTA0MDc1OTA2NA" width="235"> 我们依次插入5个节点：7，6,5,4,3,。看下图插入之后的图： &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;<img alt="五分钟搞懂什么是红黑树（全程图解）" height="277" src="https://imgconvert.csdnimg.cn/aHR0cDovL2ltYWdlMTA5LjM2MGRvYy5jb20vRG93bmxvYWRJbWcvMjAxOC8wOS8wNDE5LzE0MzI1Mjk2M183XzIwMTgwOTA0MDc1OTA2Njc" width="244"> 看出来了吗？有没有觉得很别扭，如果根节点足够大，那是不是“左腿”会变的特别长，也就是说查找的性能大打折扣，几乎就是线性查找了。 那有没有好的办法解决这个问题呢？解决这种多次插入新节点而导致的不平衡？这个时候红黑树就登场了。 &nbsp; &nbsp; <h1>红黑树</h1> 红黑树就是一种平衡的二叉查找树，说他平衡的意思是他不会变成“瘸子”，左腿特别长或者右腿特别长。除了符合二叉查找树的特性之外，还具体下列的特性： 1. 节点是红色或者黑色 2. 根节点是黑色 3. 每个叶子的节点都是黑色的空节点（NULL） 4. 每个红色节点的两个子节点都是黑色的。 5. 从任意节点到其每个叶子的所有路径都包含相同的黑色节点。 看下图就是一个典型的红黑树：<img alt="五分钟搞懂什么是红黑树（全程图解）" height="253" src="https://imgconvert.csdnimg.cn/aHR0cDovL2ltYWdlMTA5LjM2MGRvYy5jb20vRG93bmxvYWRJbWcvMjAxOC8wOS8wNDE5LzE0MzI1Mjk2M184XzIwMTgwOTA0MDc1OTA2MTQ1" width="442"> 很多童鞋又会惊讶了，天啊这个条条框框也太多了吧。没错，正式因为这些规则，才能保证红黑树的自平衡。最长路径不超过最短路径的2倍。 当插入和删除节点，就会对平衡造成破坏，这时候需要对树进行调整，从而重新达到平衡。那什么情况下会破坏红黑树的规则呢？ 1，我们看下图： &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;<img alt="五分钟搞懂什么是红黑树（全程图解）" height="267" src="https://imgconvert.csdnimg.cn/aHR0cDovL2ltYWdlMTA5LjM2MGRvYy5jb20vRG93bmxvYWRJbWcvMjAxOC8wOS8wNDE5LzE0MzI1Mjk2M185XzIwMTgwOTA0MDc1OTA2MjA4" width="452"> 向原来的红黑树插入值为14的新节点，由于父节点15是黑色节点，所以这种情况没有破坏结构，不需要做任何的改变。 2，向原树插入21呢？，看下图： &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;<img alt="五分钟搞懂什么是红黑树（全程图解）" height="312" src="https://imgconvert.csdnimg.cn/aHR0cDovL2ltYWdlMTA5LjM2MGRvYy5jb20vRG93bmxvYWRJbWcvMjAxOC8wOS8wNDE5LzE0MzI1Mjk2M18xMF8yMDE4MDkwNDA3NTkwNjMxNw" width="438"> 由于父节点22是红色节点，因此这种情况打破了红黑树的规则4，必须作出调整。那么究竟该怎么调整呢？有两种方式【变色】和【旋转】分为【左旋转】和【右旋转】。 【变色】： 为了符合红黑树的规则，会把节点红变黑或者黑变红。下图展示的是红黑树的部分，需要注意节点25并非根节点。因为21和22链接出现红色，不符合规则4，所以把22红变黑： &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<img alt="五分钟搞懂什么是红黑树（全程图解）" height="198" src="https://imgconvert.csdnimg.cn/aHR0cDovL2ltYWdlMTA5LjM2MGRvYy5jb20vRG93bmxvYWRJbWcvMjAxOC8wOS8wNDE5LzE0MzI1Mjk2M18xMV8yMDE4MDkwNDA3NTkwNjQyNg" width="476"> 但这样还是不符合规则5，所以需要把25黑变红，看下图： &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<img alt="五分钟搞懂什么是红黑树（全程图解）" height="172" src="https://imgconvert.csdnimg.cn/aHR0cDovL2ltYWdlMTA5LjM2MGRvYy5jb20vRG93bmxvYWRJbWcvMjAxOC8wOS8wNDE5LzE0MzI1Mjk2M18xMl8yMDE4MDkwNDA3NTkwNjU4Mw" width="414"> 你以为现在结束了？天真，因为25和27又是两个连续的红色节点(规则4)，所以需要将27红变黑。 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;<img alt="五分钟搞懂什么是红黑树（全程图解）" height="193" src="https://imgconvert.csdnimg.cn/aHR0cDovL2ltYWdlMTA5LjM2MGRvYy5jb20vRG93bmxvYWRJbWcvMjAxOC8wOS8wNDE5LzE0MzI1Mjk2M18xM18yMDE4MDkwNDA3NTkwNjY2MQ" width="464"> 终于结束了，都满足规则了，舒服多了。 【左旋转】 也就是逆时针旋转两个节点，使父节点被自己的右孩子取代，而自己成为自己的左孩子，听起来吓死人，直接看图吧： &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;<img alt="五分钟搞懂什么是红黑树（全程图解）" height="234" src="https://imgconvert.csdnimg.cn/aHR0cDovL2ltYWdlMTA5LjM2MGRvYy5jb20vRG93bmxvYWRJbWcvMjAxOC8wOS8wNDE5LzE0MzI1Mjk2M18xNF8yMDE4MDkwNDA3NTkwNjc1NA" width="465"> 【右旋转】 顺时针旋转两个节点，使得自己的父节点被左孩子取代，而自己成为自己的右孩子，看不懂直接看图吧： &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;<img alt="五分钟搞懂什么是红黑树（全程图解）" height="186" src="https://imgconvert.csdnimg.cn/aHR0cDovL2ltYWdlMTA5LjM2MGRvYy5jb20vRG93bmxvYWRJbWcvMjAxOC8wOS8wNDE5LzE0MzI1Mjk2M18xNV8yMDE4MDkwNDA3NTkwNjkyNg" width="421"> 看起来这么复杂，到底怎么用呢？确实很复杂，我们讲下典型的例子，大家参考下： 以刚才插入21节点的例子： &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<img alt="五分钟搞懂什么是红黑树（全程图解）" height="303" src="https://imgconvert.csdnimg.cn/aHR0cDovL2ltYWdlMTA5LjM2MGRvYy5jb20vRG93bmxvYWRJbWcvMjAxOC8wOS8wNDE5LzE0MzI1Mjk2M18xNl8yMDE4MDkwNDA3NTkwNzUx" width="425"> 首先我们需要做的是变色，把节点25以及下方的节点变色： &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<img alt="五分钟搞懂什么是红黑树（全程图解）" height="278" src="https://imgconvert.csdnimg.cn/aHR0cDovL2ltYWdlMTA5LjM2MGRvYy5jb20vRG93bmxvYWRJbWcvMjAxOC8wOS8wNDE5LzE0MzI1Mjk2M18xN18yMDE4MDkwNDA3NTkwNzE5Mg" width="397"> 由于17和25是连续的两个红色节点，那么吧节点17变黑吗？这样是不行的，你想这样一来不就打破了规则4了吗，而且根据规则2，也不可能吧13变成红色。变色已经无法解决问题了，所以只能进行旋转了。13当成X，17当成Y，左旋转试试看： <img alt="五分钟搞懂什么是红黑树（全程图解）" height="200" src="https://imgconvert.csdnimg.cn/aHR0cDovL2ltYWdlMTA5LjM2MGRvYy5jb20vRG93bmxvYWRJbWcvMjAxOC8wOS8wNDE5LzE0MzI1Mjk2M18xOF8yMDE4MDkwNDA3NTkwNzI4Ng" width="398"> <img alt="五分钟搞懂什么是红黑树（全程图解）" height="363" src="https://imgconvert.csdnimg.cn/aHR0cDovL2ltYWdlMTA5LjM2MGRvYy5jb20vRG93bmxvYWRJbWcvMjAxOC8wOS8wNDE5LzE0MzI1Mjk2M18xOV8yMDE4MDkwNDA3NTkwNzM0OA" width="523"><img alt="五分钟搞懂什么是红黑树（全程图解）" height="321" src="https://imgconvert.csdnimg.cn/aHR0cDovL2ltYWdlMTA5LjM2MGRvYy5jb20vRG93bmxvYWRJbWcvMjAxOC8wOS8wNDE5LzE0MzI1Mjk2M18yMF8yMDE4MDkwNDA3NTkwNzQ4OQ" width="464"> 由于根节点必须是黑色，所以需要变色，结果如下图： <img alt="五分钟搞懂什么是红黑树（全程图解）" src="https://imgconvert.csdnimg.cn/aHR0cDovL2ltYWdlMTA5LjM2MGRvYy5jb20vRG93bmxvYWRJbWcvMjAxOC8wOS8wNDE5LzE0MzI1Mjk2M18yMV8yMDE4MDkwNDA3NTkwNzYyOQ"> 继续，其中有两条路径（17-）8-&gt;6-&gt;NULL）的黑色节点个数不是3，是4不符合规则。 这个时候需要把13当做X，8当做Y，进行右旋转： <img alt="五分钟搞懂什么是红黑树（全程图解）" src="https://imgconvert.csdnimg.cn/aHR0cDovL2ltYWdlMTA5LjM2MGRvYy5jb20vRG93bmxvYWRJbWcvMjAxOC8wOS8wNDE5LzE0MzI1Mjk2M18yMl8yMDE4MDkwNDA3NTkwNzcwOA"><img alt="五分钟搞懂什么是红黑树（全程图解）" src="https://imgconvert.csdnimg.cn/aHR0cDovL2ltYWdlMTA5LjM2MGRvYy5jb20vRG93bmxvYWRJbWcvMjAxOC8wOS8wNDE5LzE0MzI1Mjk2M18yM18yMDE4MDkwNDA3NTkwNzgwMQ"><img alt="五分钟搞懂什么是红黑树（全程图解）" src="https://imgconvert.csdnimg.cn/aHR0cDovL2ltYWdlMTA5LjM2MGRvYy5jb20vRG93bmxvYWRJbWcvMjAxOC8wOS8wNDE5LzE0MzI1Mjk2M18yNF8yMDE4MDkwNDA3NTkwNzkxMQ"> 最后根据规则变色： <img alt="五分钟搞懂什么是红黑树（全程图解）" src="https://imgconvert.csdnimg.cn/aHR0cDovL2ltYWdlMTA5LjM2MGRvYy5jb20vRG93bmxvYWRJbWcvMjAxOC8wOS8wNDE5LzE0MzI1Mjk2M18yNV8yMDE4MDkwNDA3NTkwODQ"> 这样一来，我们终于结束了，经过调整之后符合规则。 </td> 
 </tr> 
 </tbody> 
</table>

满二叉树是完全二叉树，对于深度为k的满二叉树中结点数量是2k-1 = n，完全二叉树结点数量肯定最多2k-1,同时完全二叉树倒数第二层肯定是满的（倒数第一层有结点，那么倒是第二层序号和满二叉树相同），所以完全二叉树的结点数最少大于少一层的满二叉树，为2k-1-1。

根据上面推断得出： 2k-1-1< n=<2k-1，因为结点数Nn为整数那么n<=2k-1可以推出n<=2k ,n>2k-1-1可以推出 n>=2k-1,所以2k-1<n<=2k  。即可得k-1<=log2n<k 而k作为整数因此k=\[log2n\]+1。

> # **B树** #

# **二****叉****树的问题分析** #

二叉树的操作效率较高，但是也存在问题, 请看下面的二叉树

1)**二叉树需要加载到内存的，如果二叉树的节点少，没有什么问题，但是如果****二叉****树的节点很多****(****比如****1****亿****)****， 就存在如下问题****:**

2)**问****题****1****：在构建二叉树时，需要多次进行****i/o****操作****(****海量数据存在数据库或文件中****)****，节点海量，构建二叉树时，速度有影响**

3)**问题****2****：节点海量，****也****会造成二叉树的高度很大，会降低操作****速****度****.**

# **B****树的****基****本介绍** #

B树通过重新组织节点，降低树的高度，并且减少i/o读写次数来提升效率。

![20190922210656425.png][]

1)**如图****B****树通过重新组织节点，** **降****低了树的高度****.**

2)**文件系统及数据库系统的设计者利用了磁盘预读原理，将一个节点的大小设为等于一个****页****(**页得大小通常为4k**)****，****这样每个节点只需要一次****I/O****就可以完全载****入**

## **B****树的说明****:** ##

1)B树的阶：节点的最多子节点个数。比如2-3树的阶是3，2-3-4树的阶是4

2)B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点

3)关键字集合分布在整颗树中, 即叶子节点和非叶子节点都存放数据.

4)搜索有可能在非叶子结点结束

5)其搜索性能等价于在关键字全集内做一次二分查找

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1eXVucWlhbmcxMTE_size_16_color_FFFFFF_t_70][]

# **B+****树的介绍** #

B\+树是B树的变体，也是一种多路搜索树。

# **B+****树的说明****:** #

1)B+树的搜索与B树也基本相同，区别是B+树只有达到叶子结点才命中（B树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找

2)所有**关键字都出现在叶子结点的链表中**（即数据只能在叶子节点【也叫稠密索引】），且链表中的关键字(数据)恰好是有序的。

3)不可能在非叶子结点命中

4)非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层

5)更适合文件索引系统

6)B树和B+树各有自己的应用场景，不能说B+树**完全比**B树好，反之亦然.

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1eXVucWlhbmcxMTE_size_16_color_FFFFFF_t_70 1][]

[20190922210656425.png]: /images/20220217/7491007221054d379c5ff7dbedd3aba6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1eXVucWlhbmcxMTE_size_16_color_FFFFFF_t_70]: /images/20220217/de96338f4f944112bed4ae27328a8c62.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1eXVucWlhbmcxMTE_size_16_color_FFFFFF_t_70 1]: /images/20220217/ad21555da24b46b8abd30dd831f0a483.png