一、《算法—深入淺出》N叉樹(shù)的介紹
二、《算法—深入淺出》紅黑樹(shù)的旋轉(zhuǎn)
三、《算法—深入淺出》紅黑樹(shù)的插入
四、《算法—深入淺出》紅黑樹(shù)的刪除
一独柑、前言
在《紅黑樹(shù)的旋轉(zhuǎn)》一篇中提到過(guò)，RBT的刪除稍微比插入要復(fù)雜一點(diǎn)私植，那么如何復(fù)雜忌栅？又是如何刪除與調(diào)整？本篇將會(huì)給大家揭開(kāi)面紗曲稼！
為了能更清楚簡(jiǎn)單的描述整個(gè)過(guò)程索绪，本篇將分為：
- 查找要?jiǎng)h除的節(jié)點(diǎn)；
- 查找可以替換刪除的節(jié)點(diǎn)躯肌；
- 刪除后不滿足紅黑樹(shù)條件時(shí)的調(diào)整者春；
二、查找要?jiǎng)h除的節(jié)點(diǎn)
給定一個(gè)節(jié)點(diǎn)key 或 value清女，根據(jù)紅黑樹(shù)的特點(diǎn)：
- 所有左子樹(shù)上的節(jié)點(diǎn)值一定小于根節(jié)點(diǎn)的值钱烟；
- 所有右子樹(shù)上的節(jié)點(diǎn)值一定大于根節(jié)點(diǎn)的值；
那么，我們就可以通過(guò)二分法拴袭，來(lái)快速查找我們要?jiǎng)h除的節(jié)點(diǎn)的 key 或 value读第。
public class RBTree {
/*******************************************************************************************************************
* 刪除指定結(jié)點(diǎn)
*******************************************************************************************************************/
public void remove(int value) {
if (root == null) {
return;
}
/**************************************************************************************
* 二分法，先查找需要?jiǎng)h除的節(jié)點(diǎn)
**************************************************************************************/
TreeNode p = root;
while (p != null) {
if (p.value == value) {
break;
} else if (p.value > value) {
p = p.left;
} else {
p = p.right;
}
}
// 沒(méi)有找到指定值的節(jié)點(diǎn)
if (p == null) {
return;
}
// 查找可以替換刪除的節(jié)點(diǎn)
......
// 調(diào)整紅黑樹(shù)
......
}
}
三拥刻、查找可替換刪除的節(jié)點(diǎn)
如下圖怜瞒，我們要?jiǎng)h除值為5的節(jié)點(diǎn)：
image.png
如果我們直接刪除節(jié)點(diǎn)5，那么就要選擇節(jié)點(diǎn)2 或者 節(jié)點(diǎn)8為新的根節(jié)點(diǎn)（取代節(jié)點(diǎn)5這個(gè)根般哼，不是整個(gè) RBT 的根）吴汪，無(wú)論選擇哪個(gè)節(jié)點(diǎn)為新根節(jié)點(diǎn)，都會(huì)不滿足紅黑樹(shù)的第5點(diǎn)蒸眠，從 RBT 的根到任意葉子節(jié)點(diǎn)漾橙，其路徑上的黑色節(jié)點(diǎn)數(shù)相同。
那么楞卡，我們就沒(méi)有好的辦法了么霜运？
辦法肯定是有的，而且還有兩種辦法蒋腮，當(dāng)然淘捡，實(shí)際上只是一種方法，只是采取的策略不同而已池摧！
首先焦除，我們發(fā)現(xiàn)，比5次小的數(shù)是節(jié)點(diǎn)2的右節(jié)點(diǎn)险绘，而比5次大的數(shù)是節(jié)點(diǎn)8的左節(jié)點(diǎn)踢京，因此，我們可以選舉節(jié)點(diǎn)3或節(jié)點(diǎn)6來(lái)成為新的節(jié)點(diǎn)宦棺，我們看看分別選用新的節(jié)點(diǎn)后，紅黑樹(shù)的結(jié)果如何黔帕？
前驅(qū)or后繼.png
我們發(fā)現(xiàn)代咸，無(wú)論是采用『前驅(qū)選舉法』還是『后繼選舉法』選舉出的新根節(jié)點(diǎn)，來(lái)取代老節(jié)點(diǎn)成黄，都滿足紅黑樹(shù)的5條要求呐芥，而且不用調(diào)整（后文中會(huì)講道哪些情況下不用調(diào)整，哪些情況下需要調(diào)整）奋岁。
那么前驅(qū)與后繼是如何實(shí)現(xiàn)的思瘟，又有什么要求？
- 被刪除的節(jié)點(diǎn)只要存在兒子節(jié)點(diǎn)：
a. 如果左兒子存在闻伶，則先定位到其左兒子節(jié)點(diǎn)滨攻，然后不斷的定位到右兒子節(jié)點(diǎn)，直到下一個(gè)右兒子節(jié)點(diǎn)為NULL；
a. 同理光绕，右兒子存在女嘲，則先定位到其右兒子節(jié)點(diǎn)，再不斷定位左兒子節(jié)點(diǎn)诞帐，直到下一個(gè)左兒子節(jié)點(diǎn)為NULL欣尼；
c. 對(duì)于 a 或者 b，只需要將最右或最左節(jié)點(diǎn)的值賦值給被刪除的節(jié)點(diǎn)停蕉，然后將刪除的指向指到最右或最左子節(jié)點(diǎn)愕鼓；
d. 對(duì)于最右或最左，可能也存在兒子慧起，因此菇晃，繼續(xù)執(zhí)行第 1 點(diǎn)，谋旦；
e. 如果最右或最左沒(méi)有兒子，則執(zhí)行第 2 點(diǎn)屈尼； - 如果兩個(gè)兒子都不存在册着，則查看下節(jié)內(nèi)容；
-
遞歸查找替換節(jié)點(diǎn)（后繼）：
紅黑樹(shù)的刪除遞歸.png
查找前驅(qū)或后繼節(jié)點(diǎn)脾歧，并替換刪除節(jié)點(diǎn)的值（若有兩個(gè)兒子甲捏，先前驅(qū)還是先后繼都可以）
public class RBTree {
public void remove(int value) {
// 二分法查找待刪除的節(jié)點(diǎn)
......
// 查找可以替換刪除的節(jié)點(diǎn)
p = findPreOrNextNode(p);
// 調(diào)整紅黑樹(shù)
......
}
/*******************************************************************************************************************
* 查找后繼或前驅(qū)節(jié)點(diǎn)，最終轉(zhuǎn)化為刪除（含有一個(gè) or 零個(gè)）的子節(jié)點(diǎn)
* 【返回最終要?jiǎng)h除的子節(jié)點(diǎn)】
*******************************************************************************************************************/
private TreeNode findPreOrNextNode(TreeNode p) {
if (p.left != null || p.right != null) {
// g 為指向刪除的節(jié)點(diǎn)
TreeNode g = p;
/**********************************************************************************
* 查找
* 1. 后繼：僅比待刪除節(jié)點(diǎn)次大的節(jié)點(diǎn)
* or
* 2. 前驅(qū)：僅比待刪除節(jié)點(diǎn)次小的節(jié)點(diǎn)
**********************************************************************************/
if (p.right != null) {
// 查找后繼節(jié)點(diǎn)
p = p.right;
while (p.left != null) {
p = p.left;
}
} else {
// 查找前驅(qū)節(jié)點(diǎn)
p = p.left;
while (p.right != null) {
p = p.right;
}
}
/**********************************************************************************
* 交換【待刪除節(jié)點(diǎn)】與【后繼/前驅(qū)】的值鞭执，改為刪除【后繼/前驅(qū)】節(jié)點(diǎn)
**********************************************************************************/
g.value = p.value;
p = findPreOrNextNode(p);
} else {
/**********************************************************************************
* 待刪除節(jié)點(diǎn)沒(méi)有左司顿、右兒子，就是刪除自己
**********************************************************************************/
}
return p;
}
}
四兄纺、調(diào)整紅黑樹(shù)
如果兩個(gè)兒子都不存在大溜，則需要考慮被刪除節(jié)點(diǎn)的顏色（右節(jié)點(diǎn)同理估脆，只是條件相左）：
- 如果是紅色钦奋，則直接刪除，不用后續(xù)調(diào)整疙赠；
- 如果是黑色付材，則需要考慮其兄弟節(jié)點(diǎn)顏色，以及兄弟節(jié)點(diǎn)的兒子情況：
如果兄弟節(jié)點(diǎn)是紅色圃阳，則要滿足紅黑樹(shù)第5點(diǎn)厌衔，兄弟節(jié)點(diǎn)必有兩個(gè)黑色的兒子，則修改兄弟節(jié)點(diǎn)的左兒子為紅色捍岳，兄弟節(jié)點(diǎn)為黑色富寿，對(duì)父節(jié)點(diǎn)左旋睬隶，調(diào)整完畢；
如果兄弟節(jié)點(diǎn)是黑色（如果有兒子作喘，則一定是紅色理疙，黑色則不滿足紅黑樹(shù)第5點(diǎn)）：
兄弟節(jié)點(diǎn)有一個(gè)右兒子：將父節(jié)點(diǎn)顏色給兄弟節(jié)點(diǎn)，修改父節(jié)點(diǎn)和兄弟右兒子節(jié)點(diǎn)為紅色泞坦，對(duì)父節(jié)點(diǎn)左旋窖贤，調(diào)整完畢；
兄弟節(jié)點(diǎn)有一個(gè)左兒子贰锁，互換兄弟與其左兒子節(jié)點(diǎn)顏色赃梧，對(duì)兄弟節(jié)點(diǎn)右旋，此時(shí)和 2.b.i 一樣豌熄，執(zhí)行即可授嘀；
兄弟節(jié)點(diǎn)沒(méi)有兒子芯肤，因?yàn)閯h除的節(jié)點(diǎn)為黑色巷折，為了動(dòng)態(tài)平衡，直接修改兄弟節(jié)點(diǎn)的顏色為紅色崖咨，但此時(shí)可能不滿足紅黑樹(shù)第4點(diǎn)（父節(jié)點(diǎn)可能是紅色）锻拘，因此，將待調(diào)整節(jié)點(diǎn)指為父節(jié)點(diǎn)击蹲，繼續(xù)執(zhí)行第 2 點(diǎn)署拟；
先假設(shè)各節(jié)點(diǎn)的名稱：
- X為待刪除節(jié)點(diǎn)；
- P為父節(jié)點(diǎn)歌豺；
- B為兄弟節(jié)點(diǎn)推穷；
- BL為兄弟節(jié)點(diǎn)的左節(jié)點(diǎn)；
- BR為兄弟節(jié)點(diǎn)的右節(jié)點(diǎn)类咧；
下面將對(duì)第 2 點(diǎn)中的 5 種情況用圖來(lái)直觀的分析：
-
2.a：X = 黑色缨恒，B = 紅色，BL = 黑色轮听，BR = 黑色
2.a.png 2.b.i：X = 黑色，B = 黑色岭佳，BR = 紅色
2.b.ii：X = 黑色血巍，B = 黑色，BL = 紅色
-
2.b.iii：X = 黑色珊随，B = 黑色述寡，BL = 紅色柿隙，BR = 紅色
2.b.i-iii.png -
2.b.iv：X = 黑色，B = 黑色
2.b.iv.png 刪除結(jié)點(diǎn)后的檢查或調(diào)整：
public class RBTree {
public void remove(int value) {
// 二分法查找待刪除的節(jié)點(diǎn)
......
// 查找可以替換刪除的節(jié)點(diǎn)
......
// 調(diào)整紅黑樹(shù)鲫凶，并將 X 節(jié)點(diǎn)移除
fixedRemove(p);
if (p == p.parent.left) {
p.parent.left = null;
} else {
p.parent.right = null;
}
}
/*******************************************************************************************************************
* cur為新的刪除節(jié)點(diǎn)禀崖，需要考慮：
* 1、cur 沒(méi)有兒子：
* 1.1螟炫、cur 為紅色節(jié)點(diǎn)波附，則直接刪除；
* 1.2昼钻、cur 為黑色節(jié)點(diǎn)掸屡，需要考慮其兄弟節(jié)點(diǎn)；
* 2然评、cur 有一個(gè)兒子：
* 2.1仅财、交互 cur 與其兒子節(jié)點(diǎn)的值，改為刪除兒子節(jié)點(diǎn)碗淌；
* 2.2盏求、重復(fù)第1步；
* 3亿眠、cur 不可能有兩個(gè)兒子：
* 3.1碎罚、根據(jù) remove，cur 要么為后繼缕探、要么為前驅(qū)魂莫、要么沒(méi)有兒子；
* 3.2爹耗、所以只存在上述1耙考、2；
* 3.3潭兽、且第2步最終也轉(zhuǎn)化為第1步需要考慮的 1.1 或 1.2 情況倦始；
*******************************************************************************************************************/
private void fixedRemove(TreeNode cur) {
while (cur != root && cur.color == TreeNode.BLACK) {
/***********************************************************************************************************
* cur 為待刪除節(jié)點(diǎn)
* b 為兄弟節(jié)點(diǎn)
* p 為父節(jié)點(diǎn)
*
* 【以下分析基于 cur 為左節(jié)點(diǎn)，若為右節(jié)點(diǎn)山卦，則條件相反】
* 因?yàn)?cur 節(jié)點(diǎn)存在且為黑色鞋邑，所以，其兄弟節(jié)點(diǎn)一定存在：
*
* 1账蓉、若 b 節(jié)點(diǎn)為紅色枚碗，則滿足紅黑樹(shù)條件的情況下，b 的兒子節(jié)點(diǎn)一定存在铸本，且有兩個(gè)為黑色的兒子：
* 設(shè) b 左兒子為紅色肮雨，b 為黑色，對(duì) p 向左旋轉(zhuǎn)箱玷；
*
* 2怨规、若 b 節(jié)點(diǎn)為黑色：
* 2.1陌宿、b 有一個(gè)右兒子（一定是紅色），將 p 的顏色給 b波丰，p 和 b 的右兒子設(shè)為黑色壳坪，對(duì) p 向左旋轉(zhuǎn)；
* 2.2掰烟、b 有一個(gè)左兒子（一定是紅色）爽蝴，將兒子設(shè)為黑色，b設(shè)為紅色媚赖，b 是右節(jié)點(diǎn)霜瘪，對(duì) b 向右旋轉(zhuǎn)；（此時(shí)情況同 2.1）
* 2.3惧磺、b 有兩個(gè)兒子（一定是紅色）颖对，此時(shí)，處理同 2.1磨隘；
*
* 2.4缤底、b 沒(méi)有兒子，則設(shè) b 為紅色番捂，cur 指向 p个唧，繼續(xù)向上遞歸至根節(jié)點(diǎn)，或遇到紅色節(jié)點(diǎn)為止设预；
* 之所以要向上遞歸徙歼，是因?yàn)?p 可紅可黑，b 從黑色改變?yōu)榧t色鳖枕，此時(shí)就少了一個(gè)黑色節(jié)點(diǎn)魄梯，條件5可能不滿足，
* 需要檢查 p 節(jié)點(diǎn)顏色及其兄弟宾符；
***********************************************************************************************************/
TreeNode p = cur.parent;
TreeNode b;
if (cur == p.left) {
/*********************************************************************************
* 待刪除節(jié)點(diǎn)為左節(jié)點(diǎn)
*********************************************************************************/
b = p.right;
// 1
if (b.color == TreeNode.RED) {
b.left.color = TreeNode.RED;
b.color = TreeNode.BLACK;
rotateLeft(p);
break;
}
// 2.4
if (b.left == null && b.right == null) {
b.color = TreeNode.RED;
cur = p;
continue;
}
// 2.2
if (b.left != null && b.right == null) {
b.left.color = TreeNode.BLACK;
b.color = TreeNode.RED;
rotateRight(b);
}
// 2.1酿秸、2.3 以及 2.2 -> 2.1
b.color = p.color;
p.color = b.right.color = TreeNode.BLACK;
rotateLeft(p);
break;
} else {
/******************************************************************************
* 待刪除節(jié)點(diǎn)為右節(jié)點(diǎn)
******************************************************************************/
b = p.left;
// 1
if (b.color == TreeNode.RED) {
b.right.color = TreeNode.RED;
b.color = TreeNode.BLACK;
rotateLeft(p);
break;
}
// 2.4
if (b.left == null && b.right == null) {
b.color = TreeNode.RED;
cur = p;
continue;
}
// 2.2
if (b.right != null && b.left == null) {
b.right.color = TreeNode.BLACK;
b.color = TreeNode.RED;
rotateLeft(b);
}
// 2.1、2.3 以及 2.2 -> 2.1
b.color = p.color;
p.color = b.left.color = TreeNode.BLACK;
rotateRight(p);
break;
}
}
// 可能是2.4退出魏烫，將 p 節(jié)點(diǎn)強(qiáng)制黑色辣苏，以實(shí)現(xiàn)動(dòng)態(tài)平衡
cur.color = TreeNode.BLACK;
}
}
五、測(cè)試及結(jié)果
public class Main {
public static void main(String[] args) {
rbTree();
}
private static void rbTree() {
int[] values = new int[]{
12, 1, 9, 2, 0, 11, 7, 19, 4, 15, 18, 5, 14, 13, 10, 16, 6, 3, 8, 17
};
RBTree tree = new RBTree(null);
// 保持輸出與【https://www.cs.usfca.edu/~galles/visualization/RedBlack.html】一致的效果
// 優(yōu)先前驅(qū)
tree.setLeftFirst(true);
for (int value : values) {
tree.insert(value);
}
tree.doPreTravel();
tree.remove(14);
tree.doPreTravel();
}
}
-
完全插入完的RBT
完整的RBT.png -
刪除節(jié)點(diǎn)14后的RBT
刪除節(jié)點(diǎn)14后的RBT.png
