漫画：什么是红黑树？

我不是女神ヾ 2022-05-31 10:18 266阅读 0赞

发现了一个的做认真的微信公众号给大家分享一下里面的一篇文章，文章最后有公众号二维码。

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 1][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 2][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 3][]

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

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 4][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 5][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 6][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 7][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 8][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 9][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 10][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 11][]

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

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 12][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 13][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 14][]

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

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

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

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

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

![640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 15][]

1.查看根节点9：

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 16][]

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

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 17][]

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

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 18][]

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

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 19][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 20][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 21][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 22][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 23][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 24][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 25][]

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

![640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 1][]

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

![640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 2][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 26][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 27][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 28][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 29][]

1.节点是红色或黑色。

2.根节点是黑色。

3.每个叶子节点都是黑色的空节点（NIL节点）。

4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

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

![640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 3][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 30][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 31][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 32][]

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

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

![640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 4][]

由于父节点15是黑色节点，因此这种情况并不会破坏红黑树的规则，无需做任何调整。

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

![640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 5][]

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

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 33][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 34][]

**变色**：

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

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

![640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 6][]

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

![640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 7][]

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

![640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 8][]

左旋转：

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

![640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 9][]

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

右旋转：

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

![640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 10][]

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

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 35][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 36][]

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

![640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 5][]

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

![640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 11][]

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

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

![640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 9][]

![640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 12][]

![640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 13][]

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

![640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 14][]

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

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

![640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 10][]

![640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 15][]

![640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 16][]

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

![640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 17][]

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

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

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 37][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 38][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 39][]

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 40][]

几点说明：

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

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

—————END—————

喜欢本文的朋友们，欢迎长按下图关注订阅号程序员小灰

![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 41][]

[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1]: /images/20220531/2e0a1fb824b74a18924b101b1986254f.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 1]: /images/20220531/38db9605f19e436b944fa423fc6dcab4.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 2]: /images/20220531/1b21a8f00f0e463c88248d34cd47577e.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 3]: /images/20220531/7cb7546e24fb42c7bb4472948d91e1da.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 4]: /images/20220531/6d57e5ca82c04249af55c902afd0b1a3.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 5]: /images/20220531/82c00f1c378a491cb3e340b11a2c3188.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 6]: /images/20220531/9169d4567fbe4127857a52c64cfad010.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 7]: /images/20220531/b48c8d2a9c6d477c9ab545deb1720916.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 8]: /images/20220531/b2c6cd6d9985492aa4c56a01991ef8f3.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 9]: /images/20220531/970ac5674a1e4a25b2f3e6a06819dbcc.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 10]: /images/20220531/a001752c83834dbe889f1bbfbad2f1de.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 11]: /images/20220531/7aa408f9c3bf4e6b8d6815580614f5f1.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 12]: /images/20220531/933fe0b5407f451da50aad806a281636.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 13]: /images/20220531/707b33ca369e4b30b7317f15ed14f79a.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 14]: /images/20220531/359eb72d47894d13ad4e9b30f4d8defc.png
[640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1]: /images/20220531/d1739e08b15a45b0b857157dae8a5742.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 15]: /images/20220531/8b46ed5b3e004815b26746e4d5faa311.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 16]: /images/20220531/6243289f19c746cab2479fa7d733923c.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 17]: /images/20220531/e6287ca9a07342f3877bd57dfd4bec16.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 18]: /images/20220531/a4bcf6e01d0947d38632cec03347e041.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 19]: /images/20220531/0d5008716124479d94dcdec9d781cce4.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 20]: /images/20220531/57cba2b6c7c34a47b9925549a41d5d62.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 21]: /images/20220531/4f58d63852e047e38f850b7bdf3ec948.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 22]: /images/20220531/9f81658dc81748f48ed34cfb1a2959ff.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 23]: /images/20220531/3bfa1a2c0db24961a990f015d6c6ebc6.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 24]: /images/20220531/350d94ca50474cb79b6f776aa57f6948.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 25]: /images/20220531/d2f4d19179964c2485f7f7c5e27d99ad.png
[640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 1]: /images/20220531/55ca49f6c75c42a0b49b1fac6c08ed9c.png
[640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 2]: /images/20220531/f17ed7ea176e4dd09f52a9edafe14b01.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 26]: /images/20220531/248bbabbe89f40398b7befdb32068ebc.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 27]: /images/20220531/046f05988e104da1b63f0bcb0c2e96b5.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 28]: /images/20220531/f54be97e02b94a5c9f361ecace9607bf.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 29]: /images/20220531/c3b16bfb937c472c92f10d45ea6fcf6e.png
[640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 3]: /images/20220531/4332d19b7bd149b99f62722a3b925120.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 30]: /images/20220531/d8049fc7c5624d399274ed547bfac2ab.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 31]: /images/20220531/2ba484fabbc74a8185c00c3ff3966caa.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 32]: /images/20220531/24a5041dccac46a1981f0adca73a1fef.png
[640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 4]: /images/20220531/c827357e34c0441fbae0e1a92561a4fc.png
[640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 5]: /images/20220531/312c7638c2754b8da547af7d853c1f57.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 33]: /images/20220531/d60844f90480413082417743687e0e80.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 34]: /images/20220531/7341ec9e2632471583aa54adfa2588d5.png
[640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 6]: /images/20220531/b957dd1ff91b419d8b666803cdb4b31a.png
[640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 7]: /images/20220531/7ceac5f49e5e4e86a0707fe65f49e078.png
[640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 8]: /images/20220531/dc547043fde74bac8b78de883b44af1c.png
[640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 9]: /images/20220531/30f9ee2e31324c0a9e9c0790753e1f88.png
[640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 10]: /images/20220531/1bd69d508f6449b2bb2ec91ebcbbbf16.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 35]: /images/20220531/f5bb1f5451f54f79a724bc3a3e814f32.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 36]: /images/20220531/e9ba8e0a5c6745128532a849c034d1f0.png
[640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 11]: /images/20220531/a84687b164024322919ec7e25c1c2180.png
[640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 12]: /images/20220531/fc4d9781580946ba8f31cb99b5288faf.png
[640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 13]: /images/20220531/0a6cef16c4af4266aa2f550483e36bb7.png
[640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 14]: /images/20220531/08f45ee707c249ddabf33a4634e1e7b4.png
[640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 15]: /images/20220531/2e635865a2784bc6930ba05657631559.png
[640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 16]: /images/20220531/a21df06d956c4d678d33e7526d26892f.png
[640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1 17]: /images/20220531/2123f99340c84063838ba9cf8dd34299.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 37]: /images/20220531/4f4b677cea2041f288328c79a64554f4.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 38]: /images/20220531/b0e48037511542a887655d3c547c24bc.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 39]: /images/20220531/a1c507aeb38d44af9f3ab9831af1c3ca.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 40]: /images/20220531/83fcf1ae51b6446f8f688b095354d1d7.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1 41]: /images/20220531/fb30105a9fed48ada01f7c1e8d51b7d7.png