紅黑樹（英語：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是嚴格的平衡二叉樹瞬痘，但是插入和刪除的性能較差，所以在實際生產(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ì)，后面需要正沉袅浚回來查看：
- 每個節(jié)點要么是黑的晒哄，要么是紅的
- 根節(jié)點是黑的
- 葉節(jié)點是黑的
- 如果一個節(jié)點是紅的，他的兩個兒子節(jié)點都是黑的
- 對于任一節(jié)點而言肪获，其到葉節(jié)點樹尾端NIL指針的每一條路徑都包含相同數(shù)目的黑節(jié)點
上圖是一棵典型的紅黑樹寝凌，紅黑樹的5條特性確保了從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長，使得整棵樹大致上是平衡的孝赫。樹上的增刪改查操作的最壞情況時間都與樹的高度成正比较木，所以紅黑樹在最壞情況下也是高效的。
在紅黑樹中一般用黑的NIL節(jié)點表示葉節(jié)點青柄，不包含值伐债，只是標志該分支結(jié)束，有時候繪圖中會直接省略致开。
在正式介紹紅黑樹插入和刪除操作前峰锁，需要先了解紅黑樹的旋轉(zhuǎn)操作。
RBTree的旋轉(zhuǎn)操作
當在含n個關(guān)鍵字的紅黑樹上進行insert和delete操作時双戳，修改后的樹可能不滿足上面給出的5個紅黑樹的基本特性虹蒋，所以需要改變樹中的某些節(jié)點的顏色以及指針結(jié)構(gòu)。
這些指針結(jié)構(gòu)的修改是通過旋轉(zhuǎn)完成的飒货，旋轉(zhuǎn)分為左旋和右旋:
當在某個節(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 ：當前節(jié)點的父節(jié)點是紅色愕宋，且祖父節(jié)點的另一個子節(jié)點（叔叔節(jié)點）也是紅色
此時，我們只考慮當前節(jié)點是父節(jié)點的左兒子结榄，因為當前節(jié)點和父節(jié)點都是紅色中贝，不滿足紅黑樹的特性4 （如果一個節(jié)點是紅的，他的兩個兒子節(jié)點都是黑的）臼朗。
對策 :把父節(jié)點和叔叔節(jié)點變黑邻寿，爺爺節(jié)點涂紅，然后把當前節(jié)點指針給到爺爺依溯，讓爺爺節(jié)點那層繼續(xù)循環(huán)老厌，接受紅黑樹特性檢測。
新插入節(jié)點1黎炉，父親2和叔叔6都是紅的，所以把2和6都變成黑的醋拧， 爺爺變成紅的慷嗜。
情況2： 當前節(jié)點的父節(jié)點是紅的淀弹，叔叔節(jié)點是黑的，當前節(jié)點是父節(jié)點的右子樹庆械。
對策：當前節(jié)點的父節(jié)點作為新的當前節(jié)點薇溃，以新當前指點為支點左旋
接著上面的情況1， 在情況1的操作之后缭乘，當前節(jié)點為4沐序， 但是4的父節(jié)點3還是紅的，仍然不滿足紅黑樹的特性4堕绩， 由于叔叔節(jié)點7是黑的策幼，且4為3的右兒子，所以滿足情況2奴紧，這時候把當前節(jié)點轉(zhuǎn)移到3特姐，以3為支點左旋。4變?yōu)闋敔?的新左兒子黍氮，而原來的3下去了唐含，成為4的左兒子。4原有的左兒子（2-1分支）給3做了右兒子沫浆。
情況3：當前節(jié)點的父節(jié)點是紅色捷枯，叔叔節(jié)點是黑色，且當前節(jié)點是其父節(jié)點的左兒子
對策： 父節(jié)點變黑专执，祖父變紅铜靶，以祖父節(jié)點為支點右旋
接著上面的情況2， 當前節(jié)點變成了3他炊，由于父節(jié)點4為紅争剿，叔叔節(jié)點7 為黑，且4為5的左兒子痊末，所以滿足情況3蚕苇，所以需要將父節(jié)點4變黑，祖父5變紅凿叠，并且右旋涩笤，右旋后，4 的右兒子6跟了5做了左兒子盒件，5成了4的右兒子蹬碧。如圖所示：
這樣紅黑樹重新恢復(fù)了平衡。上面的例子里正好遇到了三種基本情況炒刁，實際操作中也許一步就成功了恩沽，簡化的來看，也就是下面三種基本情況：
case1 :
case2 :
case3 :
當前節(jié)點為父節(jié)點的右節(jié)點的時候里伯，先旋轉(zhuǎn)成為左子，即case2的樣子渤闷，再右旋疾瓮。
修復(fù)操作整體來說是一個向上回溯的過程，就拿我們舉得例子來說飒箭，情況1操作后狼电，當前節(jié)點向上移到了4， 此時又會檢測4 和它的父節(jié)點之間性質(zhì)是否符合紅黑樹的5條特性弦蹂，不對的話繼續(xù)修復(fù)紅黑樹肩碟，直到當前節(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ì)就會被改變迷帜，此時我們需要做修正。
當黑色節(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ì)即可赶袄。
- 如果當前節(jié)點時紅+黑色
直接把當前節(jié)點染成黑色，此時紅黑樹性質(zhì)全部恢復(fù) - 如果當前節(jié)點時黑+黑且是根節(jié)點抠藕，此時什么都不用做饿肺，直接結(jié)束
- 如果當前節(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é)點為新的當前節(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é)點的目的，這樣的話谭期，整棵樹還是符合紅黑樹的定義的
