這篇文章收錄在我的 Github 上 algorithms-tutorial轧铁，另外記錄了些算法題解艾栋，感興趣的可以看看，轉(zhuǎn)載請注明出處诬留。
(一) 基本概念
Red-Black Tree 稱為“紅黑樹”揩环，是一種自平衡二叉查找樹搔弄，紅黑樹和 AVL 樹類似，在進行插入和刪除時需要通過旋轉(zhuǎn)和重新著色來維持其紅黑樹的特性丰滑。
紅黑樹的應(yīng)用相當廣泛顾犹，主要是用它來存儲有序的數(shù)據(jù)，它的時間復(fù)雜度為 O(logn)，查詢效率非常高炫刷。
1. 紅黑樹和 AVL 樹的區(qū)別：
- 紅黑樹并不追求“完全平衡” —— 它只要求部分地達到平衡要求擎宝，降低了對旋轉(zhuǎn)的要求，從而提高了性能浑玛。
- 在AVL樹中任何節(jié)點的兩個兒子子樹的高度最大差別為一绍申，所以它也被稱為高度平衡樹。
- 紅黑樹的算法時間復(fù)雜度和 AVL 相同顾彰，但統(tǒng)計性能比 AVL 樹更高极阅。
- 紅黑樹是犧牲了嚴格的高度平衡的優(yōu)越條件為代價紅黑樹能夠以 O(log2 n) 的時間復(fù)雜度進行搜索、插入拘央、刪除操作涂屁。由于它的設(shè)計书在，任何不平衡都會在三次旋轉(zhuǎn)之內(nèi)解決灰伟。
2. 紅黑樹的執(zhí)行：
- 每個節(jié)點具有顏色屬性，要么為紅色儒旬，要么為黑色
- 根節(jié)點是黑色的
- 每個葉子節(jié)點 (null) 是黑色的 (這里葉子節(jié)點栏账，指為空的葉子節(jié)點)
- 如果一個節(jié)點是紅色的，則其子節(jié)點必須是黑色的
- 從一個節(jié)點到該節(jié)點的葉節(jié)點 (null) 所有路徑包含相同數(shù)目的黑節(jié)點
3. 紅黑樹的優(yōu)點：
- 紅黑樹的性質(zhì)決定了從根節(jié)點到最遠的葉節(jié)點的距離不可能超過從根節(jié)點到葉節(jié)點的距離的兩倍栈源。
- 另外可以證明的是紅黑樹的高度最多為 log(n + 1)挡爵，n 為節(jié)點個數(shù)
- 插入和刪除在最壞的情況下為 O(logn)
- 紅黑樹提供了一種替代 AVL 樹的方式，并且是一種更加簡單甚垦，不用遞歸的插入算法
4. 紅黑樹的示意圖：
(二) 基本操作
紅黑樹的基本操作是添加茶鹃、刪除。前面我們提到艰亮，在進行插入和刪除時需要通過旋轉(zhuǎn)和重新著色來維持其紅黑樹的特性闭翩，那么接下來就介紹這些操作：
一、左旋和右旋：
1. 左旋：
可以將 X 稱為當前節(jié)點迄埃，則左旋的字面意思就是將當前節(jié)點變?yōu)樽笞庸?jié)點疗韵。（這樣可避免左右旋傻傻分不清）
這時候 X 變?yōu)?Y 的左子節(jié)點盐股，若 Y 節(jié)點存在左子樹(即圖中的 β)帽馋，則將其變?yōu)?X 的右子樹
Java 代碼實現(xiàn)：
public TreeNode singleRotateWithLeft(TreeNode presentNode){
TreeNode node; //新的父節(jié)點
node = presentNode.rightChild;
presentNode.rightChild = node.leftChild;
node.leftChild = presentNode;
return node;
}
2. 右旋：
此時當前節(jié)點為 Y，則 Y節(jié)點變?yōu)?X 節(jié)點的右子樹封字，而若 X 存在右子樹(即圖中的 β)逞怨，則變?yōu)?Y 節(jié)點的左子樹
Java 代碼實現(xiàn)：
public TreeNode singleRotateWithRight(TreeNode presentNode){
TreeNode node;
node = presentNode.leftChild;
presentNode.leftChild = node.rightChild;
node.rightChild = presentNode;
return node;
}
二者疤、插入：
一個節(jié)點要插入到紅黑樹中，需要的步驟：
- 將紅黑樹當作一棵二叉查找樹叠赦，將節(jié)點插入
- 將該節(jié)點著色為紅色
- 通過旋轉(zhuǎn)和重新著色等方法修正該樹驹马，使之重新成為一棵紅黑樹
第一步：將紅黑樹當作一棵二叉查找樹，將節(jié)點插入
紅黑樹本身也是二叉查找樹，將節(jié)點插入后窥翩，該樹仍是二叉查找樹业岁。
第二步：將該節(jié)點著色為紅色
將插入的節(jié)點著色為紅色，不會違背特性(5):從一個節(jié)點到該節(jié)點的葉節(jié)點 (null) 所有路徑包含相同數(shù)目的黑節(jié)點
若插入的節(jié)點為黑色寇蚊，那么該路徑的節(jié)點就多了一個黑節(jié)點笔时，這顯然與特性(5) 相違背。
第三步：通過旋轉(zhuǎn)和重新著色等方法修正該樹仗岸，使之重新成為一棵紅黑樹
第二步中允耿，將插入的節(jié)點著色為 "紅色" 之后，不會違背特性 (5)扒怖，那么它還會違背其他特性嗎较锡？
對于特性(1) (2) (3) 顯然都不會違背，請自行想象
而對于特性 (4)盗痒，是有可能違背的
因為插入節(jié)點的父節(jié)點也可能為紅色蚂蕴，那么顯然與一個紅色節(jié)點的子節(jié)點必須為黑節(jié)點相違背。
那么俯邓，既然有可能違背特性(4) 那么我們可以通過旋轉(zhuǎn)或者重新著色來使其滿足特性(4)骡楼，再次成為紅黑樹。
無論旋轉(zhuǎn)還是重新著色稽鞭，其核心思路都是：將紅色的節(jié)點移到根節(jié)點鸟整；然后，將根節(jié)點設(shè)為黑色朦蕴。
對于插入節(jié)點的情況篮条，可以大致分為以下五種：
情況1:被插入的節(jié)點是根節(jié)點
處理方式：直接把此節(jié)點涂為黑色。
這個顯然吩抓，不然就會違背特性(2): 根節(jié)點是黑色的
代碼實現(xiàn)：
public void insert_case1(TreeNode presentNode){
if(presentNode.parent == null){
presentNode.color = "black";
}else{
insert_case2(presentNode);
}
}
情況2: 被插入的節(jié)點的父節(jié)點是黑色
處理方式：什么都不需要做涉茧，節(jié)點被插入后，仍然是紅黑樹琴拧。
代碼實現(xiàn)：
public void insert_case2(TreeNode presentNode){
if(presentNode.parent.color.equals("black")){
// do nothing
}else{
insert_case3(presentNode);
}
}
情況3降瞳、4、5 就比較復(fù)雜了些蚓胸，但是核心思路仍是：將紅色的節(jié)點移到根節(jié)點挣饥；然后，將根節(jié)點設(shè)為黑色沛膳。
在介紹方法之前扔枫，先來了解幾個概念：
如圖所示，新插入節(jié)點的父節(jié)點的父節(jié)點(即圖中黑節(jié)點)即是新插入節(jié)點的祖父節(jié)點锹安，而祖父節(jié)點的右子節(jié)點稱為叔叔節(jié)點短荐。
以后代碼部分的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu) ADT 都是用這個節(jié)點樹來實現(xiàn)的：
//java
public class TreeNode{
TreeNode leftChild;
TreeNode rightChild;
TreeNode parent;
TreeNode grandParent;
TreeNode uncle;
String color;
public TreeNode(){
grandParent = this.parent.parent;
if(this.parent == grandParent.leftChild){
uncle = grandParent.rightChild;
}else{
uncle = grandParent.leftChild;
}
}
}
情況3倚舀、4、5 都是建立在插入節(jié)點的父節(jié)點為紅色的情況下忍宋，此時會違背特性(4)痕貌，所以我們需要通過旋轉(zhuǎn)和重新著色來修復(fù)紅黑樹
情況3: 叔叔節(jié)點是紅色
處理方式：
- 將 "父節(jié)點" 設(shè)為黑色
- 將 "叔叔節(jié)點" 設(shè)為黑色
- 將 "祖父節(jié)點" 設(shè)為紅色
- 將 "祖父節(jié)點" 設(shè)為 "當前節(jié)點"(紅色節(jié)點)；之后繼續(xù)對 "當前" 進行操作
新插入節(jié)點為 N糠排，符合情況 3 要求舵稠，則將 P，U 變?yōu)楹谏牖拢珿 變?yōu)榧t色哺徊，之后再將 G 作為當前節(jié)點繼續(xù)判斷，因為 G 為根節(jié)點乾闰，那么根據(jù)情況 1落追，將其涂為黑色，完事涯肩。
代碼實現(xiàn)：
public void insert_case3(TreeNode presentNode){
if(presentNode.uncle != null && presentNode.uncle.color.equals("red")){
presentNode.parent.color = "black";
presentNode.uncle.color = "black";
grandParent.color = "red";
insert_case1(grandParent);
}else{
insert_case4(presentNode);
}
}
我再舉個例子來說明：往一課紅黑樹中插入節(jié)點 45
符合情況 3轿钠，所以顏色重繪并將節(jié)點 60 作為當前節(jié)點，就變?yōu)榱?/p>
之后又符合情況 3宽菜，所以繼續(xù)操作谣膳，最后將根節(jié)點涂成黑色就結(jié)束了
情況 4：叔叔節(jié)點為黑色或缺失竿报，且當前節(jié)點是曲線邊 (即左右或右左)
處理方式：
- 將 "父節(jié)點" 作為 "新的當前節(jié)點"
- 以 "新的當前節(jié)點" 為支點進行左旋
- 以新的當前節(jié)點(即原本的父節(jié)點)再進行操作
如圖所示：
將 P 節(jié)點作為當前節(jié)點進行左旋铅乡，然后之后再對 P 節(jié)點進行操作
代碼實現(xiàn)：
public void insert_case4(TreeNode presentNode){
if(presentNode == presentNode.parent.rightChild && presentNode.parent == presentNode.grandParent.leftChild){
singleRotateWithLeft(presentNode.parent);
presentNode = presentNode.leftChild;
}else if(presentNode == presentNode.parent.leftChild && presentNode.parent == presentNode.grandParent.rightChild){
singleRotateWithRight(presentNode.parent);
presentNode = presentNode.rightChild;
}
insert_case5(presentNode);
}
情況 5: 叔叔節(jié)點為黑色或缺失，且當前節(jié)點是在外邊(即左左或右右)
處理方式：
- 將 "父節(jié)點" 設(shè)為黑色
- 將 "祖父節(jié)點" 設(shè)為紅色
- 以 "祖父節(jié)點" 為支點進行右旋
如圖所示:
代碼實現(xiàn)：
public void insert_case5(TreeNode presentNode){
presentNode.parent.color = "black";
presentNode.grandParent.color = "red";
if(presentNode == presentNode.parent.leftChild && presentNode.parent == presentNode.grandParent.leftChild){
singleRotateWithRight(presentNode);
}else{
singleRotateWithLeft(presentNode);
}
}
讓我們用一個例子來結(jié)合說明情況 3烈菌、4阵幸、5
往圖中原本的紅黑樹插入節(jié)點 45，這里先用到情況3芽世，接著 4挚赊，最后 5，所以不再贅述原理济瓢。
step1:
step2
step3
前面代碼部分都是用尾遞歸來實現(xiàn)插入操作荠割，顯然這種插入效率并不高，截下來我改用迭代的方式來進行插入操作
迭代實現(xiàn)插入操作
public void insert_case(TreeNode presentNode){
while(presentNode != null){
if(presentNode.parent == null){
presentNode.color = "black";
break;
}else if(presentNode.parent.color.equals("black")){
//do nothing
break;
}else if(presentNode.uncle != null && presentNode.uncle.color.equals("red")){
presentNode.parent.color = "black";
presentNode.uncle.color = "black";
presentNode.grandParent.color = "red";
presentNode = presentNode.grandParent;
}else if(presentNode == presentNode.parent.rightChild && presentNode.parent == presentNode.grandParent.leftChild){
singleRotateWithLeft(presentNode.parent);
presentNode = presentNode.leftChild;
}else if(presentNode == presentNode.parent.leftChild && presentNode.parent == presentNode.grandParent.rightChild){
singleRotateWithRight(presentNode.parent);
presentNode = presentNode.rightChild;
}else{
presentNode.parent.color = "black";
presentNode.grandParent.color = "red";
if(presentNode == presentNode.parent.leftChild && presentNode.parent == presentNode.grandParent.leftChild){
singleRotateWithRight(presentNode);
}else{
singleRotateWithLeft(presentNode);
}
}
}
}
另外老師還介紹了一種 Top-down 的插入方法：從根節(jié)點到插入的節(jié)點的路徑中查找旺矾，如果遇到一個節(jié)點 X 帶有兩個紅色兒子蔑鹦，就執(zhí)行下面的操作：
這樣就會遇到一個問題：如果節(jié)點 X 的父節(jié)點也是紅色，那就違背了性質(zhì) 4箕宙，這時候我們就要根據(jù)前一種方法的情況 3嚎朽、4、5去進行討論
課上例題：構(gòu)造一棵紅黑樹柬帕，按順序加入 10哟忍，85狡门，15，70锅很，20其馏，60，30爆安，50尝偎，65，80鹏控，90致扯，40，5当辐，55
三抖僵、刪除：
將紅黑樹內(nèi)的某一個節(jié)點刪除。需要執(zhí)行的操作依次是：
- 將紅黑樹當作一顆二叉查找樹缘揪，將該節(jié)點從二叉查找樹中刪除
- 通過"旋轉(zhuǎn)和重新著色"等一系列來修正該樹耍群，使之重新成為一棵紅黑樹
在分析之前，我們再次溫習(xí)一下紅黑樹的幾個特性：
- 每個節(jié)點具有顏色屬性找筝，要么為紅色蹈垢，要么為黑色
- 根節(jié)點是黑色的
- 每個葉子節(jié)點 (null) 是黑色的 (這里葉子節(jié)點，指為空的葉子節(jié)點)
- 如果一個節(jié)點是紅色的袖裕，則其子節(jié)點必須是黑色的
- 從一個節(jié)點到該節(jié)點的葉節(jié)點 (null) 所有路徑包含相同數(shù)目的黑節(jié)點
參考鏈接:
