紅黑樹（英語：Red–black tree）是一種自平衡二叉查找樹，是在計算機科學(xué)中用到的一種數(shù)據(jù)結(jié)構(gòu)，典型的用途是實現(xiàn)關(guān)聯(lián)數(shù)組。在了解紅黑樹之前我們需要簡述一下二叉查找樹。
BST
二叉查找樹，也稱有序二叉樹，是指一棵空樹或者具有以下性質(zhì)的二叉樹：
- 左子節(jié)點的值比父節(jié)點小
- 右子節(jié)點的值比父節(jié)點大
- 任意節(jié)點的左右字樹也分別為二叉查找樹
- 沒有鍵值相等的點
在理想情況下，二叉查找樹增刪改查的時間復(fù)雜度為O(logN)，但是若是二叉樹極度不平衡，比如下圖這樣形成了一個線性鏈后，就會產(chǎn)生最壞運行情況O(N).
基于BST存在的問題，平衡二叉樹產(chǎn)生了，典型的有AVL樹和紅黑樹，因為AVL是嚴(yán)格的平衡二叉樹，但是插入和刪除的性能較差，所以在實際生產(chǎn)環(huán)境中不如紅黑樹應(yīng)用廣泛。
RBTree
紅黑樹的應(yīng)用非常廣泛，常見的函數(shù)庫，如C++中的map，multimap,以及Java中的TreeMap，TreeSet， Java8中的HashMap的實現(xiàn)也采用了紅黑樹。
紅黑樹從本質(zhì)上來說就是一顆二叉查找樹，但是在二叉樹的基礎(chǔ)上增加了著色相關(guān)的性質(zhì)，使得紅黑樹可以保證相對平衡，從而保證紅黑樹的增刪改查的時間復(fù)雜度最壞也能達到O(log N)。
下面是紅黑樹最重要的5條性質(zhì)，后面需要正?；貋聿榭矗?/p>
- 每個節(jié)點要么是黑的，要么是紅的
- 根節(jié)點是黑的
- 葉節(jié)點是黑的
- 如果一個節(jié)點是紅的，他的兩個兒子節(jié)點都是黑的
- 對于任一節(jié)點而言，其到葉節(jié)點樹尾端NIL指針的每一條路徑都包含相同數(shù)目的黑節(jié)點
上圖是一棵典型的紅黑樹，紅黑樹的5條特性確保了從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長，使得整棵樹大致上是平衡的。樹上的增刪改查操作的最壞情況時間都與樹的高度成正比，所以紅黑樹在最壞情況下也是高效的。
在紅黑樹中一般用黑的NIL節(jié)點表示葉節(jié)點，不包含值，只是標(biāo)志該分支結(jié)束，有時候繪圖中會直接省略。
在正式介紹紅黑樹插入和刪除操作前，需要先了解紅黑樹的旋轉(zhuǎn)操作。
RBTree的旋轉(zhuǎn)操作
當(dāng)在含n個關(guān)鍵字的紅黑樹上進行insert和delete操作時，修改后的樹可能不滿足上面給出的5個紅黑樹的基本特性，所以需要改變樹中的某些節(jié)點的顏色以及指針結(jié)構(gòu)。
這些指針結(jié)構(gòu)的修改是通過旋轉(zhuǎn)完成的，旋轉(zhuǎn)分為左旋和右旋:
當(dāng)在某個節(jié)點x上做左旋時，我們假設(shè)它的右孩子是y節(jié)點并且不為NIL。左旋以x到y(tǒng)之間的軸為支撐，左旋后，y成為該局部新的根，x成為y的做孩子，而y的左孩子成為x的右孩子，即圖中的β。我們以一段偽代碼說明左旋的過程:
y<-right[x] //把x的右兒子保存為y
right[x]<-left[y] //把y的左兒子給x作為右兒子
p[left[y]]<-x //把x設(shè)為y的左兒子的爸爸，這一步與上一步對應(yīng)，因為指針都是雙向的
p[y]<-p[x] //把x的爸爸設(shè)定為y的爸爸
if p[x]=nil[T] //如果x的爸爸本來就是空的
then root[T]<-y //那么y就變成了根節(jié)點
else if x=left[p[x]] //否則，如果原來x是它爸爸的左兒子
then left[p[x]]<-y //就把y設(shè)為原來x爸爸的左兒子
else right[p[x]]<-y //不然就把y設(shè)為原來x爸爸的右兒子
left[y]<-x //x這時候轉(zhuǎn)下來成為y的左兒子
p[x]<-y //y 也就成了x的爸爸了
在實際的樹中，旋轉(zhuǎn)如下所示：
旋轉(zhuǎn)后，18代替了11成為了7的右兒子，11，成了18的左兒子，18原先的兒子，即以14為根節(jié)點的左子樹成了11的右兒子，如下所示：
右旋操作與左旋類似，讀者們可以自行試著寫出偽代碼。
RBTree的插入操作
紅黑樹的插入與BST的插入方式是一樣的，也是通過不斷比較大小，插入到合適位置，只不過插入后需要做調(diào)整，以滿足紅黑樹的5條特性。
先看一下BST的插入代碼：
public BinaryNode<T> insert(T t,BinaryNode<T> node)
{
if(node==null)
{
return new BinaryNode<T>(t, null, null);
}
int result = t.compareTo(node.data);
if(result<0)
node.left= insert(t,node.left);
else if(result>0)
node.right= insert(t,node.right);
else
;//doNothing
return node;
}
新插入的節(jié)點總是設(shè)為紅色的，所以如果父節(jié)點為黑色，就不需要修復(fù)，因為沒有任何性質(zhì)被改變，所以只有在父節(jié)點為紅色節(jié)點時需要做修復(fù)操作。
修復(fù)操作一共分為3種情況：
情況1 ：當(dāng)前節(jié)點的父節(jié)點是紅色，且祖父節(jié)點的另一個子節(jié)點（叔叔節(jié)點）也是紅色
此時，我們只考慮當(dāng)前節(jié)點是父節(jié)點的左兒子，因為當(dāng)前節(jié)點和父節(jié)點都是紅色，不滿足紅黑樹的特性4 （如果一個節(jié)點是紅的，他的兩個兒子節(jié)點都是黑的）。
對策 :把父節(jié)點和叔叔節(jié)點變黑，爺爺節(jié)點涂紅，然后把當(dāng)前節(jié)點指針給到爺爺，讓爺爺節(jié)點那層繼續(xù)循環(huán)，接受紅黑樹特性檢測。
新插入節(jié)點1，父親2和叔叔6都是紅的，所以把2和6都變成黑的， 爺爺變成紅的。
情況2： 當(dāng)前節(jié)點的父節(jié)點是紅的，叔叔節(jié)點是黑的，當(dāng)前節(jié)點是父節(jié)點的右子樹。
對策：當(dāng)前節(jié)點的父節(jié)點作為新的當(dāng)前節(jié)點，以新當(dāng)前指點為支點左旋
接著上面的情況1， 在情況1的操作之后，當(dāng)前節(jié)點為4， 但是4的父節(jié)點3還是紅的，仍然不滿足紅黑樹的特性4， 由于叔叔節(jié)點7是黑的，且4為3的右兒子，所以滿足情況2，這時候把當(dāng)前節(jié)點轉(zhuǎn)移到3，以3為支點左旋。4變?yōu)闋敔?的新左兒子，而原來的3下去了，成為4的左兒子。4原有的左兒子（2-1分支）給3做了右兒子。
情況3：當(dāng)前節(jié)點的父節(jié)點是紅色，叔叔節(jié)點是黑色，且當(dāng)前節(jié)點是其父節(jié)點的左兒子
對策： 父節(jié)點變黑，祖父變紅，以祖父節(jié)點為支點右旋
接著上面的情況2， 當(dāng)前節(jié)點變成了3，由于父節(jié)點4為紅，叔叔節(jié)點7 為黑，且4為5的左兒子，所以滿足情況3，所以需要將父節(jié)點4變黑，祖父5變紅，并且右旋，右旋后，4 的右兒子6跟了5做了左兒子，5成了4的右兒子。如圖所示：
這樣紅黑樹重新恢復(fù)了平衡。上面的例子里正好遇到了三種基本情況，實際操作中也許一步就成功了，簡化的來看，也就是下面三種基本情況：
case1 :
case2 :
case3 :
當(dāng)前節(jié)點為父節(jié)點的右節(jié)點的時候，先旋轉(zhuǎn)成為左子，即case2的樣子，再右旋。
修復(fù)操作整體來說是一個向上回溯的過程，就拿我們舉得例子來說，情況1操作后，當(dāng)前節(jié)點向上移到了4， 此時又會檢測4 和它的父節(jié)點之間性質(zhì)是否符合紅黑樹的5條特性，不對的話繼續(xù)修復(fù)紅黑樹，直到當(dāng)前節(jié)點轉(zhuǎn)移到root節(jié)點，且root節(jié)點為黑色，修復(fù)操作結(jié)束。
RBTree的刪除操作
刪除操作首先也需要做普通BST的刪除操作，刪除操作會刪除對應(yīng)的節(jié)點，葉子節(jié)點就會直接刪除，如果是非葉子節(jié)點，就會用中序遍歷的后繼節(jié)點來頂替要刪除的節(jié)點，有的書上也會用前驅(qū)節(jié)點來頂替。刪除后也需要做修復(fù)操作，來滿足紅黑樹的特性。
首先也是看一下BST刪除節(jié)點的代碼：
public BinaryNode<T> remove(T t,BinaryNode<T> node)
{
if(node == null)
return node;//沒有找到,doNothing
int result = t.compareTo(node.data);
if(result>0)
node.right = remove(t,node.right);
else if(result<0)
node.left = remove(t,node.left);
else if(node.left!=null&&node.right!=null)
{ //待刪除節(jié)點有兩個兒子節(jié)點時，用右兒子中的最小元素填充待刪除節(jié)點
node.data = findMin(node.right).data;
node.right = remove(node.data,node.right);
}
else //只有一個兒子的時候，把父節(jié)點的兒子指針指向兒子的該獨生子
node = (node.left!=null)?node.left:node.right;
return node;
}
刪除修復(fù)操作在遇到被刪除的節(jié)點是紅色節(jié)點或者到達root節(jié)點時，修復(fù)操作完畢。
在刪除一個節(jié)點后，如果刪除的節(jié)點時紅色節(jié)點，那么紅黑樹的性質(zhì)并不會被影響，此時不需要修正，如果刪除的是黑色節(jié)點，原紅黑樹的性質(zhì)就會被改變，此時我們需要做修正。
當(dāng)黑色節(jié)點被刪除后，假設(shè)該節(jié)點為y，會產(chǎn)生3個問題：
- 如果y原來是根節(jié)點，而y的一個紅色孩子成為新的根，則違反了性質(zhì)2
- 如果y的子節(jié)點和y的父節(jié)點都是紅色，那么y被刪除后，兩個連續(xù)的紅色節(jié)點連接起來，違反了性質(zhì)4
- 刪除y將導(dǎo)致先前包含y的任何路徑上的黑節(jié)點個數(shù)少1，性質(zhì)5被破壞
現(xiàn)在我們假設(shè)，頂替刪除節(jié)點的那個后來節(jié)點，繼承了被刪除的黑色節(jié)點的那層黑色，也就是說頂替的節(jié)點具有雙重顏色，如果原來是黑色，那么現(xiàn)在就是黑+黑，如果原來是紅色，現(xiàn)在就是紅+黑。因為有了這層額外的黑色，所以性質(zhì)5還是能保持的，現(xiàn)在只需要恢復(fù)它的性質(zhì)即可。
- 如果當(dāng)前節(jié)點時紅+黑色
直接把當(dāng)前節(jié)點染成黑色，此時紅黑樹性質(zhì)全部恢復(fù) - 如果當(dāng)前節(jié)點時黑+黑且是根節(jié)點，此時什么都不用做，直接結(jié)束
- 如果當(dāng)前節(jié)點時黑+黑，但是不是根節(jié)點，那么又可以分為以下4種情況
設(shè)刪除節(jié)點為x節(jié)點
情況1：x節(jié)點時黑+黑，且x的兄弟節(jié)點是紅色（x的父節(jié)點和兄弟節(jié)點的子節(jié)點都是黑色）
因為兄弟節(jié)點7必須有黑色孩子，我們可以改變4和7的顏色，再對4做一次左旋，而且紅黑性質(zhì)繼續(xù)保存。完成這兩個操作后，盡管所有路徑上黑色節(jié)點的數(shù)目沒有改變，但現(xiàn)在刪除節(jié)點有了一個黑色的兄弟和一個紅色的父親（它的新兄弟是黑色因為它是原先紅7的一個兒子），所以我們可以接下去按情形2、情形3或情形4來處理。
情況2：x節(jié)點時黑+黑，x的兄弟節(jié)點時黑色（x的兄弟節(jié)點的兩個孩子都是黑色）
此時我們把x的兄弟節(jié)點轉(zhuǎn)變?yōu)榧t色，設(shè)置x的父節(jié)點為新的當(dāng)前節(jié)點。
其實這樣做的思想是把原先x中的一個黑色屬性上移。原先的x變成單純的黑節(jié)點，而它的父節(jié)點4此時變成了紅+黑，如果4原來就是黑，那么此時變成黑+黑。此時左邊分支的黑節(jié)點數(shù)沒有變化，但是右邊4,7那一條分支，黑節(jié)點數(shù)增加了1，因為此時4也包含黑屬性，所以需要通過減1個黑色節(jié)點，因為兄弟節(jié)點7的子節(jié)點都是黑的，所以直接把7 變成紅的。
經(jīng)過上面的步驟，黑色屬性轉(zhuǎn)移到4中去了，這時候繼續(xù)對4進行處理。
情況3：x節(jié)點是黑+黑節(jié)點，x的兄弟節(jié)點時黑色（x的兄弟節(jié)點的左兒子是紅，右兒子是黑）
此時我們把x的兄弟節(jié)點的左兒子設(shè)為黑色，將兄弟節(jié)點設(shè)為紅色，再對兄弟節(jié)點進行右旋。并且重新設(shè)置旋轉(zhuǎn)后x的兄弟節(jié)點，此時是5.
其實這一步只是一個中間狀態(tài)，并且不是平衡的，目的是為了得到情況4的狀態(tài)
情況4：x節(jié)點是黑+黑節(jié)點，x的兄弟節(jié)點時黑色（x的兄弟節(jié)點的右兒子是紅，左兒子隨意）
此時，把x的父節(jié)點的顏色賦給x的兄弟節(jié)點，把父節(jié)點設(shè)為黑色，將x的兄弟節(jié)點的右子節(jié)點設(shè)為黑色，再對x的父節(jié)點進行左旋。這一步操作的真正的節(jié)點借調(diào)操作，通過將兄弟節(jié)點以及兄弟節(jié)點的右節(jié)點借調(diào)過來，并將兄弟節(jié)點的右子節(jié)點變成紅色來達到借調(diào)兩個黑節(jié)點的目的，這樣的話，整棵樹還是符合紅黑樹的定義的
