动画 | 什么是红黑树？（基于2-3树）

蔚落 2023-06-26 03:24 100阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![format_png][]

学习过2-3树之后就知道应怎样去理解红黑树了，如果直接看「算法导论」里的红黑树的性质，是看不出所以然。我们也看看一颗二分搜索树满足红黑的性质：

1.每个节点或是红色的，或是黑色的；

2.根节点是黑色的；

3.每个叶子节点（NIL）是黑色的；

4.如果一个节点是红色的，则它的两个子节点都是黑色的；

5.对每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点。

如果说前面4个还算理解，那第5个性质又是怎么去理解呢？此时我们借着2-3树去理解基本的红黑树，当然我会在后几篇文章介绍2-3-4树以及基于2-3-4树的红黑树。

抛开上面二分搜索树满足红黑的性质，我们知道2-3树不是二叉树，我们把它转换成一颗二叉树，2-节点很好转，3-节点转二叉却有两种，如下图：

![format_png 1][]

红黑是指被指向节点的链接颜色，对于一颗2-3树，因为3-节点的存在有很多不同的二叉树的表示，所以我们只考虑左倾的情况。

左倾红黑树和2-3树等价的定义

红黑树的定义是含有红黑链接并满足下列条件的二分搜索树：

1.红链接均为左连接；

2.没有任何一个节点同时和两条红链接相连；

3.该树是完美黑色平衡的，即任意空链接到根节点的路径上的黑链接数量相同（和2-3树等价的，任意节点到其叶子节点的高度都是相同的）。

因为2-3树不存在永久的4-节点，4-节点终归要分解的（在2-3-4树中，为了更好地插入和删除，4-节点只存在于叶子节点，非叶子节点和2-3树一样的），所以在2-3树中没有任何一个节点能同时和两条红链接相连。对于第3条，2-3树本身是绝对平衡的，将3-节点转成二叉只增加了左红链接，其他黑链接没有什么变化，依然是黑色平衡的。

查找元素

查找命中和二分搜索树一样，从根节点开始，如果查找命中则返回，否则比它小的进行左递归查找，比它大的进行右递归查找，直到查找为空。

写插入元素和删除元素之前，还是要先介绍一下旋转和颜色转换。

旋转

在插入或者删除操作中可能会出现右倾或者两条连续的红链接，在向上变换的过程中（恢复）都要调整为左倾。

假设有一条红色的右链接需要转为左链接，如下图所示：

![format_png 2][]

这个操作叫做左旋转，右链接变成左链接，意味着被红链接指向的节点会变成红色，根节点默认是黑色。

右旋转也一样，不过在左倾红黑树中，只有出现两条连续红色的左连接才会进行右旋转，如下图：

![format_png 3][]

Code：左旋转和右旋转

![format_png 4][]

颜色转换

颜色转换是用在临时4-节点上的，不管是向下变换还是向上变换。

![format_png 5][]

Code：颜色转换

![format_png 6][]

插入元素

插入元素也需要先进行查找命中，查找未命中则在此节点（NIL）插入一个元素，是在红黑树底下插入一个红色节点，插入元素默认是红色节点。

如果红黑树目前是一颗空树，可以直接存储一个元素作为节点，然后该节点变成黑色。如果不是一颗空树，插入元素分两种情况：向2-节点插入新元素和向3-节点插入新元素。

向2-节点插入新元素有两种情况

向2-节点插入新元素很简单，如果新元素小于父节点的元素，直接插入红色的节点即可；如果新元素大于父节点的元素，则产生一个红色右链接，插完之后进行向上变换，在向上变换的过程中（修复红黑树的性质）需要进行左旋转，将右链接变成左链接，满足左倾红黑树的性质。

![format_png 7][]

向3-节点插入新元素有三种情况

1.新元素小于3-节点最小值

2.新元素位于3-节点最小值和最大值之间

3.新元素大于3-节点最大值

![format_png 8][]

插入元素只有向上变换的过程，目的是为了满足红黑性质。

动画：插入元素

Code：插入元素

![format_png 9][]

删除元素

删除元素既有向下变换也有向上变换：向下变换是为了树底下有一个被红链接指向的节点可以被删除，不影响黑色平衡；向上变换是为了修复基于2-3树的左倾红黑树。

Code：向上变换（修复调整）

![format_png 10][]

删除元素有4个原则：

1.删除元素的当前节点不能是2-节点；

2.向下变换不为2-节点；

3.从树底部删除节点；

4.向上变换，消除右倾和4-节点。

删除元素借鉴了之前学的二分搜索树删除元素的思想，二分搜索树删除元素分为删除最小元素、删除最大元素和删除任意元素三种情况：删除最小元素是一直递归它的左孩子，直到左孩子为空才进行删除；删除最大的元素则相反；如果是删除任意的元素需要进行命中查找，找到了就取右子树的最小值替换掉待删除元素，然后进行右子树的删除最小元素。

红黑树删除元素也是一样的，不过是多了向下变换和向上变换的过程。因为是左倾红黑树，删除最小元素是最合适的。

删除最小元素

「算法4」里的红黑树介绍了删除最小键这一小节，虽没有很详细地介绍，但给出了沿着左链接向下变换的三种情况：

1.如果当前节点（父节点位置）的左子节点不是2-节点，完成；

2.如果当前节点（父节点位置）的左子节点是2-节点而左子节点的兄弟节点不是2-节点，则左子节点借它的兄弟节点的一个键过来；

3.如果当前节点（父节点位置）的左子节点和左子节点的兄弟节点都是2-节点，将左子节点、当前节点和左子节点的兄弟节点合并成一个临时的4-节点，使当前节点由3-节点变成2-节点或则4-节点变成3-节点。

![format_png 11][]

Code：moveRedLeft

![format_png 12][]

删除最大节点思路也是一样的，不过这是左倾红黑树，对删除最大节点益处不大，甚至向下转换的时候左倾调整为右倾，向上转换balance还要将右倾调整为左倾。

动画：删除最小元素

Code：删除最小元素

![format_png 13][]

删除任意元素

在前面学习了删除最小节点，删除任意节点自然就很简单了。我们如果要删除一个节点，首先进行命中查找，查找到这个待删除元素，将右子树的最小值替换掉这个待删除元素，指向待删除节点的链接颜色不能被改变。然后进行右子树的删除最小元素。

在命中查找过程中，需要沿着左链接或沿着右链接进行向下转换。前面删除最小元素就是沿着左链接向下转换的。

沿着右链接向下转换也分三种情况：

1.如果当前节点（父节点位置）的右子节点不是2-节点，将左倾转换成右倾；

2.如果当前节点（父节点位置）的右子节点是2-节点而右子节点的兄弟节点不是2-节点，则右子节点借它的兄弟节点的一个键过来；

3.如果当前节点（父节点位置）的右子节点和右子节点的兄弟节点都是2-节点，将右子节点、当前节点和右子节点的兄弟节点合并成一个临时的4-节点，使当前节点由3-节点变成2-节点或则4-节点变成3-节点。

![format_png 14][]

Code：moveRedRight

![format_png 15][]

Code：删除任意元素

![format_png 16][]

动画：删除任意元素

阅读原文可查看算法4里的RedBlackTree.java源码

**-----------------------**

**公众号：五分钟学算法****（ID：CXYxiaowu****）**

**博客：www.cxyxiaowu.com**

**知乎：程序员吴师兄**

**一个正在学习算法的人，致力于将算法讲清楚！**

长按下图二维码关注，和你一起领悟算法的魅力**。**

![format_png 17][]

**戳一下下方的小程序，24 小时一起学算法**

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVFUN2tTdnJpYk9tQW5HeGpGczdaMWhTZjhrbjJQRUlrWTlwaWJWaWJraDZ0SW15WkdEdzZpYnhSNW9ibnZqVWliOXlRYkR6RHpvOWxNaHNhQS82NDA?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbU43cmdpYlIzWFVmTjRTZThueDdqUUl1RVNmZEFXZUVrZ2dJZThLSXNXbW9GcUlPY2U0VUowcFg3SUMxWW5ickxYSTdmNEZkWFJaVXcvNjQw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbU43cmdpYlIzWFVmTjRTZThueDdqUUlwUVhlMng0dUQ3MmxIN1VaUk94SzZlOVdvVEF4MHFlS2VpYTlqckxPdmpxTHV4enNhaFl3NzFnLzY0MA?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbU43cmdpYlIzWFVmTjRTZThueDdqUUlpY0RjTTZhajI1TnJPR0FNNDNMdFViV0V5cGZlV1BaR3lzcXp5aWFoaWNpY2xZN2Y3eGhKbld4RnZRLzY0MA?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbU43cmdpYlIzWFVmTjRTZThueDdqUUlGRHNpYTRvaWE4V2drZllielFGdFJpYWdTUmFFV1pjNTg2OURnOGwzaWE4YmNJcTVnUjZpYlg5R29IZy82NDA?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbU43cmdpYlIzWFVmTjRTZThueDdqUUlnNjd6MGtZVTlRNHdJdmxpYXhoZFdReTZNSjg1aGdTZGxUM1JQT2FiNngwVm1YdGhPNnoyZ2JRLzY0MA?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbU43cmdpYlIzWFVmTjRTZThueDdqUUlwWEJmWWx5R3l1bnBIRjZsUkJla0NZenJUdUFtSzlQdGxhN0R1dW5FR3hKRDRHcURLOWc1aWN3LzY0MA?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbU43cmdpYlIzWFVmTjRTZThueDdqUUlFdElXTGlhV0xLRTBiU0lmUzBIM1BhdGdsN2V5WDJ4emRYb0swTTJpYnh6S1JpYmRsOGcwYXVteEEvNjQw?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbU43cmdpYlIzWFVmTjRTZThueDdqUUlWejl0UFN4UDNmUTNjaWJhbHQzQklKWVc1bEdkQ0dCVDYyZ2ljNEsybUJ0NEd0cHVXYWlhTFRpYW5nLzY0MA?x-oss-process=image/format,png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbU43cmdpYlIzWFVmTjRTZThueDdqUUlpYnR6anRSaWNlOUpPNFAydURNalpXVFlYMjlqMlVmc012NVp6dkJjQUJhdUprWmIzZ2h6R0RFQS82NDA?x-oss-process=image/format,png
[format_png 10]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbU43cmdpYlIzWFVmTjRTZThueDdqUUk4bTRrTm55dG5NSEhKM3FBTVU5SDNON3dpY0E0V2xpYzU2aGZvTzd3djJPSXh2NmVWc09qdWlhamcvNjQw?x-oss-process=image/format,png
[format_png 11]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbU43cmdpYlIzWFVmTjRTZThueDdqUUlWOGtNUDZHWEpRckNxUHFjczZmcHhhdnRUcmxpYXJDOThoVm1CY1VHdUJXRG9vTERScHBhdU9nLzY0MA?x-oss-process=image/format,png
[format_png 12]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbU43cmdpYlIzWFVmTjRTZThueDdqUUk4YUdpYmljU0NXa3luajlCVklmOGxMVElhR3lYS1psY2g5bkhXYmNIN2FUTU1CZFZCZ0szWTdUUS82NDA?x-oss-process=image/format,png
[format_png 13]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbU43cmdpYlIzWFVmTjRTZThueDdqUUl3SFQ2NVR3cXBwcUluV1dzYWlhcHZCaWIwQndjRWlhRHE5VnNQekQ3eXYzYXAydlZpYnNEY2NNTEFnLzY0MA?x-oss-process=image/format,png
[format_png 14]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbU43cmdpYlIzWFVmTjRTZThueDdqUUlsT3dsR3VXcDh2S2liaWJVcER1NXVBZWVaRUVRNlhWa3RsN1F1V0F0NWxjaWNTYk42RVJINzNQVEEvNjQw?x-oss-process=image/format,png
[format_png 15]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbU43cmdpYlIzWFVmTjRTZThueDdqUUl1dGliOEJ2aER5RW9sR3JHZkJoWWR1UnRIWk9LaWF5MkxBSW1pYm9rZElVUXNLTHFFNkV2Q1hSYXcvNjQw?x-oss-process=image/format,png
[format_png 16]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbU43cmdpYlIzWFVmTjRTZThueDdqUUlpYUJrWEVLQjUzMlhYQmI3OTJRZ01pYVN1TVFrSVNOdDNXN0dUZFNNdFVuR1hQRm5YVVNlYUExUS82NDA?x-oss-process=image/format,png
[format_png 17]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVJnTjYxb1pBaWFiNHpKOE9SbG03ektWY2lhUTFGRFFkSHFpYXA5UjlmTWRVM29BWkxiNEwxWk50dnFzeFFLbGljVkxpY0d4ekZ2NFRmV3BtQS82NDA?x-oss-process=image/format,png