概念
- 紅黑樹是一種自平衡的二叉查找樹,是一種高效的查找樹.
- 紅黑樹具有良好的效率, 它可在O(logN)時間內完成查找,增加,刪除等操作.
注意: 下文中, 非紅色節點就是黑色節點, 即NULL節點是黑色節點
特徵
- 節點是紅色或黑色.
- 根節點是黑色.
- 每個葉子節點(NULL節點/空節點)是黑色
- .每個紅色節點的兩個孩子節點必須是黑色. (從葉子到根的所有路徑上不能有兩個連續的紅色節點)
- 從任意節點到其葉子節點的所有路徑都包含相同數目的黑色節點.
旋轉
當樹的結構發生改變時(添加/刪除元素時), 紅黑樹的五個特徵可能會被打破, 需要通過調整結構和顏色使樹重新滿足紅黑樹的特徵, 調整可以分為兩類:
- 顏色調整: 改變節點的顏色
- 結構調整: 左旋 + 右旋
左旋
左旋就是成為右孩子的左孩子節點.
左旋有以下三個步驟:
- 將旋轉節點的右節點的左節點關聯到旋轉節點的右節點上
- 將旋轉節點的父節點與旋轉節點的右節點進行關聯
- 將旋轉節點與旋轉節點的右節點進行關聯
左旋示例圖
對節點30進行左旋的過程如下:
參考TreeMap的左旋代碼
/** From CLR */private void rotateLeft(Entryp) {
// p為null就沒意思了
if (p != null) {
// 獲取p的右節點r, 臨時存儲
Entryr = p.right;
// 步驟1
// 1. 將p的右節點的左節點連接到p的右節點上
p.right = r.left;
// 2. 將p的右節點的左節點的父節點指向為p
if (r.left != null)
r.left.parent = p;
// 步驟2
// 1. 將p的父節點賦值給r, r的父節點指向為p的父節點
r.parent = p.parent;
// 2-1. 父節點為空, 根節點即為r
if (p.parent == null)
root = r;
// 2-2. 父節點不為空, 判斷p是父節點的左節點還是右節點, 然後進行關聯
else if (p.parent.left == p) // p是父節點的左節點
p.parent.left = r;
else // p是父節點的右節點
p.parent.right = r;
// 步驟3
r.left = p;
p.parent = r;
}}
右旋
右旋就是成為左孩子的右孩子節點.
右旋有以下三個步驟(與左旋相反):
- 將旋轉節點的左節點的右節點關聯到旋轉節點的左節點上
- 將旋轉節點的父節點與旋轉節點的左節點進行關聯
- 將旋轉節點與旋轉節點的左節點進行關聯
右旋示例圖:
對節點35進行右旋的過程如下:
參考TreeMap的右旋代碼:
/** From CLR */private void rotateRight(Entryp) {
// p為null就沒意思了
if (p != null) {
// 臨時存儲p的左節點
Entryl = p.left;
// 步驟1
p.left = l.right;
if (l.right != null)
l.right.parent = p;
// 步驟2
l.parent = p.parent;
if (p.parent == null)
root = l;
else if (p.parent.right == p)
p.parent.right = l;
else p.parent.left = l;
// 步驟3
l.right = p;
p.parent = l;
}}
尋找節點的後繼
當刪除一個節點時, 需要找一個後繼節點(也可以使用前驅, 這裡我們使用後繼)接替刪除節點的位置, 那麼如何尋找後繼節點呢?
參考TreeMap的尋找後繼代碼:
/**
* Returns the successor of the specified Entry, or null if no such.
*/staticTreeMap.Entry successor(Entry t) {
if (t == null) // null is null
return null;
else if (t.right != null) { // 右節點非空
// 循環尋找右節點的左節點的左節點..., 直到左節點的左節點為空, 返回.
Entryp = t.right;
while (p.left != null)
p = p.left;
return p;
} else { // 右節點非空
Entryp = t.parent; // 父節點
Entrych = t; // 當前節點
while (p != null && ch == p.right) { // 當前節點是否是父節點的右節點
ch = p; // 獲取父節點的引用
p = p.parent; // 父節點為祖父節點
}
// 如果當前節點不是父節點的右節點, 返回當前節點
return p;
}}
當然TreeMap中還有尋找節點的前驅的方法: Entry
實際上前驅後繼就是二叉樹中序遍歷時待刪除節點的前驅後繼.
插入
這裡主要說紅黑樹是如何進行新元素插入之後的調節, 來重新讓樹成為一顆紅黑樹.
插入的時候會出現以下四種情況:
- 情況1: 新節點(當前節點)為根節點
- 情況2: 新節點(當前節點)的父節點為黑色
- 情況3: 新節點(當前節點)的父節點為紅色 & 叔叔節點為紅色
- 情況4: 新節點(當前節點)的父節點為紅色 & 叔叔節點為黑色
下面分別說明各個情況時如何進行處理.
情況1: 新節點(當前節點)為根節點
直接將新節點(當前節點)染為黑色即可.
示例圖
在一棵空樹中插入節點20.
情況2: 新節點(當前節點)的父節點為黑色
父節點是黑色, 添加一個紅色孩子節點並不會影響紅黑樹的性質, 不需要調整.
示例圖
在一棵紅黑樹中插入節點33, 因為父節點是黑色, 所以不需要進行調整即可.
情況3: 新節點(當前節點)的父節點為紅色 & 叔叔節點為紅色
祖父節點一定為黑色.
處理步驟:
- 將父節點和叔叔節點染為黑色將祖父節點染為紅色將新節點(當前節點)指向為祖父節點
該情況與當前節點是父節點的左孩子還是右孩子無關, 因為不涉及旋轉.
這時新節點(當前節點)的顏色還是紅色, 可能出現四種情況:
- 情況1: 新節點(當前節點)為根節點
- 情況2: 新節點(當前節點)的父節點為黑色
- 情況3: 新節點(當前節點)的叔叔節點為紅色
- 情況4: 新節點(當前節點)的叔叔節點為黑色
然後再進入對應情況的處理方案中處理.
示例圖
在紅黑樹中插入節點8(X), 插入之後的紅黑樹如下:
很明顯違反了紅黑樹的性質5, 需要進行調整, 按照情況3的處理步驟進行調整, 調整之後的紅黑樹如下:
然後將當前節點(X)指向祖父節點, 繼續進行其它情況的調整.
情況4: 新節點(當前節點)的父節點為紅色 & 叔叔節點為黑色
處理步驟(父節點是祖父節點的左節點):
- 判斷新節點(當前節點)是否是父節點的右孩子節點(將當前節點調整為父節點的左孩子節點)
1 是: 新節點(當前節點)指向父節點, 然後對當前節點進行左旋
2 否: 不作處理
2. 將父節點染為黑色
3. 將祖父節點染為紅色
4. 對祖父節點進行右旋
處理步驟(父節點是祖父節點的右節點):
- 判斷新節點(當前節點)是否是父節點的左孩子節點(將當前節點調整為父節點的右孩子節點)
1 是: 新節點(當前節點)指向父節點, 然後對當前節點進行右旋
2 否: 不作處理
2. 將父節點染為黑色
3.將祖父節點染為紅色
4.對祖父節點進行左旋
以當前節點是父節點的左節點為例, 步驟1-1完成之後, 就變為當前節點是父節點的左孩子節點, 並且叔叔節點是黑色. 如果當前節點本就是父節點的左孩子節點, 則不進行處理, 直接進入步驟2.
這時新節點的的顏色還是紅色, 兄弟節點的顏色為紅色, 父節點為黑色, 可能出現四種情況:
- 情況1: 新節點(當前節點)為根節點
- 情況2: 新節點(當前節點)的父節點為黑色
- 情況3: 新節點(當前節點)的叔叔節點為紅色
- 情況4: 新節點(當前節點)的叔叔節點為黑色
然後再進入對應情況的處理方案中處理.
示例圖
繼續調整情況3中的紅黑樹:
按照情況4進行調整之後, 調整之後的紅黑樹如下:
調整完成.
插入總結
當新插入一個元素時, 先按照二叉排序樹的方法進行元素的插入, 之後將新元素的顏色染為紅色, 然後對樹進行調整, 使其重新成為紅黑樹.
參考TreeMap的插入調整代碼
/** From CLR */private void fixAfterInsertion(Entryx) {
// 默認新節點的顏色為紅色
x.color = RED;
// 父節點為黑色時, 增加一個紅色節點並不會影響紅黑樹
while (x != null && x != root && x.parent.color == RED) {
// 父節點為祖父節點的左節點
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
// 獲取叔叔節點
Entryy = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) { // 叔叔節點為紅色時
// 父節點和兄弟節點染為黑色
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
// 祖父節點染為紅色
setColor(parentOf(parentOf(x)), RED);
// 當前節點指向為祖父節點
x = parentOf(parentOf(x));
} else { // 叔叔節點為黑色時
// 判斷當前節點的左右
// 將當前節點調整為父節點的左節點
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
// 父節點染為黑色
setColor(parentOf(x), BLACK);
// 祖父節點染為紅色
setColor(parentOf(parentOf(x)), RED);
// 對祖父節點進行右旋
rotateRight(parentOf(parentOf(x)));
}
} else {
Entryy = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
// 最後將根節點染為黑色? 為什麼需要這段代碼, 我覺得你應該知道的.
root.color = BLACK;}
刪除
相對於插入, 紅黑樹的刪除操作要複雜的多, 不過我們拆解分析, 就簡單了, 把複雜問題拆解為小問題.
對於一顆紅黑樹, 其刪除節點的情況可以分為3種:
- 情況1: 節點既有左子樹又有右子樹
- 情況2: 節點只有左子樹或只有右子樹
- 情況3: 節點既沒有左子樹又沒有右子樹(葉子節點)
對於情況1, 我們首先要找到該節點的前驅或後繼節點, 使用前驅或後繼節點的值覆蓋待刪除節點的值, 然後將前驅或後繼節點按照情況2或情況3進行刪除即可. 前驅或者後繼節點頂多有一個子節點.
所以, 對於紅黑樹來說, 實際刪除節點的情況只有兩種(情況2和情況3).
情況2出現的情況
- 情況2-1: 待刪除節點為紅色
- 情況2-1-1: 待刪除節點的右孩子為黑色(不存在)
- 情況2-1-2: 待刪除節點的右孩子為紅色(不存在)
- 情況2-1-3: 待刪除節點的左孩子為黑色(不存在)
- 情況2-1-4: 待刪除節點的左孩子為紅色(不存在)
- 情況2-2: 待刪除節點為黑色
- 情況2-2-1: 待刪除節點的右孩子為黑色(不存在)
- 情況2-2-2: 待刪除節點的右孩子為紅色
- 情況2-2-3: 待刪除節點的左子樹為黑色(不存在)
- 情況2-2-4: 待刪除節點的左孩子為紅色
分析情況2, 只有情況2-2-2和情況2-2-4成立, 而這兩種情況下只需要把紅色節點刪除即可.
其它情況並不符合紅黑樹的特性, 所以根本不會存在其它情況的刪除.
情況2-2-2: 待刪除節點為黑色 & 待刪除節點的右孩子為紅色
處理步驟:
- 將其右孩子鏈接到其父節點上.將右孩子染為黑色即可.
這種情況就是普通的節點刪除操作
示例圖
在下圖紅黑樹中, 要刪除節點25
按照上述的處理步驟進行調整, 調整之後的紅黑樹如下:
直接把孩子節點染為黑色, 然後替換被刪除節點的位置即可.
情況2-2-2: 待刪除節點為黑色 & 待刪除節點的左孩子為紅色
處理步驟:
- 將其左孩子鏈接到其父節點上.將左孩子染為黑色即可.
這種情況就是普通的節點刪除操作.
示例圖
如同情況2-2-1的示例圖, 只不過孩子節點在左邊而已.
情況3出現的情況
- 情況3-1: 待刪除節點為黑色
- 情況3-1-1: 兄弟節點為紅色
- 情況3-1-2: 兄弟節點為黑色 & 兄弟節點的兩個孩子有一個為紅色
- 情況3-1-3: 兄弟節點為黑色 & 兄弟節點的兩個孩子都是黑色(包括NULL節點)
- 情況3-2: 待刪除節點為紅色
情況3-1-1: 待刪除節點為黑色 & 兄弟節點為紅色
處理步驟(待刪除節點是父節點的左孩子):
- 父節點染為紅色兄弟節點染為黑色對父節點進行左旋重新計算兄弟節點
處理步驟(待刪除節點是父節點的右孩子):
- 父節點染為紅色兄弟節點染為黑色對父節點進行右旋重新計算兄弟節點
這時, 父節點為紅色, 兄弟節點為黑色, 進入其它情況.
示例圖
在下圖紅黑樹中, 要刪除節點5
按照上述的處理步驟進行調整, 調整之後的紅黑樹如下:
這時還是不符合紅黑樹的性質, 需要進一步調整, 這時進入情況3-1-3.
情況3-1-2: 待刪除節點為黑色 & 兄弟節點為黑色 & 兄弟節點的兩個孩子有一個為紅色
處理步驟(待刪除節點是父節點的左孩子):
- 判斷兄弟節點的右節點是否是黑色(NULL節點為黑色)
- 將兄弟節點的左孩子染為黑色
- 將兄弟節點染為紅色
- 對兄弟節點進行右旋
- 重新計算兄弟節點
- 將兄弟節點的顏色染為父節點的顏色
- 將父節點染為黑色將兄弟節點的右孩子染為黑色
- 對父節點進行左旋
處理步驟(待刪除節點是父節點的右孩子):
- 判斷兄弟節點的左節點是否是黑色(NULL節點為黑色)
- 將兄弟節點的右孩子染為黑色
- 將兄弟節點染為紅色
- 對兄弟節點進行左旋重新計算兄弟節點
- 將兄弟節點的顏色染為父節點的顏色
- 將父節點染為黑色將兄弟節點的右孩子染為黑色
- 對父節點進行右旋
示例圖
以待刪除節點是父節點的左孩子為例, 在下圖紅黑樹中, 要刪除節點15
按照上述的處理步驟進行調整, 調整之後的紅黑樹如下:
調整完成.
中間我們省略了步驟1中的處理步驟, 內部的處理步驟同插入時的調整類似, 把兄弟節點的紅色孩子節點調整兄弟節點的右孩子(如果兄弟節點是左孩子的話, 那麼就是將紅色孩子節點調整為左孩子).
其實這種情況下, 我們不關係待刪除節點的父節點的顏色, 因為這種情況的調整是在內部進行調整的.
情況3-1-3: 待刪除節點為黑色 & 兄弟節點為黑色 & 兄弟節點的兩個孩子都是黑色(包括NULL節點)
注: 這裡兄弟的孩子節點包括NULL節點.
處理步驟:
- 將兄弟節點染為紅色將父節點染為黑色
該情況與當待刪除節點是父節點的左孩子還是右孩子無關, 因為不涉及旋轉.
當前節點指向父節點之後, 再看符合哪種調整情況, 繼續進行調整.
示例圖
情況3-1-1中調整之後樹為:
按照上述的處理步驟進行調整, 調整之後的紅黑樹如下:
調整完成.
情況3-2: 待刪除節點為紅色
這時, 父節點為黑色, 兄弟節點一定為紅色. 因為此時待刪除節點和兄弟節點都沒有孩子節點.
直接刪除就好.
刪除總結
刪除時, 先看待刪除節點的顏色, 然後查看其兄弟節點的顏色, 再查看兄弟節點的孩子節點的顏色, 然後根據具體的情況進行調整.
參考TreeMap的刪除調整代碼
/** From CLR */private void fixAfterDeletion(Entryx) {
// 刪除的節點為黑色時, 需要進行調整
while (x != root && colorOf(x) == BLACK) {
// 當前節點是左節點
if (x == leftOf(parentOf(x))) {
// 獲取右節點(兄弟節點)
Entrysib = rightOf(parentOf(x));
// 兄弟節點是紅色時
if (colorOf(sib) == RED) {
// 兄弟節點染為黑色
setColor(sib, BLACK);
// 父節點染為紅色
setColor(parentOf(x), RED);
// 對父節點進行左旋
rotateLeft(parentOf(x));
// 重新計算兄弟節點
sib = rightOf(parentOf(x));
}
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) { // 兄弟節點的兩個孩子都是黑色
// 兄弟節點染為紅色
setColor(sib, RED);
// 將當前節點指向父節點
x = parentOf(x);
} else { // 兄弟節點的兩個孩子有一個為紅色
// 判斷兄弟節點紅色孩子節點的位置
// 將兄弟節點的紅色孩子節點調整到兄弟節點的右孩子節點位置
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
// 將兄弟節點的顏色染為父節點的顏色
setColor(sib, colorOf(parentOf(x)));
// 父節點染為黑色
setColor(parentOf(x), BLACK);
// 兄弟節點的右孩子染為黑色
setColor(rightOf(sib), BLACK);
// 對父節點進行左旋
rotateLeft(parentOf(x));
// 退出循環
x = root;
}
} else { // symmetric
Entrysib = leftOf(parentOf(x));
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}
if (colorOf(rightOf(sib)) == BLACK &&
colorOf(leftOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(leftOf(sib)) == BLACK) {
setColor(rightOf(sib), BLACK);
setColor(sib, RED);
rotateLeft(sib);
sib = leftOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(leftOf(sib), BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}
// 最後將當前節點染為黑色, 為什麼需要這段代碼? 我覺得你應該知道的.
setColor(x, BLACK);}
總結
紅黑樹是一個比較重要的算法, 我覺得作為一個程序員應該需要了解它.
紅黑樹的核心在於元素變動之後, 如何進行調整使其重新成為一顆紅黑樹.
通過學習紅黑樹, 深刻體會到大問題並不可怕, 一點點拆分為小問題, 一定會解決的.
文章不是一氣呵成的, 個別地方可能會有問題, 如有發現, 煩請指出.
JAVA算法
鏈接：http://www.imooc.com/article/247142
閱讀更多 前端小學生 的文章
