2-3树与红黑树

末蓝、 2022-05-16 03:19 186阅读 0赞

**红黑树与2-3树具有等价性，我们在了解红黑树前先了解2-3树对我们理解红黑树是有帮助的，同时，对于理解B树也是有帮助的（用于磁盘存储，文件系统或数据库存储）**

# 1.  2-3树 #

下面的图片就是一颗2-3树

![70][]

![70 1][]

可以看出，2-3树是一棵绝对平衡的树——根节点到任意一个叶子节点所经过的节点数量是相同的

那么2-3树是怎样来维护它的绝对平衡的呢？我们来看看下面例子

![70 2][]

假设现在有个根节点42，现在要向42添加一个元素37，如果是二分搜索树，则37应该添加到42的左子节点，但是2-3树有一个很重要的性质：**就是对于2-3树来说添加节点绝对不会添加到一个空的位置。**

因为42的左子树为空，所以37只能添加到最后一个叶子节点上，而现在最后一个叶子节点是根节点42，所以37与42融合，成为一个3-节点，此时只有一个节点，整个树是绝对平衡的。

![70 3][]

现在我们又添加一个12，但此时根节点的左子树还是为空，为了保持绝对平衡，12先与根节点融合成为4-节点

![70 4][]

但由于2-3树不能存在4-节点，所以此时的根节点可以分裂成一棵子树，有三个2-节点组成的绝对平衡树

![70 5][]

这里我们总结下：**2-3树中添加一个新的元素，它不会像二分搜索树一样添加到一个空的节点位置，它一定会添加到我们最后搜索到的叶子节点，和它进行融合。**

1）如果我们要融合的节点是个2-节点的话，我们就直接融合成一个3-节点

![70 6][]

2）如果我们融合的节点本来就是一个3-节点的话，我们就临时融合成一个4-节点，然后这个4-节点我们再将它变形，变形成一个子树，如果我们融合的这个3-节点本身就是根节点，那很好办

![70 7][]

如果我们融合的3-节点是叶子节点，父亲节点为2-节点的话

![70 8][]

如果我们融合的3-节点是叶子节点，父亲节点为3-节点的话

![70 9][]

# 2. 红黑树与2-3树的等价性 #

对于红黑树，它只能存在一个元素，所以2-3树中2-节点和3-节点在红黑树中对应的关系

![70 10][]

**所有红色节点都是左倾斜的是人为定义的**

![70 11][]

![70 12][]

我们了解了2-3树和红黑树之间的关系我们可以看下红黑树的相对于BST树的基础代码有哪些变化

![70 13][]

最后，我们来看下红黑树的5个性质：

![70 14][]

我们来一一看下这五条性质：

1）这条就不用讲了：）

2）红黑树本身等价于2-3树，而红黑树中的根节点要不是2-节点，要不就是3-节点，我们看下面这这张图2-3树中2-节点和3-节点的等价图：

![70 10][]

3）第三条我们要看清楚是指的最后的空节点，这条与其说是性质，不如说是定义，我们再红黑树定义空为黑色

4）我们还是可以更据2-3树中2-节点和3-节点的等价图来看

![70 15][]

红色节点下面有两个节点，如果子节点是2-节点的话，那肯定就是黑色，如果是3-节点，那首先连接的也是黑色，然后黑色的左节点才是红色（而对于黑色节点，它的右孩子肯定是黑色，左孩子就不一定了）

5）这条是核心，我们看下下面的图就一清二楚了

![70 16][]

由于红黑树的最大高度为2logn，它会比AVL树的高度高，所以我们再红黑树上对元素的寻找会比AVL慢一点，虽然都是O(logn)级别，但是为什么红黑树这么重要，因为对于红黑树来说，添加与删除元素这两个操作相比于AVL来说更快一些，如果我们存储的数据结构要经常发生添加和删除的变动的话，相应的使用红黑树会更好些。而数据不怎么变动，查询更多的话，AVL还是快一点点。

# 3. 红黑树添加元素的子方法 #

我们先看下在2-3树中添加一个新的元素：

1.  添加进2-节点，形成一个3-节点
2.  添加进3-节点，形成一个4-节点

所以可以看到，红黑树添加节点时，永远添加红色节点，后续再根据树的平衡情况做相应的调整

# 3.1  向2-节点添加元素 #

### 1） 根节点应变为黑色 ###

![70 17][]

### 2） 左旋转 ###

现在有棵红黑树的根节点是42，现在向树中添加一个比42小的元素37，则直接添加即可（加入节点初始都是红色）

![70 18][]

![70 19][]

现在，我们假定红黑树还是只有一个根节点37，现在向树中添加一个比37大的元素42

![70 20][]

![70 21][]

而我们定义我们的红黑树中的红色节点都是向左旋转的，所以我们此时要进行左旋转

![70 22][]

![70 23][]

旋转完成后我们再对两个节点的颜色做个调换

![70 24][]

在这里，可能大家会有疑问，**x.color=node.color，**如果node不是根节点的情况下，node可能是红色，那node和x节点都是红色了啊，大家不用急，这个左旋转只是一个子过程，在左旋转之后，有可能产生两个连续的红色节点，然后我们会将左旋转后产生的新的根x传回去，在传回去之后，在我们添加逻辑中，还要进行更多的后续处理，而这些后续处理将在后面讲到。

左旋转的过程中并不维持红黑树的性质，我们左旋转操作的目的是为了使42和37这两个元素对应成2-3树中的一个3-节点就可以了，接下来看下代码：

![70 25][]

# 3.2 向3-节点添加元素 #

# #

### 1）颜色翻转（flipColors） ###

![70 26][]

因为66比42大，所以66就成为42的右子节点![70 27][]

![70 28][]

上面这个二叉树其实相当于2-3树中的4-节点，如下如

![70 29][]

而且42这个节点还要继续向上做融合才能保持绝对平衡，所以红黑树中就要相应的做颜色的变换，如下

![70 30][]

接下来我们看下代码：

![70 31][]

### 2）右旋转 ###

向3-节点中添加元素12

![70 32][]

![70 33][]

这样的情况在2-3树中相当于：

![70 34][]

所以我们需要对上面的红黑树进行**右旋转**

![70 35][]

![70 36][]

接下来，x要与原先根节点node的颜色相同，并且现在node节点是与现在的根节点x融合的（**现在这个结构还是4-节点**），所以现在node应该是红色

![70 37][]

好，现在我们就可以用到上面讲的**颜色翻转**就行了

![70 38][]

我们来看下代码：

![70 39][]

## ##

### 3）第三种情况 ###

![70 40][]

![70 41][]

我们用之前使用的三个过程就可已完成了

![70 42][]

![70 43][]

![70 44][]

# 4.  添加 #

首先我们对上一节对3-节点中添加元素做个总结，如下图：

![70 45][]

最后我们看下代码

![70 46][]

[70]: /images/20220516/2f9b16b481d04644b6145749f9d26660.png
[70 1]: /images/20220516/7f916e6b83064971942cd5e01e270cad.png
[70 2]: /images/20220516/010bd43b34904cc488f4cf8effc2a88a.png
[70 3]: /images/20220516/bb994623becd4c779513c29d289da4af.png
[70 4]: /images/20220516/aa06567f0258423a8952afbc28a9baed.png
[70 5]: /images/20220516/d192665c51724a599d4c138a758620c0.png
[70 6]: /images/20220516/f0310734daef45ba887f65c259a99208.png
[70 7]: /images/20220516/443e87f649cd4c2eafee14022681fa7c.png
[70 8]: /images/20220516/61df62d92d284357899b7447e31cf92a.png
[70 9]: /images/20220516/ebb1a2be99164b5599f6d0f392fbbb79.png
[70 10]: /images/20220516/f771d8f9028143838a8043c5dab97b4b.png
[70 11]: /images/20220516/c004dc0de68b4d73a1832658a4b5d515.png
[70 12]: /images/20220516/8baabc29c711452d8befcedcd31de45b.png
[70 13]: /images/20220516/8f692c6bfb6f4067a70bdfad8b8ee27d.png
[70 14]: /images/20220516/f49b06f0fc444d468d42dcf79d17d01f.png
[70 15]: /images/20220516/863addf928a4469eb7363ddef35a315a.png
[70 16]: /images/20220516/f1d7bb06877d49b4bbd127fb84e1951b.png
[70 17]: /images/20220516/4e476562624d4795947d68047978ca6b.png
[70 18]: /images/20220516/50994e29ff954421a9f40d6e2efd90cc.png
[70 19]: /images/20220516/bb794351a5604d39ad9ef49a2b66078b.png
[70 20]: /images/20220516/d4d7c1bfb4ab45dcb52210a3542d5512.png
[70 21]: /images/20220516/257b3767d6ef4e32af0726ee00aa9d36.png
[70 22]: /images/20220516/ae2d5b71a91d43ee8f6a3395ac238895.png
[70 23]: /images/20220516/5c351fcc608e46c890304b7920e5182b.png
[70 24]: /images/20220516/d8c8b8fb5b23490cb64117f3a4a73492.png
[70 25]: /images/20220516/2fee9618af7647f8994f93f52ff3fb00.png
[70 26]: /images/20220516/7b037e42fc9348338f7572b35dd68322.png
[70 27]: /images/20220516/628fe4a777ec457691e53dd794cfac69.png
[70 28]: /images/20220516/62f4900a2bab4e05aef8cf88b889d3b6.png
[70 29]: /images/20220516/c6ce8eb7181e4733aa777a679bbf3630.png
[70 30]: /images/20220516/0730f90f69e9404d86e147d85799ab88.png
[70 31]: /images/20220516/fea18df43736497682ceb4c05fa082db.png
[70 32]: /images/20220516/97da69b7989b43338bd60c987f63ef45.png
[70 33]: /images/20220516/c05c1091ba604e90b00df788c8c24700.png
[70 34]: /images/20220516/5676d671e1a545d49209f62a94d34a45.png
[70 35]: /images/20220516/718ea2d009ea4cd1a9a426f62e51d4b5.png
[70 36]: /images/20220516/5c5d839b9d0a41f0afbf90cf72ab7f66.png
[70 37]: /images/20220516/3fd4263cc2804b0891a0acfe925ee0f3.png
[70 38]: /images/20220516/9034947ca18b4add8a2cacf344d62d7f.png
[70 39]: /images/20220516/311f3ae9dcfd4e7c8889a187039f7ac6.png
[70 40]: /images/20220516/e8f9e6b7bb984fd38d3cd62c16afb701.png
[70 41]: /images/20220516/55cbccafcfd249d3b29188a1aa41691e.png
[70 42]: /images/20220516/20831c7430de4af69b4b73357a5fc642.png
[70 43]: /images/20220516/8e445c6d085544cd92038f1c4de228ac.png
[70 44]: /images/20220516/b568c952b99b4c34b6a1eb792a4afe3e.png
[70 45]: /images/20220516/ad73a31741644770a8ff680765f632ca.png
[70 46]: /images/20220516/12940fef204246bba31892a457d049b0.png