資料結構:紅黑樹
- 1. 紅黑樹的演變
- 2. 紅黑樹的性質
- 3. 紅黑樹的實作
-
- 3.1 HashMap中的紅黑樹
-
- 3.1.1 TreeNode的結構
- 3.1.2 treeify() & untreeify()
- 3.1.3 split()
- 3.1 左旋與右旋
- 3.2 紅黑樹的插入
- 3.3 紅黑樹的删除
1. 紅黑樹的演變
此部分的思想來自于Sedgewick的《 算法[第四版] 》。參考部落格：
https://blog.csdn.net/chen_zhang_yu/article/details/52415077
紅黑樹的起源是二叉查找樹，二叉查找樹從根節點開始，左子節點小于它，右子節點大于它。每個節點都符合這個特性，是以易于查找，是一種很好的資料結構。但是它有一個問題，就是容易偏向某一側，這樣就像一個連結清單結構了，失去了樹結構的優點。
2-3樹是二叉查找樹的變種，樹中的2和3代表兩種節點，以下表示為2-節點和3-節點。
- 2-節點即普通節點：包含一個元素，兩條子連結。
- 3-節點則是擴充版，包含2個元素和三條連結：兩個元素A、B，左邊的連結指向小于A的節點，中間的連結指向介于A、B值之間的節點，右邊的連結指向大于B的節點。
一顆完美平衡的2-3查找樹中的所有空連結到根結點的距離都是相同的。
下面來看2-3樹的構造過程，和标準的二叉查找樹由上向下生長不同，2-3樹的生長是由下向上的。
- 如果将值插入一個2-節點，則将2-節點擴充為一個3-節點。
- 如果将值插入一個3-節點，分為以下幾種情況。
- 3-節點沒有父節點，即整棵樹就隻有它一個三節點。此時，将3-節點擴充為一個4-節點，即包含三個元素的節點，然後将其分解，變成一棵二叉樹。
[Java集合]Map源碼分析：HashMap紅黑樹解析1. 紅黑樹的演變2. 紅黑樹的性質3. 紅黑樹的實作 - 3-節點有一個2-節點的父節點，此時的操作是，3-節點擴充為4-節點，然後分解4-節點，然後将分解後的新樹的父節點融入到2-節點的父節點中去
[Java集合]Map源碼分析：HashMap紅黑樹解析1. 紅黑樹的演變2. 紅黑樹的性質3. 紅黑樹的實作 -
3-節點有一個3-節點的父節點，此時操作是：3-節點擴充為4-節點，然後分解4-節點，新樹父節點向上融合，上面的3-節點繼續擴充，融合，分解，新樹繼續向上融合，直到父節點為2-節點為止，如果向上到根節點都是3-節點，将根節點擴充為4-節點，然後分解為新樹，至此，整個樹增加一層，仍然保持平衡。
将{7,8,9,10,11,12}中的數值依次插入2-3樹，畫出它的過程：
[Java集合]Map源碼分析：HashMap紅黑樹解析1. 紅黑樹的演變2. 紅黑樹的性質3. 紅黑樹的實作
将這種直白的表述寫成代碼實作起來并不友善，因為要處理的情況太多。這樣需要維護兩種不同類型的節點，将連結和其他資訊從一個節點複制到另一個節點，将節點從一種類型轉換為另一種類型等等。
是以，紅黑樹出現了，紅黑樹的背後邏輯就是2-3樹。但是由于用紅黑作為标記這個小技巧，最後實作的代碼量并不大。
我們來看看紅黑樹和2-3樹的關聯，首先是紅和黑的含義。紅黑樹中，所有的節點都是标準的2-節點，為了展現出3-節點，這裡将3-節點的兩個元素用左斜紅色的連結連接配接起來，即連接配接了兩個2-節點來表示一個3-節點。這裡紅色節點标記就代表指向其的連結是紅連結，黑色标記的節點就是普通的節點。紅色節點是可以與其父節點合并為一個3-節點的，紅黑樹實作的其實是一個完美的黑色平衡，如果你将紅黑樹中所有的紅色連結放平，那麼它所有的葉子節點到根節點的距離都是相同的。是以它并不是一個嚴格的平衡二叉樹，但是它的綜合性能已經很優秀了。
紅連結放平：
是以，紅黑樹的一種定義是滿足下列條件的二叉查找樹：
- 紅連結均為左連結。
- 沒有任何一個結點同時和兩條紅連結相連。(這樣會出現4-節點)
- 該樹是完美黑色平衡的，即任意空連結到根結點的路徑上的黑連結數量相同。
注意：該定義來自Sedgewick的《 算法[第四版] 》，這裡的紅黑樹為左傾紅黑樹，Java實作的紅黑樹中，左右連結均可為紅連結（可與2-3-4樹對應）。
2. 紅黑樹的性質
《算法導論》對R-B Tree的介紹：
紅黑樹，一種二叉查找樹，但在每個結點上增加一個存儲位表示結點的顔色，可以是Red或Black。
通過對任何一條從根到葉子的路徑上各個結點着色方式的限制，紅黑樹確定沒有一條路徑會比其
他路徑長出倆倍，因而是接近平衡的。
紅黑樹，滿足以下性質（即隻有滿足以下全部性質的樹，我們才稱之為紅黑樹）：
1）每個結點要麼是紅的，要麼是黑的。
2）根結點是黑的。
3）每個葉結點，即空結點（NIL）是黑的。
4）如果一個結點是紅的，那麼它的倆個兒子都是黑的。
5）對每個結點，從該結點到其子孫結點的所有路徑上包含相同數目的黑結點。
3. 紅黑樹的實作
動畫模拟網站：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
3.1 HashMap中的紅黑樹
3.1.1 TreeNode的結構
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
//省略後續代碼
TreeNode繼承自LinkedHashMap中的内部類——LinkedHashMap.Entry，而這個内部類又繼承自Node。我們再來看看它的幾個屬性，parent用來指向它的父節點，left指向左孩子，right指向右孩子，prev則指向前一個節點（原連結清單中的前一個節點），注意，這些字段跟Entry，Node中的字段一樣，是使用預設通路權限的，是以子類可以直接使用父類的屬性。
3.1.2 treeify() & untreeify()
/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
//這裡其實是将單連結清單轉化成了雙向連結清單，tl是p的前驅，每次循環更新指向雙連結清單的最後一個元素，用來和p相連，p是目前節點
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
在treeifyBin函數中，先将所有節點替換為TreeNode，然後再将單連結清單轉為雙連結清單，友善之後的周遊和移動操作。而最終的操作，實際上是調用TreeNode的方法treeify進行的。
final void treeify(Node<K,V>[] tab) {
//樹的根節點
TreeNode<K,V> root = null;
//x是目前節點，next是後繼
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
//如果根節點為null，把目前節點設定為根節點
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
//這裡循環周遊，進行二叉搜尋樹的插入
for (TreeNode<K,V> p = root;;) {
//p指向周遊中的目前節點，x為待插入節點，k是x的key，h是x的hash值，ph是p的hash值，dir用來訓示x節點與p的比較，-1表示比p小，1表示比p大，不存在相等情況，因為HashMap中是不存在兩個key完全一緻的情況。
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
//如果hash值相等，那麼判斷k是否實作了comparable接口，如果實作了comparable接口就使用compareTo進行進行比較，如果仍舊相等或者沒有實作comparable接口，則在tieBreakOrder中比較
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
//進行插入平衡處理
root = balanceInsertion(root, x);
break;
}
}
}
}
//確定給定節點是桶中的第一個元素
moveRootToFront(tab, root);
}
//這裡不是為了整體排序，而是為了在插入中保持一緻的順序
static int tieBreakOrder(Object a, Object b) {
int d;
//用兩者的類名進行比較，如果相同則使用對象預設的hashcode進行比較
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
循環周遊目前樹，然後找到可以該節點可以插入的位置，依次和周遊節點比較，比它大則跟其右孩子比較，小則與其左孩子比較，依次周遊，直到找到左孩子或者右孩子為null的位置進行插入。
moveRootToFront()函數是将root節點移動到桶中的第一個元素，也就是連結清單的首節點，這樣做是因為在判斷桶中元素類型的時候會對連結清單進行周遊，将根節點移動到連結清單前端可以確定類型判斷時不會出現錯誤。
/**
* 把給定節點設為桶中的第一個元素
*/
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
int index = (n - 1) & root.hash;
//first指向連結清單第一個節點
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
if (root != first) {
//如果root不是第一個節點，則将root放到第一個首節點位置
Node<K,V> rn;
tab[index] = root;
TreeNode<K,V> rp = root.prev;
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
//這裡是防禦性程式設計，校驗更改後的結構是否滿足紅黑樹和雙連結清單的特性
//因為HashMap并沒有做并發安全處理，可能在并發場景中意外破壞了結構
assert checkInvariants(root);
}
}
untreeify()源碼：
/**
* Returns a list of non-TreeNodes replacing those linked from
* this node.
*/
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
for (Node<K,V> q = this; q != null; q = q.next) {
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
3.1.3 split()
/**
* Splits nodes in a tree bin into lower and upper tree bins,
* or untreeifies if now too small. Called only from resize;
* see above discussion about split bits and indices.
*
* @param map the map
* @param tab the table for recording bin heads
* @param index the index of the table being split
* @param bit the bit of hash to split on
*/
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
3.1 左旋與右旋
左旋：左旋結點E，就是讓E去做它的右孩子（S）的左孩子，如果S有左孩子，則讓這個左孩子去做E的右孩子。
右旋：左旋結點S，就是讓S去做它的左孩子（E）的右孩子，如果E有右孩子，則讓這個右孩子去做S的左孩子。
左旋的代碼實作：
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> r, pp, rl;
if (p != null && (r = p.right) != null) {//如果p不為空且p有右孩子r
if ((rl = p.right = r.left) != null)//如果r的左孩子不為空，讓他去做p的右孩子
rl.parent = p;
if ((pp = r.parent = p.parent) == null)//讓p的父親做r的父親，如果p的父親為空
(root = r).red = false;//r為根節點，變黑
else if (pp.left == p)//如果p是左孩子
pp.left = r;
else//如果p是右孩子
pp.right = r;
r.left = p;//将p置為r的左孩子
p.parent = r;//将r置為p的父親
}
return root;
}
右旋的代碼實作：
//與左旋類似，不做分析
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> l, pp, lr;
if (p != null && (l = p.left) != null) {
if ((lr = p.left = l.right) != null)
lr.parent = p;
if ((pp = l.parent = p.parent) == null)
(root = l).red = false;
else if (pp.right == p)
pp.right = l;
else
pp.left = l;
l.right = p;
p.parent = l;
}
return root;
}
3.2 紅黑樹的插入
插入分如下幾種情況：
- 插入的為根節點，則直接把顔色改成黑色即可。
- 插入的節點的父節點是黑色節點，則不需要調整，因為插入的節點會初始化為紅色節點，紅色節點是不會影響樹的平衡的。
- 插入的節點的祖父節點為null，即插入的節點的父節點是根節點，直接插入即可（因為根節點肯定是黑色）。
-
插入的節點父節點和祖父節點都存在，并且其父節點是祖父節點的左節點。這種情況稍微麻煩一點，又分兩種子情況：
i. 插入節點的叔叔節點是紅色，則将父親節點和叔叔節點都改成黑色，然後祖父節點改成紅色即可。
ii. 插入節點的叔叔節點是黑色或不存在：
a.若插入節點是其父節點的右孩子，則将其父節點左旋，
b.若為左孩子，則将其父節點變成黑色節點，将其祖父節點變成紅色節點，然後将其祖父節點右旋。
-
插入的節點父節點和祖父節點都存在，并且其父節點是祖父節點的右節點。這種情況跟上面是類似的，分兩種子情況：
i.插入節點的叔叔節點是紅色，則将父親節點和叔叔節點都改成黑色，然後祖父節點改成紅色即可。
ii.插入節點的叔叔節點是黑色或不存在：
a.若插入節點是其父節點的左孩子，則将其父節點右旋
b.若為右孩子，則将其父節點變成黑色節點，将其祖父節點變成紅色節點，然後将其祖父節點左旋。
重複進行上述操作，直到變成1或2情況時則結束變換。下面從無到有建構一顆紅黑樹，假設插入的順序為：10，5，9，3，6，7，19，32，24，17。
首先10，為情景1，直接改成黑色即可，再插入5，為情景2，比10小，放到10的左孩子位置，插入9，比10小，但是比5大，放到5的右孩子位置，此時，為情景4iia，左旋後變成了情景4iib，變色右旋即可完成轉化。插入3後為情景4i，将父節點和叔叔節點同時變色即可，插入6不需要調整，插入7後為情景5i，變色即可。插入19不需要調整，插入32，變成了5iib，左旋變色即可，插入24，變成5iia，右旋後變成5i，變色即可，最後插入17。
插入的代碼實作：
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
x.red = true;
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
//情景1：父節點為null
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
//情景2，3：父節點是黑色節點或者祖父節點為null
else if (!xp.red || (xpp = xp.parent) == null)
return root;
//情景4：插入的節點父節點和祖父節點都存在，并且其父節點是祖父節點的左節點
if (xp == (xppl = xpp.left)) {
//情景4i：插入節點的叔叔節點是紅色
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
//情景4ii：插入節點的叔叔節點是黑色或不存在
else {
//情景4iia：插入節點是其父節點的右孩子
if (x == xp.right) {
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//情景4iib：插入節點是其父節點的左孩子
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateRight(root, xpp);
}
}
}
}
//情景5：插入的節點父節點和祖父節點都存在，并且其父節點是祖父節點的右節點
else {
//情景5i：插入節點的叔叔節點是紅色
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
//情景5ii：插入節點的叔叔節點是黑色或不存在
else {
· //情景5iia：插入節點是其父節點的左孩子
if (x == xp.left) {
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//情景5iib：插入節點是其父節點的右孩子
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}
3.3 紅黑樹的删除
這裡分為兩部分内容：1.二叉搜尋樹的删除，2.紅黑樹的删除調整。
二叉搜尋樹的删除主要有這麼幾種情景：
- 待删除的節點無左右孩子。
- 待删除的節點隻有左孩子或者右孩子。
- 待删除的節點既有左孩子又有右孩子。
對于情景1，直接删除即可，情景2，則直接把該節點的父節點指向它的左孩子或者右孩子即可，情景3稍微複雜一點，需要先找到其右子樹的最左孩子（或者左子樹的最右孩子），即左（右）子樹中序周遊時的第一個節點，然後将其與待删除的節點互換，最後再删除該節點（如果有右子樹，則右子樹上位）。總之，就是先找到它的替代者，找到之後替換這個要删除的節點，然後再把這個節點真正删除掉。
删除完之後，如果替代者是紅色節點，則不需要調整，如果是黑色節點，則會導緻左子樹和右子樹路徑中黑色節點數量不一緻，需要進行紅黑樹的調整，跟上面一樣，替代節點為其父節點的左孩子與右孩子的情況類似，是以這裡隻說其為左孩子的情景（PS:上一步的尋找替換節點使用的是右子樹的最左節點，是以該節點如果有孩子，隻能是右孩子）：
情景1：隻有右孩子且為紅色，直接用右孩子替換該節點然後變成黑色即可。
情景2：隻有右孩子且為黑色，那麼删除該節點會導緻父節點的左子樹路徑上黑色節點減一，此時隻能去借助右子樹，從右子樹中借一個紅色節點過來即可，具體取決于右子樹的情況，這裡又分成兩種：
i.兄弟節點是紅色，則此時父節點是黑色，且兄弟節點肯定有兩個孩子，且兄弟節點的左右子樹路徑上均有兩個黑色節點，此時隻需将兄弟節點與父節點顔色互換，然後将父節點左旋，左旋後，兄弟節點的左子樹SL挂到了父節點p的右孩子位置，這時會導緻p的右子樹路徑上的黑色節點比左子樹多一，此時再SL置為紅色即可。
ii.兄弟節點是黑色，那麼就隻能打它孩子的主意了，這裡主要關注遠侄子（兄弟節點的右孩子，即SR）的顔色情況，這裡分成兩種情況：
a.遠侄子SR是黑色，近侄子任意（白色代表顔色可為任意顔色），則先将S轉為紅色，然後右旋，再将SL換成P節點顔色，P塗成黑色，S也塗成黑色，再進行左旋即可。其實簡單說就是SL上位，替換父節點位置。
b.遠侄子SR為紅色，近侄子任意（該子樹路徑中有且僅有一個黑色節點），則先将兄弟節點與父節點顔色互換，将SR塗成黑色，再将父節點左旋即可。
删除的代碼實作：
- 二叉搜尋樹的删除，
/**
* Removes the given node, that must be present before this call.
* This is messier than typical red-black deletion code because we
* cannot swap the contents of an interior node with a leaf
* successor that is pinned by "next" pointers that are accessible
* independently during traversal. So instead we swap the tree
* linkages. If the current tree appears to have too few nodes,
* the bin is converted back to a plain bin. (The test triggers
* somewhere between 2 and 6 nodes, depending on tree structure).
*/
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, boolean movable) {
int n;
if (tab == null || (n = tab.length) == 0)
return;
int index = (n - 1) & hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
if (pred == null)
tab[index] = first = succ;
else
pred.next = succ;
if (succ != null)
succ.prev = pred;
if (first == null)
return;
if (root.parent != null)
root = root.root();
if (root == null || root.right == null ||
(rl = root.left) == null || rl.left == null) {
tab[index] = first.untreeify(map); // too small
return;
}
TreeNode<K,V> p = this, pl = left, pr = right, replacement;
if (pl != null && pr != null) {
TreeNode<K,V> s = pr, sl;
while ((sl = s.left) != null) // find successor
s = sl;
boolean c = s.red; s.red = p.red; p.red = c; // swap colors
TreeNode<K,V> sr = s.right;
TreeNode<K,V> pp = p.parent;
if (s == pr) { // p was s's direct parent
p.parent = s;
s.right = p;
}
else {
TreeNode<K,V> sp = s.parent;
if ((p.parent = sp) != null) {
if (s == sp.left)
sp.left = p;
else
sp.right = p;
}
if ((s.right = pr) != null)
pr.parent = s;
}
p.left = null;
if ((p.right = sr) != null)
sr.parent = p;
if ((s.left = pl) != null)
pl.parent = s;
if ((s.parent = pp) == null)
root = s;
else if (p == pp.left)
pp.left = s;
else
pp.right = s;
if (sr != null)
replacement = sr;
else
replacement = p;
}
else if (pl != null)
replacement = pl;
else if (pr != null)
replacement = pr;
else
replacement = p;
//p是待删除節點，replacement用于後續的紅黑樹調整，指向的是p或者p的繼承者。
//如果p是葉子節點，p==replacement，否則replacement為p的右子樹中最左節點
if (replacement != p) {
//若p不是葉子節點，則讓replacement的父節點指向p的父節點
TreeNode<K,V> pp = replacement.parent = p.parent;
if (pp == null)
root = replacement;
else if (p == pp.left)
pp.left = replacement;
else
pp.right = replacement;
p.left = p.right = p.parent = null;
}
//若待删除的節點p時紅色的，則樹平衡未被破壞，無需進行調整。
//否則删除節點後需要進行調整
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
//p為葉子節點，則直接将p從樹中清除
if (replacement == p) { // detach
TreeNode<K,V> pp = p.parent;
p.parent = null;
if (pp != null) {
if (p == pp.left)
pp.left = null;
else if (p == pp.right)
pp.right = null;
}
}
if (movable)
moveRootToFront(tab, r);
}
- 紅黑樹的删除調整。
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root, TreeNode<K,V> x) {
for (TreeNode<K,V> xp, xpl, xpr;;) {
//x為空或x為根節點，直接傳回
if (x == null || x == root)
return root;
//x為根節點，染成黑色，直接傳回（因為調整過後，root并不一定指向删除操作過後的根節點，如果之前删除的是root節點，則x将成為新的根節點）
else if ((xp = x.parent) == null) {
x.red = false;
return x;
}
//如果x為紅色，則無需調整，傳回
else if (x.red) {
x.red = false;
return root;
}
//x為其父節點的左孩子
else if ((xpl = xp.left) == x) {
//如果它有紅色的兄弟節點xpr，那麼它的父親節點xp一定是黑色節點
if ((xpr = xp.right) != null && xpr.red) {
xpr.red = false;
xp.red = true;
//對父節點xp做左旋轉
root = rotateLeft(root, xp);
//重新将xp指向x的父節點，xpr指向xp新的右孩子
xpr = (xp = x.parent) == null ? null : xp.right;
}
//如果xpr為空，則向上繼續調整，将x的父節點xp作為新的x繼續循環
if (xpr == null)
x = xp;
else {
//sl和sr分别為其近侄子和遠侄子
TreeNode<K,V> sl = xpr.left, sr = xpr.right;
if ((sr == null || !sr.red) &&
(sl == null || !sl.red)) {
xpr.red = true; //若sl和sr都為黑色或者不存在，即xpr沒有紅色孩子，則将xpr染紅
x = xp; //本輪結束，繼續向上循環
}
else {
//否則的話，就需要進一步調整
if (sr == null || !sr.red) {
if (sl != null) //若左孩子為紅，右孩子不存在或為黑
sl.red = false; //左孩子染黑
xpr.red = true; //将xpr染紅
root = rotateRight(root, xpr); //右旋
xpr = (xp = x.parent) == null ?
null : xp.right; //右旋後，xpr指向xp的新右孩子，即上一步中的sl
}
if (xpr != null) {
xpr.red = (xp == null) ? false : xp.red; //xpr染成跟父節點一緻的顔色，為後面父節點xp的左旋做準備
if ((sr = xpr.right) != null)
sr.red = false; //xpr新的右孩子染黑，防止出現兩個紅色相連
}
if (xp != null) {
xp.red = false; //将xp染黑，并對其左旋，這樣就能保證被删除的X所在的路徑又多了一個黑色節點，進而達到恢複平衡的目的
root = rotateLeft(root, xp);
}
//到此調整已經完畢，進入下一次循環後将直接退出
x = root;
}
}
}
//x為其父節點的右孩子，跟上面類似
else { // symmetric
if (xpl != null && xpl.red) {
xpl.red = false;
xp.red = true;
root = rotateRight(root, xp);
xpl = (xp = x.parent) == null ? null : xp.left;
}
if (xpl == null)
x = xp;
else {
TreeNode<K,V> sl = xpl.left, sr = xpl.right;
if ((sl == null || !sl.red) &&
(sr == null || !sr.red)) {
xpl.red = true;
x = xp;
}
else {
if (sl == null || !sl.red) {
if (sr != null)
sr.red = false;
xpl.red = true;
root = rotateLeft(root, xpl);
xpl = (xp = x.parent) == null ?
null : xp.left;
}
if (xpl != null) {
xpl.red = (xp == null) ? false : xp.red;
if ((sl = xpl.left) != null)
sl.red = false;
}
if (xp != null) {
xp.red = false;
root = rotateRight(root, xp);
}
x = root;
}
}
}
}
}