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

BST

二叉查找樹（Binary Search Tree翘魄，簡稱BST）是一棵二叉樹鼎天，它的左子節(jié)點(diǎn)的值比父節(jié)點(diǎn)的值要小，右節(jié)點(diǎn)的值要比父節(jié)點(diǎn)的值大暑竟。它的高度決定了它的查找效率斋射。

在理想的情況下，二叉查找樹增刪查改的時間復(fù)雜度為O(logN)（其中N為節(jié)點(diǎn)數(shù)）光羞，最壞的情況下為O(N)绩鸣。當(dāng)它的高度為logN+1時，我們就說二叉查找樹是平衡的纱兑。

image

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查找的時候，先與當(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)指針為空或者查找到對應(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)后榜掌，對比父節(jié)點(diǎn)优妙，小的就插入到父節(jié)點(diǎn)的左節(jié)點(diǎn)，大就插入到父節(jié)點(diǎn)的右節(jié)點(diǎn)上憎账。

BST的刪除操作

刪除操作的步驟如下：

1. 查找到要刪除的節(jié)點(diǎn)套硼。
2. 如果待刪除的節(jié)點(diǎn)是葉子節(jié)點(diǎn)，則直接刪除胞皱。
3. 如果待刪除的節(jié)點(diǎn)不是葉子節(jié)點(diǎn)邪意，則先找到待刪除節(jié)點(diǎn)的中序遍歷的后繼節(jié)點(diǎn)，用該后繼節(jié)點(diǎn)的值替換待刪除的節(jié)點(diǎn)的值反砌，然后刪除后繼節(jié)點(diǎn)雾鬼。

image

BST存在的問題

BST存在的主要問題是，數(shù)在插入的時候會導(dǎo)致樹傾斜于颖，不同的插入順序會導(dǎo)致樹的高度不一樣呆贿，而樹的高度直接的影響了樹的查找效率。理想的高度是logN森渐，最壞的情況是所有的節(jié)點(diǎn)都在一條斜線上做入，這樣的樹的高度為N。

RBTree

基于BST存在的問題同衣，一種新的樹——平衡二叉查找樹(Balanced BST)產(chǎn)生了竟块。平衡樹在插入和刪除的時候，會通過旋轉(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ì)時器、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的定義如下:

1. 任何一個節(jié)點(diǎn)都有顏色贪染，黑色或者紅色
2. 根節(jié)點(diǎn)是黑色的
3. 父子節(jié)點(diǎn)之間不能出現(xiàn)兩個連續(xù)的紅節(jié)點(diǎn)
4. 任何一個節(jié)點(diǎn)向下遍歷到其子孫的葉子節(jié)點(diǎn)缓呛，所經(jīng)過的黑節(jié)點(diǎn)個數(shù)必須相等
5. 空節(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樹，但是它在對BST的插入和刪除操作時會維持樹的平衡杭隙，即保證樹的高度在[logN,logN+1]（理論上，極端的情況下可以出現(xiàn)RBTree的高度達(dá)到2*logN因妙，但實(shí)際上很難遇到）痰憎。這樣RBTree的查找時間復(fù)雜度始終保持在O(logN)從而接近于理想的BST。RBTree的刪除和插入操作的時間復(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)就是左旋怒详。

image

RBTree的查找操作

RBTree的查找操作和BST的查找操作是一樣的炉媒。請參考BST的查找操作代碼。

RBTree的插入操作

RBTree的插入與BST的插入方式是一致的昆烁，只不過是在插入過后吊骤，可能會導(dǎo)致樹的不平衡，這時就需要對樹進(jìn)行旋轉(zhuǎn)操作和顏色修復(fù)（在這里簡稱插入修復(fù)）静尼，使得它符合RBTree的定義白粉。

新插入的節(jié)點(diǎn)是紅色的，插入修復(fù)操作如果遇到父節(jié)點(diǎn)的顏色為黑則修復(fù)操作結(jié)束鼠渺。也就是說鸭巴，只有在父節(jié)點(diǎn)為紅色節(jié)點(diǎn)的時候是需要插入修復(fù)操作的。

插入修復(fù)操作分為以下的三種情況拦盹，而且新插入的節(jié)點(diǎn)的父節(jié)點(diǎn)都是紅色的：

1. 叔叔節(jié)點(diǎn)也為紅色鹃祖。
2. 叔叔節(jié)點(diǎn)為空，且祖父節(jié)點(diǎn)掌敬、父節(jié)點(diǎn)和新節(jié)點(diǎn)處于一條斜線上惯豆。
3. 叔叔節(jié)點(diǎn)為空，且祖父節(jié)點(diǎn)奔害、父節(jié)點(diǎn)和新節(jié)點(diǎn)不處于一條斜線上楷兽。

插入操作-case 1

case 1的操作是將父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)與祖父節(jié)點(diǎn)的顏色互換，這樣就符合了RBTRee的定義华临。即維持了高度的平衡芯杀，修復(fù)后顏色也符合RBTree定義的第三條和第四條。下圖中，操作完成后A節(jié)點(diǎn)變成了新的節(jié)點(diǎn)揭厚。如果A節(jié)點(diǎn)的父節(jié)點(diǎn)不是黑色的話却特，則繼續(xù)做修復(fù)操作。

image

插入操作-case 2

case 2的操作是將B節(jié)點(diǎn)進(jìn)行右旋操作筛圆，并且和父節(jié)點(diǎn)A互換顏色裂明。通過該修復(fù)操作RBTRee的高度和顏色都符合紅黑樹的定義。如果B和C節(jié)點(diǎn)都是右節(jié)點(diǎn)的話太援，只要將操作變成左旋就可以了闽晦。

image

插入操作-case 3

case 3的操作是將C節(jié)點(diǎn)進(jìn)行左旋，這樣就從case 3轉(zhuǎn)換成case 2了提岔，然后針對case 2進(jìn)行操作處理就行了仙蛉。case 2操作做了一個右旋操作和顏色互換來達(dá)到目的。如果樹的結(jié)構(gòu)是下圖的鏡像結(jié)構(gòu)碱蒙，則只需要將對應(yīng)的左旋變成右旋荠瘪，右旋變成左旋即可。

image

插入操作的總結(jié)

插入后的修復(fù)操作是一個向root節(jié)點(diǎn)回溯的操作赛惩，一旦牽涉的節(jié)點(diǎn)都符合了紅黑樹的定義哀墓，修復(fù)操作結(jié)束。之所以會向上回溯是由于case 1操作會將父節(jié)點(diǎn)坊秸，叔叔節(jié)點(diǎn)和祖父節(jié)點(diǎn)進(jìn)行換顏色麸祷，有可能會導(dǎo)致祖父節(jié)點(diǎn)不平衡(紅黑樹定義3)。這個時候需要對祖父節(jié)點(diǎn)為起點(diǎn)進(jìn)行調(diào)節(jié)（向上回溯）褒搔。

祖父節(jié)點(diǎn)調(diào)節(jié)后如果還是遇到它的祖父顏色問題阶牍，操作就會繼續(xù)向上回溯，直到root節(jié)點(diǎn)為止星瘾，根據(jù)定義root節(jié)點(diǎn)永遠(yuǎn)是黑色的走孽。在向上的追溯的過程中，針對插入的3中情況進(jìn)行調(diào)節(jié)琳状。直到符合紅黑樹的定義為止磕瓷。直到牽涉的節(jié)點(diǎn)都符合了紅黑樹的定義，修復(fù)操作結(jié)束念逞。

如果上面的3中情況如果對應(yīng)的操作是在右子樹上困食，做對應(yīng)的鏡像操作就是了。

RBTree的刪除操作

刪除操作首先需要做的也是BST的刪除操作翎承，刪除操作會刪除對應(yīng)的節(jié)點(diǎn)硕盹，如果是葉子節(jié)點(diǎn)就直接刪除，如果是非葉子節(jié)點(diǎn)叨咖，會用對應(yīng)的中序遍歷的后繼節(jié)點(diǎn)來頂替要刪除節(jié)點(diǎn)的位置瘩例。刪除后就需要做刪除修復(fù)操作啊胶，使的樹符合紅黑樹的定義，符合定義的紅黑樹高度是平衡的垛贤。

刪除修復(fù)操作在遇到被刪除的節(jié)點(diǎn)是紅色節(jié)點(diǎn)或者到達(dá)root節(jié)點(diǎn)時焰坪，修復(fù)操作完畢。

刪除修復(fù)操作是針對刪除黑色節(jié)點(diǎn)才有的聘惦，當(dāng)黑色節(jié)點(diǎn)被刪除后會讓整個樹不符合RBTree的定義的第四條某饰。需要做的處理是從兄弟節(jié)點(diǎn)上借調(diào)黑色的節(jié)點(diǎn)過來，如果兄弟節(jié)點(diǎn)沒有黑節(jié)點(diǎn)可以借調(diào)的話善绎，就只能往上追溯露乏，將每一級的黑節(jié)點(diǎn)數(shù)減去一個，使得整棵樹符合紅黑樹的定義涂邀。

刪除操作的總體思想是從兄弟節(jié)點(diǎn)借調(diào)黑色節(jié)點(diǎn)使樹保持局部的平衡，如果局部的平衡達(dá)到了箱锐，就看整體的樹是否是平衡的比勉，如果不平衡就接著向上追溯調(diào)整。

刪除修復(fù)操作分為四種情況(刪除黑節(jié)點(diǎn)后)：

1. 待刪除的節(jié)點(diǎn)的兄弟節(jié)點(diǎn)是紅色的節(jié)點(diǎn)驹止。
2. 待刪除的節(jié)點(diǎn)的兄弟節(jié)點(diǎn)是黑色的節(jié)點(diǎn)浩聋，且兄弟節(jié)點(diǎn)的子節(jié)點(diǎn)都是黑色的。
3. 待調(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)是黑色的。
4. 待調(diào)整的節(jié)點(diǎn)的兄弟節(jié)點(diǎn)是黑色的節(jié)點(diǎn)撤卢，且右子節(jié)點(diǎn)是是紅色的(兄弟節(jié)點(diǎn)在右邊)环凿，如果兄弟節(jié)點(diǎn)在左邊，則就是對應(yīng)的就是左節(jié)點(diǎn)是紅色的放吩。

刪除操作-case 1

由于兄弟節(jié)點(diǎn)是紅色節(jié)點(diǎn)的時候智听，無法借調(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)換之后就會變成后面的case 2悔雹，case 3，或者case 4進(jìn)行處理了腌零。上升操作需要對C做一個左旋操作梯找，如果是鏡像結(jié)構(gòu)的樹只需要做對應(yīng)的右旋操作即可益涧。

之所以要做case 1操作是因?yàn)樾值芄?jié)點(diǎn)是紅色的，無法借到一個黑節(jié)點(diǎn)來填補(bǔ)刪除的黑節(jié)點(diǎn)闲询。

image

刪除操作-case 2

case 2的刪除操作是由于兄弟節(jié)點(diǎn)可以消除一個黑色節(jié)點(diǎn)久免，因?yàn)樾值芄?jié)點(diǎn)和兄弟節(jié)點(diǎn)的子節(jié)點(diǎn)都是黑色的，所以可以將兄弟節(jié)點(diǎn)變紅阎姥，這樣就可以保證樹的局部的顏色符合定義了鸽捻。這個時候需要將父節(jié)點(diǎn)A變成新的節(jié)點(diǎn)，繼續(xù)向上調(diào)整衣赶，直到整顆樹的顏色符合RBTree的定義為止厚满。

case 2這種情況下之所以要將兄弟節(jié)點(diǎn)變紅，是因?yàn)槿绻研值芄?jié)點(diǎn)借調(diào)過來遵馆，會導(dǎo)致兄弟的結(jié)構(gòu)不符合RBTree的定義团搞，這樣的情況下只能是將兄弟節(jié)點(diǎn)也變成紅色來達(dá)到顏色的平衡多艇。當(dāng)將兄弟節(jié)點(diǎn)也變紅之后，達(dá)到了局部的平衡了复隆，但是對于祖父節(jié)點(diǎn)來說是不符合定義4的挽拂。這樣就需要回溯到父節(jié)點(diǎn)骨饿，接著進(jìn)行修復(fù)操作。

image

刪除操作-case 3

case 3的刪除操作是一個中間步驟黎侈，它的目的是將左邊的紅色節(jié)點(diǎn)借調(diào)過來闷游，這樣就可以轉(zhuǎn)換成case 4狀態(tài)了，在case 4狀態(tài)下可以將D休吠，E節(jié)點(diǎn)都階段過來业簿，通過將兩個節(jié)點(diǎn)變成黑色來保證紅黑樹的整體平衡梅尤。

之所以說case-3是一個中間狀態(tài)，是因?yàn)楦鶕?jù)紅黑樹的定義來說，下圖并不是平衡的矾湃，他是通過case 2操作完后向上回溯出現(xiàn)的狀態(tài)堕澄。之所以會出現(xiàn)case 3和后面的case 4的情況蛙紫，是因?yàn)榭梢酝ㄟ^借用侄子節(jié)點(diǎn)的紅色，變成黑色來符合紅黑樹定義4僵驰。

image

刪除操作-case 4

Case 4的操作是真正的節(jié)點(diǎn)借調(diào)操作蒜茴，通過將兄弟節(jié)點(diǎn)以及兄弟節(jié)點(diǎn)的右節(jié)點(diǎn)借調(diào)過來浆西，并將兄弟節(jié)點(diǎn)的右子節(jié)點(diǎn)變成紅色來達(dá)到借調(diào)兩個黑節(jié)點(diǎn)的目的近零，這樣的話抄肖，整棵樹還是符合RBTree的定義的漓摩。

Case 4這種情況的發(fā)生只有在待刪除的節(jié)點(diǎn)的兄弟節(jié)點(diǎn)為黑陈瘦，且子節(jié)點(diǎn)不全部為黑痊项，才有可能借調(diào)到兩個節(jié)點(diǎn)來做黑節(jié)點(diǎn)使用，從而保持整棵樹都符合紅黑樹的定義皱埠。

image

刪除操作的總結(jié)

紅黑樹的刪除操作是最復(fù)雜的操作边器，復(fù)雜的地方就在于當(dāng)刪除了黑色節(jié)點(diǎn)的時候托修，如何從兄弟節(jié)點(diǎn)去借調(diào)節(jié)點(diǎn)睦刃，以保證樹的顏色符合定義。由于紅色的兄弟節(jié)點(diǎn)是沒法借調(diào)出黑節(jié)點(diǎn)的际长，這樣只能通過選擇操作讓他上升到父節(jié)點(diǎn)兴泥，而由于它是紅節(jié)點(diǎn)搓彻，所以它的子節(jié)點(diǎn)就是黑的，可以借調(diào)竭沫。

對于兄弟節(jié)點(diǎn)是黑色節(jié)點(diǎn)的可以分成3種情況來處理骑篙，當(dāng)所以的兄弟節(jié)點(diǎn)的子節(jié)點(diǎn)都是黑色節(jié)點(diǎn)時靶端，可以直接將兄弟節(jié)點(diǎn)變紅，這樣局部的紅黑樹顏色是符合定義的脏榆。但是整顆樹不一定是符合紅黑樹定義的须喂，需要往上追溯繼續(xù)調(diào)整。

對于兄弟節(jié)點(diǎn)的子節(jié)點(diǎn)為左紅右黑或者 (全部為紅仔役，右紅左黑)這兩種情況又兵，可以先將前面的情況通過選擇轉(zhuǎn)換為后一種情況卒废，在后一種情況下摔认，因?yàn)樾值芄?jié)點(diǎn)為黑，兄弟節(jié)點(diǎn)的右節(jié)點(diǎn)為紅页屠，可以借調(diào)出兩個節(jié)點(diǎn)出來做黑節(jié)點(diǎn)蓖柔，這樣就可以保證刪除了黑節(jié)點(diǎn)况鸣，整棵樹還是符合紅黑樹的定義的竹观，因?yàn)楹谏?jié)點(diǎn)的個數(shù)沒有改變臭增。

紅黑樹的刪除操作是遇到刪除的節(jié)點(diǎn)為紅色，或者追溯調(diào)整到了root節(jié)點(diǎn)列牺，這時刪除的修復(fù)操作完畢瞎领。

RBTree的Java實(shí)現(xiàn)

點(diǎn)擊閱讀原文，查看代碼詳情震放。

代碼調(diào)試的時候殿遂，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)

括號左邊表示元素的內(nèi)容乙各。括號內(nèi)的第一個元素表示顏色觅丰，B表示black，R表示red蜕企；第二個元素表示父元素的值轻掩；第三個元素表示左右懦底，LE表示在父元素的左邊聚唐。RI表示在父元素的右邊。

第一個元素d是root節(jié)點(diǎn)扮惦，由于它沒有父節(jié)點(diǎn)崖蜜，所以括號內(nèi)只有一個元素客峭。

總結(jié)

作為平衡二叉查找樹里面眾多的實(shí)現(xiàn)之一舔琅，紅黑樹無疑是最簡潔、實(shí)現(xiàn)最為簡單的鼠锈。紅黑樹通過引入顏色的概念购笆，通過顏色這個約束條件的使用來保持樹的高度平衡。作為平衡二叉查找樹样傍，旋轉(zhuǎn)是一個必不可少的操作衫哥。通過旋轉(zhuǎn)可以降低樹的高度襟锐，在紅黑樹里面還可以轉(zhuǎn)換顏色粮坞。

紅黑樹里面的插入和刪除的操作比較難理解莫杈，這時要注意記住一點(diǎn)：操作之前紅黑樹是平衡的，顏色是符合定義的媳叨。在操作的時候就需要向兄弟節(jié)點(diǎn)糊秆、父節(jié)點(diǎn)议双、侄子節(jié)點(diǎn)借調(diào)和互換顏色聋伦，要達(dá)到這個目的界睁，就需要不斷的進(jìn)行旋轉(zhuǎn)翻斟。所以紅黑樹的插入刪除操作需要不停的旋轉(zhuǎn)，一旦借調(diào)了別的節(jié)點(diǎn)，刪除和插入的節(jié)點(diǎn)就會達(dá)到局部的平衡（局部符合紅黑樹的定義）腻扇，但是被借調(diào)的節(jié)點(diǎn)就不會平衡了幼苛，這時就需要以被借調(diào)的節(jié)點(diǎn)為起點(diǎn)繼續(xù)進(jìn)行調(diào)整舶沿，直到整棵樹都是平衡的配并。在整個修復(fù)的過程中溉旋，插入具體的分為3種情況，刪除分為4種情況邑闲。

整個紅黑樹的查找监憎，插入和刪除都是O(logN)的鲸阔，原因就是整個紅黑樹的高度是logN迄委，查找從根到葉叙身，走過的路徑是樹的高度，刪除和插入操作是從葉到根的晃痴，所以經(jīng)過的路徑都是logN倘核。

參考文獻(xiàn)

1. Cormen T H, Leiserson C E, Rivest R L, 等. 算法導(dǎo)論（第3版）. 殷建平, 等. 機(jī)械工業(yè)出版社, 2012.
2. Sedgewick R, Wayne K. 算法（第4版）. 謝路云 譯. 人民郵電出版社, 2012.
3. Weiss M A. 數(shù)據(jù)結(jié)構(gòu)與算法分析（第2版）. 馮舜璽 譯. 機(jī)械工業(yè)出版社, 2004.
4. Knuth D E. 計(jì)算機(jī)程序設(shè)計(jì)藝術(shù) 卷3：排序與查找（英文版 第2版）. 人民郵電出版社, 2010.

原文地址:https://cloud.tencent.com/developer/article/1058189