红黑树的快速实现

痛定思痛。 2024-02-18 23:43 39阅读 0赞

#### 红黑树的概述： ####

红黑树本质上是一种二叉查找树，但它在二叉查找树的基础上额外添加了一个标记（颜色），同时具有一定的规则。这些规则使红黑树保证了一种平衡，插入、删除、查找的最坏时间复杂度都为 O(logn)。

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

#### 红黑树的性质： ####

1、每个节点要么是**红色**，要么是**黑色**；  
2、根节点永远是**黑色**的；  
3、所有的叶节点都是是**黑色**的（注意这里说叶子节点其实是上图中的 NIL 节点）；  
4、每个红色节点的两个子节点一定都是**黑色**；  
5、从任一节点到其子树中每个叶子节点的路径都包含**相同数量**的黑色节点。

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

#### 红黑树的旋转 ####

左旋：将一个向右倾斜的红色链接旋转为向左链接。对比操作前后，可以看出，该操作实际上是将红线链接的两个节点中的一个较大的节点移动到根节点上。

![aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xMjM0ODQ2MS05MWM4YmFhNzlkMjhiNmJkLmdpZg][]

右旋：与左旋刚好相反，这里就不赘述了，直接看图。

![aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xMjM0ODQ2MS03ZDg2MzY4NDJjMzIxNjBiLmdpZg][]

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

#### 红黑树的插入与调整 ####

因为要满足红黑树的这五条性质，如果我们插入的是黑色节点，那就违反了性质五，需要进行大规模调整；如果我们插入的是红色节点，那就只有在要插入节点的父节点也是红色的时候违反性质四或者当插入的节点是根节点时，违反性质二，所以，我们把要插入的节点的颜色变成红色。

不需要调整的情况：  
1、当插入的节点是根节点时，直接涂黑即可；  
2、当要插入的节点的父节点是黑色的时候，这个时候插入一个红色的节点并没有对这五个性质产生破坏。所以直接插入不用在进行调整操作。

需要调整的情况：即插入节点的父结点也是*红色*。  
因为左右对称的缘故，在此只讨论父结点位于祖父节点的左支的情况（N 为插入节点）：

1、叔叔节点是红色  
这时候只进行换色操作：将父结点和叔叔节点涂成黑色，祖父节点涂成红色。

![format_png][]

2、叔叔节点是黑色，插入节点位于父节点的右支  
这时候需要将父结点当成新的插入节点，并以他为支点进行左旋操作，进入情况3 。

![format_png 1][]

3、叔叔节点是黑色，插入节点位于父结点的左支  
这时候需要先进行换色操作：将父结点涂成黑色，祖父节点涂成红色；然后进行右旋操作。

![format_png 2][]

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

#### 红黑树的删除与调整 ####

如果被删除结点有孩子，则需要选一个合适的孩子节点作为新的根节点，称为当前节点。  
1、只有左孩子或只有右孩子，则让该孩子作为当前节点替代被删除结点；  
2、左右孩子均存在，则用被删除结点的中序后继结点作为当前节点替代被删除结点。

注意：替代只是**值的互换，颜色不变**。  
即：当前节点是黑色，被删除结点是红色。替换后，当前节点位于被删除结点的位置，是红色；被删除结点位于当前节点原来的位置，是黑色。

不需要调整的情况：  
1、被删除结点的是红色的；  
2、被删除结点只有一个孩子，用孩子的值替换被删除节点，删除孩子结点。

需要调整的情况：（被删除节点为黑色）  
因为左右对称的缘故，在此只讨论父结点位于祖父节点的左支的情况：  
1、兄弟节点为红色  
这时候需要互换父结点和兄弟节点的颜色，并进行左旋操作。

![format_png 3][]

2、兄弟节点为黑色，且其左右孩子也为黑色  
将兄弟节点涂成红色，再将父结点当成新的被删除结点（只是当成，并不删除）进行一次调整（右图中少了根节点的左孩子被删除元素）。

![format_png 4][]

3、兄弟节点为黑色，且其左孩子为红色  
先换色：左孩子涂成黑色，兄弟节点涂成红色；再以兄弟节点为支点右旋。变成情况4 。

![format_png 5][]

4、兄弟节点为黑色，且其右孩子为红色  
先换色：父结点的颜色赋给兄弟节点，父结点涂成黑色，兄弟节点的右孩子涂成黑色；再左旋（右图中a 的左孩子是被删除元素）。

![format_png 6][]

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

#### 红黑树的查找 ####

与二叉排序树的查找一样：从根节点出发，待找值较大时往右子树方向查找，待找值较小时往左子树方向查找，直到找到匹配的结点。若找不到则查找失败。

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

#### 红黑树的应用 ####

Epoll 实现、Java集合中的 TreeSet 和 TreeMap、C++ STL 中的 set、map，以及 Linux 虚拟内存的管理，都是通过红黑树去实现的。  
在平时也可以应用于各种管理系统的查找算法中，借此提高效率。

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

#### 在线生成红黑树 ####

看完本教程，如果你还不太能清楚的写出红黑树的构造过程，那么，这一个网站将能很好地帮助到你。它不仅支持手动输入结点值，也能随机生成结点，更重要的是，该网站把每一次插入、删除的调整步骤都展现了出来。赶紧试试吧！  
[在线生成红黑树（含变形步骤）][Link 1]

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

更多内容请移步微信公众号 “ 暗星涌动 ”

[aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xMjM0ODQ2MS05MWM4YmFhNzlkMjhiNmJkLmdpZg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/6b1f3b1f51de4442a8b00e1fe9455853.png
[aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xMjM0ODQ2MS03ZDg2MzY4NDJjMzIxNjBiLmdpZg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/49c20740b9414d2482951fa5c5bd3bca.png
[format_png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/f2f9a4d30393401baecf778047cc780b.png
[format_png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/1748a21d73fe4fde8236a87ab19b979d.png
[format_png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/36cd3f0e524a4d7bb48bf06028cda69f.png
[format_png 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/436df6085be54f24b76398f01a498c45.png
[format_png 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/85425b47e8de4d19a9e758b8687b7115.png
[format_png 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/299f9aaea33c4a009348a25035faed77.png
[format_png 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/45312dac89d544ca983755e5ea69eae7.png
[Link 1]: https://sandbox.runjs.cn/show/2nngvn8w