紅黑樹是平衡二叉查找樹的一種。為了深入理解紅黑樹，我們需要從二叉查找樹開始講起隶垮。

BST

二叉查找樹（Binary Search Tree，簡稱BST）是一棵二叉樹秘噪，它的左子節(jié)點(diǎn)的值比父節(jié)點(diǎn)的值要小狸吞，右節(jié)點(diǎn)的值要比父節(jié)點(diǎn)的值大。它的高度決定了它的查找效率指煎。

BST

BST的查找操作

T  key = a search key
Node root = point to the root of a BST

while(true){
    if(root==null){
        break;
    }
    if(root.value.equals(key)){
        return root;
    }
    else if(key.compareTo(root.value)<0){
        root = root.left;
    }
    else{
        root = root.right;
    }
}
return null;

從程序中可以看出像街，當(dāng)BST查找的時(shí)候黎棠，先與當(dāng)前節(jié)點(diǎn)進(jìn)行比較：

• 如果相等的話就返回當(dāng)前節(jié)點(diǎn)；
• 如果少于當(dāng)前節(jié)點(diǎn)則繼續(xù)查找當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)宅广；
• 如果大于當(dāng)前節(jié)點(diǎn)則繼續(xù)查找當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)葫掉。

直到當(dāng)前節(jié)點(diǎn)指針為空或者查找到對(duì)應(yīng)的節(jié)點(diǎn)，程序查找結(jié)束跟狱。

BST的插入操作

Node node = create a new node with specify value
Node root = point the root node of a BST
Node parent = null;

//find the parent node to append the new node
while(true){
   if(root==null)break;
   parent = root;
   if(node.value.compareTo(root.value)<=0){
      root = root.left;  
   }else{
      root = root.right;
   } 
}
if(parent!=null){
   if(node.value.compareTo(parent.value)<=0){//append to left
      parent.left = node;
   }else{//append to right
      parent.right = node;
   }
}

插入操作先通過循環(huán)查找到待插入的節(jié)點(diǎn)的父節(jié)點(diǎn)俭厚，和查找父節(jié)點(diǎn)的邏輯一樣，都是比大小驶臊，小的往左挪挤，大的往右叼丑。找到父節(jié)點(diǎn)后，對(duì)比父節(jié)點(diǎn)扛门，小的就插入到父節(jié)點(diǎn)的左節(jié)點(diǎn)鸠信，大就插入到父節(jié)點(diǎn)的右節(jié)點(diǎn)上。

BST的刪除操作

刪除操作的步驟如下：

• 查找到要?jiǎng)h除的節(jié)點(diǎn)论寨。
• 如果待刪除的節(jié)點(diǎn)是葉子節(jié)點(diǎn)星立，則直接刪除。
• 如果待刪除的節(jié)點(diǎn)不是葉子節(jié)點(diǎn)葬凳，則先找到待刪除節(jié)點(diǎn)的中序遍歷的后繼- 節(jié)點(diǎn)绰垂，用該后繼節(jié)點(diǎn)的值替換待刪除的節(jié)點(diǎn)的值，然后刪除后繼節(jié)點(diǎn)火焰。

BST remove

BST存在的問題

BST存在的主要問題是劲装，數(shù)在插入的時(shí)候會(huì)導(dǎo)致樹傾斜，不同的插入順序會(huì)導(dǎo)致樹的高度不一樣昌简，而樹的高度直接的影響了樹的查找效率占业。理想的高度是logN，最壞的情況是所有的節(jié)點(diǎn)都在一條斜線上纯赎，這樣的樹的高度為N谦疾。

RBTree

基于BST存在的問題，一種新的樹——平衡二叉查找樹(Balanced BST)產(chǎn)生了址否。平衡樹在插入和刪除的時(shí)候餐蔬，會(huì)通過旋轉(zhuǎn)操作將高度保持在logN。其中兩款具有代表性的平衡樹分別為AVL樹和紅黑樹佑附。AVL樹由于實(shí)現(xiàn)比較復(fù)雜樊诺，而且插入和刪除性能差，在實(shí)際環(huán)境下的應(yīng)用不如紅黑樹音同。

紅黑樹（Red-Black Tree词爬，以下簡稱RBTree）的實(shí)際應(yīng)用非常廣泛，比如Linux內(nèi)核中的完全公平調(diào)度器权均、高精度計(jì)時(shí)器顿膨、ext3文件系統(tǒng)等等，各種語言的函數(shù)庫如Java的TreeMap和TreeSet叽赊，C++ STL的map恋沃、multimap、multiset等必指。

RBTree也是函數(shù)式語言中最常用的持久數(shù)據(jù)結(jié)構(gòu)之一囊咏，在計(jì)算幾何中也有重要作用。值得一提的是，Java 8中HashMap的實(shí)現(xiàn)也因?yàn)橛肦BTree取代鏈表梅割，性能有所提升霜第。

RBTree的定義

RBTree的定義如下:

• 任何一個(gè)節(jié)點(diǎn)都有顏色，黑色或者紅色
• 根節(jié)點(diǎn)是黑色的
• 父子節(jié)點(diǎn)之間不能出現(xiàn)兩個(gè)連續(xù)的紅節(jié)點(diǎn)
• 任何一個(gè)節(jié)點(diǎn)向下遍歷到其子孫的葉子節(jié)點(diǎn)户辞，所經(jīng)過的黑節(jié)點(diǎn)個(gè)數(shù)必須相等
• 空節(jié)點(diǎn)被認(rèn)為是黑色的

數(shù)據(jù)結(jié)構(gòu)表示如下：

class  Node<T>{
   public  T value;
   public   Node<T> parent;
   public   boolean isRed;
   public   Node<T> left;
   public   Node<T> right;
}

RBTree在理論上還是一棵BST樹泌类，但是它在對(duì)BST的插入和刪除操作時(shí)會(huì)維持樹的平衡，即保證樹的高度在[logN,logN+1]（理論上底燎，極端的情況下可以出現(xiàn)RBTree的高度達(dá)到2*logN刃榨，但實(shí)際上很難遇到）。這樣RBTree的查找時(shí)間復(fù)雜度始終保持在O(logN)從而接近于理想的BST书蚪。RBTree的刪除和插入操作的時(shí)間復(fù)雜度也是O(logN)喇澡。RBTree的查找操作就是BST的查找操作。

RBTree的旋轉(zhuǎn)操作

旋轉(zhuǎn)操作(Rotate)的目的是使節(jié)點(diǎn)顏色符合定義殊校，讓RBTree的高度達(dá)到平衡。Rotate分為left-rotate（左旋）和right-rotate（右旋）读存，區(qū)分左旋和右旋的方法是：待旋轉(zhuǎn)的節(jié)點(diǎn)從左邊上升到父節(jié)點(diǎn)就是右旋为流，待旋轉(zhuǎn)的節(jié)點(diǎn)從右邊上升到父節(jié)點(diǎn)就是左旋。

BST remove

RBTree的查找操作
RBTree的查找操作和BST的查找操作是一樣的让簿。請(qǐng)參考BST的查找操作代碼敬察。

RBTree的插入操作

RBTree的插入與BST的插入方式是一致的，只不過是在插入過后尔当，可能會(huì)導(dǎo)致樹的不平衡莲祸，這時(shí)就需要對(duì)樹進(jìn)行旋轉(zhuǎn)操作和顏色修復(fù)（在這里簡稱插入修復(fù)），使得它符合RBTree的定義椭迎。
新插入的節(jié)點(diǎn)是紅色的锐帜，插入修復(fù)操作如果遇到父節(jié)點(diǎn)的顏色為黑則修復(fù)操作結(jié)束。也就是說畜号，只有在父節(jié)點(diǎn)為紅色節(jié)點(diǎn)的時(shí)候是需要插入修復(fù)操作的缴阎。
插入修復(fù)操作分為以下的三種情況，而且新插入的節(jié)點(diǎn)的父節(jié)點(diǎn)都是紅色的：
叔叔節(jié)點(diǎn)也為紅色简软。
叔叔節(jié)點(diǎn)為空蛮拔，且祖父節(jié)點(diǎn)、父節(jié)點(diǎn)和新節(jié)點(diǎn)處于一條斜線上痹升。
叔叔節(jié)點(diǎn)為空建炫，且祖父節(jié)點(diǎn)、父節(jié)點(diǎn)和新節(jié)點(diǎn)不處于一條斜線上疼蛾。

插入操作-case 1

插入修復(fù)case 1

插入修復(fù)case 2

插入修復(fù)case 3

祖父節(jié)點(diǎn)調(diào)節(jié)后如果還是遇到它的祖父顏色問題切省，操作就會(huì)繼續(xù)向上回溯最岗，直到root節(jié)點(diǎn)為止，根據(jù)定義root節(jié)點(diǎn)永遠(yuǎn)是黑色的数尿。在向上的追溯的過程中仑性，針對(duì)插入的3中情況進(jìn)行調(diào)節(jié)。直到符合紅黑樹的定義為止右蹦。直到牽涉的節(jié)點(diǎn)都符合了紅黑樹的定義诊杆，修復(fù)操作結(jié)束。
如果上面的3中情況如果對(duì)應(yīng)的操作是在右子樹上何陆，做對(duì)應(yīng)的鏡像操作就是了晨汹。
RBTree的刪除操作
刪除操作首先需要做的也是BST的刪除操作，刪除操作會(huì)刪除對(duì)應(yīng)的節(jié)點(diǎn)贷盲，如果是葉子節(jié)點(diǎn)就直接刪除淘这，如果是非葉子節(jié)點(diǎn)剥扣，會(huì)用對(duì)應(yīng)的中序遍歷的后繼節(jié)點(diǎn)來頂替要?jiǎng)h除節(jié)點(diǎn)的位置。刪除后就需要做刪除修復(fù)操作铝穷，使的樹符合紅黑樹的定義钠怯，符合定義的紅黑樹高度是平衡的。
刪除修復(fù)操作在遇到被刪除的節(jié)點(diǎn)是紅色節(jié)點(diǎn)或者到達(dá)root節(jié)點(diǎn)時(shí)曙聂，修復(fù)操作完畢晦炊。
刪除修復(fù)操作是針對(duì)刪除黑色節(jié)點(diǎn)才有的，當(dāng)黑色節(jié)點(diǎn)被刪除后會(huì)讓整個(gè)樹不符合RBTree的定義的第四條宁脊。需要做的處理是從兄弟節(jié)點(diǎn)上借調(diào)黑色的節(jié)點(diǎn)過來断国，如果兄弟節(jié)點(diǎn)沒有黑節(jié)點(diǎn)可以借調(diào)的話，就只能往上追溯榆苞，將每一級(jí)的黑節(jié)點(diǎn)數(shù)減去一個(gè)稳衬，使得整棵樹符合紅黑樹的定義。
刪除操作的總體思想是從兄弟節(jié)點(diǎn)借調(diào)黑色節(jié)點(diǎn)使樹保持局部的平衡坐漏，如果局部的平衡達(dá)到了薄疚，就看整體的樹是否是平衡的，如果不平衡就接著向上追溯調(diào)整仙畦。
刪除修復(fù)操作分為四種情況(刪除黑節(jié)點(diǎn)后)：
待刪除的節(jié)點(diǎn)的兄弟節(jié)點(diǎn)是紅色的節(jié)點(diǎn)输涕。
待刪除的節(jié)點(diǎn)的兄弟節(jié)點(diǎn)是黑色的節(jié)點(diǎn)，且兄弟節(jié)點(diǎn)的子節(jié)點(diǎn)都是黑色的慨畸。
待調(diào)整的節(jié)點(diǎn)的兄弟節(jié)點(diǎn)是黑色的節(jié)點(diǎn)，且兄弟節(jié)點(diǎn)的左子節(jié)點(diǎn)是紅色的衣式，右節(jié)點(diǎn)是黑色的(兄弟節(jié)點(diǎn)在右邊)寸士，如果兄弟節(jié)點(diǎn)在左邊的話，就是兄弟節(jié)點(diǎn)的右子節(jié)點(diǎn)是紅色的碴卧，左節(jié)點(diǎn)是黑色的弱卡。
待調(diào)整的節(jié)點(diǎn)的兄弟節(jié)點(diǎn)是黑色的節(jié)點(diǎn)，且右子節(jié)點(diǎn)是是紅色的(兄弟節(jié)點(diǎn)在右邊)住册，如果兄弟節(jié)點(diǎn)在左邊婶博，則就是對(duì)應(yīng)的就是左節(jié)點(diǎn)是紅色的。

刪除操作-case 1
由于兄弟節(jié)點(diǎn)是紅色節(jié)點(diǎn)的時(shí)候荧飞，無法借調(diào)黑節(jié)點(diǎn)凡人，所以需要將兄弟節(jié)點(diǎn)提升到父節(jié)點(diǎn)，由于兄弟節(jié)點(diǎn)是紅色的叹阔，根據(jù)RBTree的定義挠轴，兄弟節(jié)點(diǎn)的子節(jié)點(diǎn)是黑色的，就可以從它的子節(jié)點(diǎn)借調(diào)了耳幢。
case 1這樣轉(zhuǎn)換之后就會(huì)變成后面的case 2岸晦，case 3，或者case 4進(jìn)行處理了。上升操作需要對(duì)C做一個(gè)左旋操作启上，如果是鏡像結(jié)構(gòu)的樹只需要做對(duì)應(yīng)的右旋操作即可邢隧。
之所以要做case 1操作是因?yàn)樾值芄?jié)點(diǎn)是紅色的，無法借到一個(gè)黑節(jié)點(diǎn)來填補(bǔ)刪除的黑節(jié)點(diǎn)冈在。

刪除情況1

刪除情況2

刪除情況3

刪除情況4

代碼調(diào)試的時(shí)候桑涎，printTree輸出格式如下:d(B)b(B d LE) g(R d RI)a(R b LE) e(B g LE) h(B g RI)f(R e RI)
括號(hào)左邊表示元素的內(nèi)容彬向。括號(hào)內(nèi)的第一個(gè)元素表示顏色，B表示black攻冷，R表示red娃胆；第二個(gè)元素表示父元素的值；第三個(gè)元素表示左右等曼，LE表示在父元素的左邊里烦。RI表示在父元素的右邊凿蒜。
第一個(gè)元素d是root節(jié)點(diǎn)，由于它沒有父節(jié)點(diǎn)胁黑，所以括號(hào)內(nèi)只有一個(gè)元素废封。
總結(jié)
作為平衡二叉查找樹里面眾多的實(shí)現(xiàn)之一，紅黑樹無疑是最簡潔丧蘸、實(shí)現(xiàn)最為簡單的漂洋。紅黑樹通過引入顏色的概念，通過顏色這個(gè)約束條件的使用來保持樹的高度平衡力喷。作為平衡二叉查找樹刽漂，旋轉(zhuǎn)是一個(gè)必不可少的操作。通過旋轉(zhuǎn)可以降低樹的高度弟孟，在紅黑樹里面還可以轉(zhuǎn)換顏色贝咙。
紅黑樹里面的插入和刪除的操作比較難理解，這時(shí)要注意記住一點(diǎn)：操作之前紅黑樹是平衡的披蕉，顏色是符合定義的颈畸。在操作的時(shí)候就需要向兄弟節(jié)點(diǎn)、父節(jié)點(diǎn)没讲、侄子節(jié)點(diǎn)借調(diào)和互換顏色眯娱，要達(dá)到這個(gè)目的，就需要不斷的進(jìn)行旋轉(zhuǎn)爬凑。所以紅黑樹的插入刪除操作需要不停的旋轉(zhuǎn)徙缴，一旦借調(diào)了別的節(jié)點(diǎn)，刪除和插入的節(jié)點(diǎn)就會(huì)達(dá)到局部的平衡（局部符合紅黑樹的定義）嘁信，但是被借調(diào)的節(jié)點(diǎn)就不會(huì)平衡了于样，這時(shí)就需要以被借調(diào)的節(jié)點(diǎn)為起點(diǎn)繼續(xù)進(jìn)行調(diào)整，直到整棵樹都是平衡的潘靖。在整個(gè)修復(fù)的過程中穿剖，插入具體的分為3種情況，刪除分為4種情況卦溢。
整個(gè)紅黑樹的查找糊余，插入和刪除都是O(logN)的，原因就是整個(gè)紅黑樹的高度是logN单寂，查找從根到葉贬芥，走過的路徑是樹的高度，刪除和插入操作是從葉到根的宣决，所以經(jīng)過的路徑都是logN蘸劈。
參考文獻(xiàn)
Cormen T H, Leiserson C E, Rivest R L, 等. 算法導(dǎo)論（第3版）. 殷建平, 等. 機(jī)械工業(yè)出版社, 2012.
Sedgewick R, Wayne K. 算法（第4版）. 謝路云 譯. 人民郵電出版社, 2012.
Weiss M A. 數(shù)據(jù)結(jié)構(gòu)與算法分析（第2版）. 馮舜璽 譯. 機(jī)械工業(yè)出版社, 2004.
Knuth D E. 計(jì)算機(jī)程序設(shè)計(jì)藝術(shù) 卷3：排序與查找（英文版 第2版）. 人民郵電出版社, 2010.