漫画算法：什么是红黑树？

男娘i 2022-02-28 00:44 250阅读 0赞

来源：伯乐专栏作者/玻璃猫，微信公众号 - 程序员小灰

[http://www.sohu.com/a/201923614\_466939][http_www.sohu.com_a_201923614_466939]

--------------------

![67260ece502d47d9b0db602516827eff.jpeg][]

![8b5ccac51f34434d964258e5d6687978.jpeg][]

![9cca33e80bc74faba44b930724e49f64.jpeg][]

![3062093a52b447cba487d7e235b9d7c6.jpeg][]

![e7b2959192aa4146a602b89ddbecae1f.jpeg][]

![dd7edd987de74efdb57cb7763a067d98.jpeg][]

![2ccc7032574f4824a239638091e792ce.jpeg][]

![502b54c458894438ac74ba59e02b8b51.jpeg][]

![e1052cda577842cb86c241e725bc8b47.jpeg][]

![3384350d0e75420ca1c44e4f68b4b305.jpeg][]

![ad65da97fc6643d384c375cc407cf8a0.jpeg][]

————————————

![77189be89ec14d06a36a6125c4ce1c2d.jpeg][]

![d7ea64ec17f949aba3214a7c0a66da4f.jpeg][]

![b3d4b3a4012c4104a0c4c2ce10f20784.jpeg][]

**二叉查找树（BST）具备什么特性呢？**

1.左子树上所有结点的值均小于或等于它的根结点的值。

2.右子树上所有结点的值均大于或等于它的根结点的值。

3.左、右子树也分别为二叉排序树。

下图中这棵树，就是一颗典型的二叉查找树：

![2d5ac4356e1f4d76a849862b80cfb0a5.jpeg][]

1.查看根节点9：

![202128cf82084e64a251b458f0ddcd9b.jpeg][]

2.由于10 > 9，因此查看右孩子13：

![03f91d80755843c796777925e2ec30fd.jpeg][]

3.由于10 < 13，因此查看左孩子11：

![4e8d133618af440384439bc6bac2fb64.jpeg][]

4.由于10 < 11，因此查看左孩子10，发现10正是要查找的节点：

![9182fc564c2f4e43a21ccf5303ff52f2.jpeg][]

![e9b367e9c0d64a9daa34a05f90e29215.jpeg][]

![aa89019ee4714be5af06f711e3708876.jpeg][]

![90a859b8d3f3458a8ab2fc918de7d7eb.jpeg][]

![acd4821be66e4c8bba1acc94f8442fdb.jpeg][]

![020ee565d63142b3a5a28a3da7f147d7.jpeg][]

![76747b669de04a23bd8230356de87880.jpeg][]

假设初始的二叉查找树只有三个节点，根节点值为9，左孩子值为8，右孩子值为12：

![be7648945b8c486e89a659862226dc78.png][]

接下来我们依次插入如下五个节点：7,6,5,4,3。依照二叉查找树的特性，结果会变成什么样呢？

![3490195d7e3a405c97c34d391c71f09b.png][]

![7f5e4ce8e6d84cd09ed4100d4787f6a3.jpeg][]

![bb37a41b5e214bbc84d715e91d53e4cd.jpeg][]

![dcc085654a894782a80beaddac3bb539.jpeg][]

![be0ee1c118d34cefafb49a473405ed15.jpeg][]

> 1.节点是红色或黑色。
> 
> 2.根节点是黑色。
> 
> 3.每个叶子节点都是黑色的空节点（NIL节点）。
> 
> 4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
> 
> 5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

下图中这棵树，就是一颗典型的红黑树：

![eefb5a3397ef4089b356e7c9f0938a8d.jpeg][]

![afe0c004a93a4f2bb48f3238a2399cdd.jpeg][]

![9f456ef7f4d248e2a1d85c4a5bea34ac.jpeg][]

![41cc88c556db4c08b25d7b112538deea.jpeg][]

什么情况下会破坏红黑树的规则，什么情况下不会破坏规则呢？我们举两个简单的栗子：

1.向原红黑树插入值为14的新节点：

![1f1a6ca2e3674e71bb5e815c3d042ee5.jpeg][]

2.向原红黑树插入值为21的新节点：

![c0042741a40d47249e287908c16a9203.jpeg][]

由于父节点22是红色节点，因此这种情况打破了红黑树的规则4（每个红色节点的两个子节点都是黑色），必须进行调整，使之重新符合红黑树的规则。

![5cba1325f2ab4248b5819ec42c7c0d6c.jpeg][]

![9879d043f1474808b53de100f88dab33.jpeg][]

**变色：**

为了重新符合红黑树的规则，尝试把红色节点变为黑色，或者把黑色节点变为红色。

下图所表示的是红黑树的一部分，需要注意节点25并非根节点。因为节点21和节点22连续出现了红色，不符合规则4，所以把节点22从红色变成黑色：

![142bd79263094ec89bccb2cfd8316113.png][]

但这样并不算完，因为凭空多出的黑色节点打破了规则5，所以发生连锁反应，需要继续把节点25从黑色变成红色：

![3e651c84a1494495a73287df0ca92216.jpeg][]

此时仍然没有结束，因为节点25和节点27又形成了两个连续的红色节点，需要继续把节点27从红色变成黑色：

![a8c4ce5620424588bdbee69f4bb3d527.png][]

**左旋转：**

逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子。说起来很怪异，大家看下图：

![b3cd82550b29445eac5b6e6b0f40f03c.png][]

图中，身为右孩子的Y取代了X的位置，而X变成了自己的左孩子。此为左旋转。

**右旋转：**

顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子。大家看下图：

![c739da55ba784729919bc18b57c3a5c3.png][]

图中，身为左孩子的Y取代了X的位置，而X变成了自己的右孩子。此为右旋转。

![bb8724b6cf3c41dc91fdcaa1d792690d.jpeg][]

![9bad19884c284d34b521ac32d0c530e7.jpeg][]

我们以刚才插入节点21的情况为例：

![7a4055b4eaa14fd097ffa241abd86032.jpeg][]

首先，我们需要做的是变色，把节点25及其下方的节点变色：

![a0c2409f6c7d4c468a3d1c80c18ebe9b.jpeg][]

此时节点17和节点25是连续的两个红色节点，那么把节点17变成黑色节点？恐怕不合适。这样一来不但打破了规则4，而且根据规则2（根节点是黑色），也不可能把节点13变成红色节点。

变色已无法解决问题，我们把节点13看做X，把节点17看做Y，像刚才的示意图那样进行左旋转：

![cb7731c2eb4e4e2b839004e3dcaf7126.png][]

![9f6949f1ca624323ad26bd474912571a.jpeg][]

![d7da48b838514b33bd8b44ab1b55c9e1.jpeg][]

由于根节点必须是黑色节点，所以需要变色，变色结果如下：

![d32de019907c4e9a9c2e3490d66677de.jpeg][]

这样就结束了吗？并没有。因为其中两条路径(17 -> 8 -> 6 -> NIL)的黑色节点个数是4，其他路径的黑色节点个数是3，不符合规则5。

这时候我们需要把节点13看做X，节点8看做Y，像刚才的示意图那样进行右旋转：

![2e7e68bb13de4558a66b0a1262e072e7.png][]

![1fdcb0466c7a4ecc84b54cb701781243.jpeg][]

![b3fcbe987f214340b0b03d129b2a2059.jpeg][]

最后根据规则来进行变色：

![79bbe75c48da4a7492c21af0e18065a5.jpeg][]

如此一来，我们的红黑树变得重新符合规则。这一个例子的调整过程比较复杂，经历了如下步骤：

变色 -> 左旋转 -> 变色 -> 右旋转 -> 变色

![9630c04fdf1342649588611ed6996033.jpeg][]

![b13f956364da426c9ba9849654e9459b.jpeg][]

![ea1ad93b413448198ad375bf157c7fce.jpeg][]

![a4b8f455c8ff4ec6b0a778daf3a5b893.jpeg][]

**几点说明：**

1. 关于红黑树自平衡的调整，插入和删除节点的时候都涉及到很多种Case，由于篇幅原因无法展开来一一列举，有兴趣的朋友可以参考维基百科，里面讲的非常清晰。

2.漫画中红黑树调整过程的示例是一种比较复杂的情形，没太看明白的小伙伴也不必钻牛角尖，关键要懂得红黑树自平衡调整的主体思想。

[http_www.sohu.com_a_201923614_466939]: http://www.sohu.com/a/201923614_466939
[67260ece502d47d9b0db602516827eff.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/67260ece502d47d9b0db602516827eff.jpeg
[8b5ccac51f34434d964258e5d6687978.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/8b5ccac51f34434d964258e5d6687978.jpeg
[9cca33e80bc74faba44b930724e49f64.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/9cca33e80bc74faba44b930724e49f64.jpeg
[3062093a52b447cba487d7e235b9d7c6.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/3062093a52b447cba487d7e235b9d7c6.jpeg
[e7b2959192aa4146a602b89ddbecae1f.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/e7b2959192aa4146a602b89ddbecae1f.jpeg
[dd7edd987de74efdb57cb7763a067d98.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/dd7edd987de74efdb57cb7763a067d98.jpeg
[2ccc7032574f4824a239638091e792ce.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/2ccc7032574f4824a239638091e792ce.jpeg
[502b54c458894438ac74ba59e02b8b51.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/502b54c458894438ac74ba59e02b8b51.jpeg
[e1052cda577842cb86c241e725bc8b47.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/e1052cda577842cb86c241e725bc8b47.jpeg
[3384350d0e75420ca1c44e4f68b4b305.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/3384350d0e75420ca1c44e4f68b4b305.jpeg
[ad65da97fc6643d384c375cc407cf8a0.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/ad65da97fc6643d384c375cc407cf8a0.jpeg
[77189be89ec14d06a36a6125c4ce1c2d.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/77189be89ec14d06a36a6125c4ce1c2d.jpeg
[d7ea64ec17f949aba3214a7c0a66da4f.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/d7ea64ec17f949aba3214a7c0a66da4f.jpeg
[b3d4b3a4012c4104a0c4c2ce10f20784.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/b3d4b3a4012c4104a0c4c2ce10f20784.jpeg
[2d5ac4356e1f4d76a849862b80cfb0a5.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/2d5ac4356e1f4d76a849862b80cfb0a5.jpeg
[202128cf82084e64a251b458f0ddcd9b.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/202128cf82084e64a251b458f0ddcd9b.jpeg
[03f91d80755843c796777925e2ec30fd.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/03f91d80755843c796777925e2ec30fd.jpeg
[4e8d133618af440384439bc6bac2fb64.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/4e8d133618af440384439bc6bac2fb64.jpeg
[9182fc564c2f4e43a21ccf5303ff52f2.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/9182fc564c2f4e43a21ccf5303ff52f2.jpeg
[e9b367e9c0d64a9daa34a05f90e29215.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/e9b367e9c0d64a9daa34a05f90e29215.jpeg
[aa89019ee4714be5af06f711e3708876.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/aa89019ee4714be5af06f711e3708876.jpeg
[90a859b8d3f3458a8ab2fc918de7d7eb.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/90a859b8d3f3458a8ab2fc918de7d7eb.jpeg
[acd4821be66e4c8bba1acc94f8442fdb.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/acd4821be66e4c8bba1acc94f8442fdb.jpeg
[020ee565d63142b3a5a28a3da7f147d7.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/020ee565d63142b3a5a28a3da7f147d7.jpeg
[76747b669de04a23bd8230356de87880.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/76747b669de04a23bd8230356de87880.jpeg
[be7648945b8c486e89a659862226dc78.png]: http://5b0988e595225.cdn.sohucs.com/images/20171102/be7648945b8c486e89a659862226dc78.png
[3490195d7e3a405c97c34d391c71f09b.png]: http://5b0988e595225.cdn.sohucs.com/images/20171102/3490195d7e3a405c97c34d391c71f09b.png
[7f5e4ce8e6d84cd09ed4100d4787f6a3.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/7f5e4ce8e6d84cd09ed4100d4787f6a3.jpeg
[bb37a41b5e214bbc84d715e91d53e4cd.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/bb37a41b5e214bbc84d715e91d53e4cd.jpeg
[dcc085654a894782a80beaddac3bb539.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/dcc085654a894782a80beaddac3bb539.jpeg
[be0ee1c118d34cefafb49a473405ed15.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/be0ee1c118d34cefafb49a473405ed15.jpeg
[eefb5a3397ef4089b356e7c9f0938a8d.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/eefb5a3397ef4089b356e7c9f0938a8d.jpeg
[afe0c004a93a4f2bb48f3238a2399cdd.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/afe0c004a93a4f2bb48f3238a2399cdd.jpeg
[9f456ef7f4d248e2a1d85c4a5bea34ac.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/9f456ef7f4d248e2a1d85c4a5bea34ac.jpeg
[41cc88c556db4c08b25d7b112538deea.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/41cc88c556db4c08b25d7b112538deea.jpeg
[1f1a6ca2e3674e71bb5e815c3d042ee5.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/1f1a6ca2e3674e71bb5e815c3d042ee5.jpeg
[c0042741a40d47249e287908c16a9203.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/c0042741a40d47249e287908c16a9203.jpeg
[5cba1325f2ab4248b5819ec42c7c0d6c.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/5cba1325f2ab4248b5819ec42c7c0d6c.jpeg
[9879d043f1474808b53de100f88dab33.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/9879d043f1474808b53de100f88dab33.jpeg
[142bd79263094ec89bccb2cfd8316113.png]: http://5b0988e595225.cdn.sohucs.com/images/20171102/142bd79263094ec89bccb2cfd8316113.png
[3e651c84a1494495a73287df0ca92216.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/3e651c84a1494495a73287df0ca92216.jpeg
[a8c4ce5620424588bdbee69f4bb3d527.png]: http://5b0988e595225.cdn.sohucs.com/images/20171102/a8c4ce5620424588bdbee69f4bb3d527.png
[b3cd82550b29445eac5b6e6b0f40f03c.png]: http://5b0988e595225.cdn.sohucs.com/images/20171102/b3cd82550b29445eac5b6e6b0f40f03c.png
[c739da55ba784729919bc18b57c3a5c3.png]: http://5b0988e595225.cdn.sohucs.com/images/20171102/c739da55ba784729919bc18b57c3a5c3.png
[bb8724b6cf3c41dc91fdcaa1d792690d.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/bb8724b6cf3c41dc91fdcaa1d792690d.jpeg
[9bad19884c284d34b521ac32d0c530e7.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/9bad19884c284d34b521ac32d0c530e7.jpeg
[7a4055b4eaa14fd097ffa241abd86032.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/7a4055b4eaa14fd097ffa241abd86032.jpeg
[a0c2409f6c7d4c468a3d1c80c18ebe9b.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/a0c2409f6c7d4c468a3d1c80c18ebe9b.jpeg
[cb7731c2eb4e4e2b839004e3dcaf7126.png]: http://5b0988e595225.cdn.sohucs.com/images/20171102/cb7731c2eb4e4e2b839004e3dcaf7126.png
[9f6949f1ca624323ad26bd474912571a.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/9f6949f1ca624323ad26bd474912571a.jpeg
[d7da48b838514b33bd8b44ab1b55c9e1.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/d7da48b838514b33bd8b44ab1b55c9e1.jpeg
[d32de019907c4e9a9c2e3490d66677de.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/d32de019907c4e9a9c2e3490d66677de.jpeg
[2e7e68bb13de4558a66b0a1262e072e7.png]: http://5b0988e595225.cdn.sohucs.com/images/20171102/2e7e68bb13de4558a66b0a1262e072e7.png
[1fdcb0466c7a4ecc84b54cb701781243.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/1fdcb0466c7a4ecc84b54cb701781243.jpeg
[b3fcbe987f214340b0b03d129b2a2059.jpeg]: /images/20220228/feb3fa48d29c4eb88f2b8cb73e22d4b1.png
[79bbe75c48da4a7492c21af0e18065a5.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/79bbe75c48da4a7492c21af0e18065a5.jpeg
[9630c04fdf1342649588611ed6996033.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/9630c04fdf1342649588611ed6996033.jpeg
[b13f956364da426c9ba9849654e9459b.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/b13f956364da426c9ba9849654e9459b.jpeg
[ea1ad93b413448198ad375bf157c7fce.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/ea1ad93b413448198ad375bf157c7fce.jpeg
[a4b8f455c8ff4ec6b0a778daf3a5b893.jpeg]: http://5b0988e595225.cdn.sohucs.com/images/20171102/a4b8f455c8ff4ec6b0a778daf3a5b893.jpeg