紅黑樹筆記

紅黑樹是平衡二叉查找樹的一種稚字。為了深入理解紅黑樹豌鹤，我們需要從二叉查找樹開始講起沪袭。

BST

二叉查找樹（Binary Search Tree艇抠，簡稱BST）是一棵二叉樹默怨，它的左子節(jié)點的值比父節(jié)點的值要小讯榕，右節(jié)點的值要比父節(jié)點的值大。它的高度決定了它的查找效率匙睹。

在理想的情況下愚屁，二叉查找樹增刪查改的時間復(fù)雜度為O(logN)（其中N為節(jié)點數(shù)），最壞的情況下為O(N)痕檬。

BST存在傾斜的問題

平衡的BST：

傾斜的BST:

publicclassBstTest{staticclassNode{publicStringcontent;publicNodeparent;publicNodeleft;publicNoderight;publicNode(Stringcontent) {this.content=content;? ? ? ? }? ? }publicNoderoot;// BST的查找操作publicNodesearch(Stringcontent) {Noder=root;while(r!=null) {if(r.content.equals(content)) {returnr;}elseif(content.compareTo(r.content)>1) {r=r.right;}elseif(content.compareTo(r.content)<=1) {r=r.left;? ? ? ? ? ? }? ? ? ? }returnnull;? ? }// BST的插入操作publicvoidinsert(Stringcontent) {NodenewNode=newNode(content);Noder=root;Nodeparent=null;if(r==null) {root=newNode;return;? ? ? ? }while(r!=null) {parent=r;if(newNode.content.compareTo(r.content)>1) {r=r.right;}elseif(newNode.content.compareTo(r.content)<1){r=r.left;}else{r=r.left;? ? ? ? ? ? }? ? ? ? }if(parent.content.compareTo(newNode.content)>1) {parent.left=newNode;newNode.parent=parent;}else{parent.right=newNode;newNode.parent=parent;? ? ? ? }? ? }}

紅黑樹-RBTree

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

紅黑樹（Red-Black Tree朵夏，以下簡稱RBTree）的實際應(yīng)用非常廣泛蔼啦，比如Linux內(nèi)核中的完全公平調(diào)度器、高精度計時器仰猖、ext3文件系統(tǒng)等等捏肢，各種語言的函數(shù)庫如Java的TreeMap和TreeSet奈籽，C++ STL的map、multimap鸵赫、multiset等衣屏。

RBTree也是函數(shù)式語言中最常用的持久數(shù)據(jù)結(jié)構(gòu)之一，在計算幾何中也有重要作用辩棒。值得一提的是狼忱，Java 8中HashMap的實現(xiàn)也因為用RBTree取代鏈表，性能有所提升一睁。

《算法導(dǎo)論》中對于紅黑樹的定義如下：

每個結(jié)點或是紅的钻弄，或是黑的

根節(jié)點是黑的

每個葉結(jié)點是黑的

如果一個結(jié)點是紅的，則它的兩個兒子都是黑的

對每個結(jié)點者吁，從該結(jié)點到其子孫節(jié)點的所有路徑上包含相同數(shù)目的黑結(jié)點

對與第4點窘俺，網(wǎng)上有些定義是：父子節(jié)點之間不能出現(xiàn)兩個連續(xù)的紅節(jié)點，這種定義和《算法導(dǎo)論》中定義的效果是一樣的

RBTree在理論上還是一棵BST樹复凳，但是它在對BST的插入和刪除操作時會維持樹的平衡瘤泪，即保證樹的高度在[logN,logN+1]（理論上，極端的情況下可以出現(xiàn)RBTree的高度達到2*logN育八，但實際上很難遇到）对途。這樣RBTree的查找時間復(fù)雜度始終保持在O(logN)從而接近于理想的BST。RBTree的刪除和插入操作的時間復(fù)雜度也是O(logN)单鹿。RBTree的查找操作就是BST的查找操作掀宋。

插入數(shù)據(jù)

向紅黑樹中插入新的結(jié)點深纲。具體做法是仲锄，將新結(jié)點的 color 賦為紅色，然后以BST的插入方法插入到紅黑樹中去湃鹊。之所以將新插入的結(jié)點的顏色賦為紅色儒喊，是因為：如果設(shè)為黑色，就會導(dǎo)致根到葉子的路徑上有一條路上币呵，多一個額外的黑結(jié)點怀愧，這個是很難調(diào)整的。但是設(shè)為紅色結(jié)點后余赢，可能會導(dǎo)致出現(xiàn)兩個連續(xù)紅色結(jié)點的沖突芯义，那么可以通過顏色調(diào)換和樹旋轉(zhuǎn)來調(diào)整，這樣簡單多了妻柒。

接下來扛拨，討論一下插入以后，紅黑樹的情況举塔。設(shè)要插入的結(jié)點為N绑警，其父結(jié)點為P求泰，其 祖父結(jié)點為G，其父親的兄弟結(jié)點為U（即P和U 是同一個結(jié)點的兩個子結(jié)點）计盒。如果P是黑色的渴频，則整棵樹不必調(diào)整就已經(jīng)滿足了紅黑樹的所有性質(zhì)。如果P是紅色的（可知北启，其父結(jié)點G一定是黑色的）卜朗，則插入N后，違背了紅色結(jié)點只能有黑色孩子的性質(zhì)咕村，需要進行調(diào)整聊替。

調(diào)整時分以下三種情況：

新結(jié)點N的叔叔結(jié)點U是紅色的

處理方式是：將P和U修改為黑色，G修改為紅色培廓。

現(xiàn)在新結(jié)點N有了一個黑色的父結(jié)點P惹悄，因為通過父結(jié)點P或叔父結(jié)點U的任何路徑都必定通過祖父結(jié)點G，在這些路徑上的黑結(jié)點數(shù)目沒有改變肩钠。

但是泣港，紅色的祖父結(jié)點G的父結(jié)點也有可能是紅色的，這就違反了性質(zhì)3价匠。為了解決這個問題当纱，我們從祖父結(jié)點G開始遞歸向上調(diào)整顏色。如圖2

新結(jié)點N的叔叔結(jié)點U是黑色的踩窖，且N是左孩子坡氯。

處理方式：對祖父結(jié)點G進行一次右旋轉(zhuǎn)

在旋轉(zhuǎn)后產(chǎn)生的樹中，以前的父結(jié)點P現(xiàn)在是新結(jié)點N和以前的祖父節(jié)點G的父結(jié)點洋腮，然后交換以前的父結(jié)點P和祖父結(jié)點G的顏色箫柳，結(jié)果仍滿足紅黑樹性質(zhì)。如圖 2.15啥供。在(b)中悯恍，虛線代表原來的指針，實線代表旋轉(zhuǎn)過后的指針伙狐。所謂旋轉(zhuǎn)就是改變圖中所示的兩個指針的值即可涮毫。當然，在實際應(yīng)用中贷屎，還有父指針p也需要修改罢防，這里為了圖示的簡潔而省略掉了。

新結(jié)點N的叔叔結(jié)點U是黑色的唉侄，且N是右孩子咒吐。

處理方式：對P進行一次左旋轉(zhuǎn)，就把問題轉(zhuǎn)化成了第二種情況。如圖 2.16所示渤滞。

紅黑樹插入數(shù)據(jù)的代碼與二叉查找樹是相同的贬墩，只是在插入以后，會對不滿足紅黑樹性質(zhì)的結(jié)點進行調(diào)整妄呕。

HashMap中紅黑樹的插入操作

static<K,V>TreeNode<K,V>balanceInsertion(TreeNode<K,V>root,TreeNode<K,V>x) {// 新節(jié)點默認為紅色x.red=true;// xp表示x的父結(jié)點陶舞，xpp表示x的祖父結(jié)點，xppl表示xpp的左孩子結(jié)點绪励，xppr表示xpp的右孩子結(jié)點for(TreeNode<K,V>xp,xpp,xppl,xppr;;) {// 如果x沒有父結(jié)點肿孵，則表示x是第一個結(jié)點，自動為根節(jié)點疏魏，根節(jié)點為黑色if((xp=x.parent)==null) {x.red=false;returnx;? ? ? ? }// 如果父結(jié)點不是紅色（就是黑色）停做，或者x沒有祖父節(jié)點，那么就證明x是第二層節(jié)點大莫，父節(jié)點為根節(jié)點// 這種情況無需就行操作elseif(!xp.red||(xpp=xp.parent)==null)returnroot;? ? ? ? // 進入到這里蛉腌，表示x的父節(jié)點為紅色? ? ? ? // 如果x的父節(jié)點是祖父結(jié)點的左孩子if(xp==(xppl=xpp.left)) {// 祖父結(jié)點的右孩子，也就是x的叔叔節(jié)點不為空只厘，且為紅色if((xppr=xpp.right)!=null&&xppr.red) {// 父節(jié)點和叔叔節(jié)點都為紅色烙丛，只需要變色，且將x替換為祖父節(jié)點然后進行遞歸xppr.red=false;xp.red=false;xpp.red=true;x=xpp;? ? ? ? ? ? }// 如果叔叔節(jié)點為空羔味，或者為黑色else{// 如果x節(jié)點為xp的右孩子if(x==xp.right) {// 先進行左旋河咽，并且把x替換為xp進行遞歸，在左旋的過程中產(chǎn)生了新的root節(jié)點root=rotateLeft(root,x=xp);// x替換后赋元，修改xp和xppxpp=(xp=x.parent)==null?null:xp.parent;? ? ? ? ? ? ? ? }// 如果x本來是左孩子忘蟹，或者已經(jīng)經(jīng)過了上面的左旋之后，進行變色加右旋if(xp!=null) {xp.red=false;if(xpp!=null) {xpp.red=true;root=rotateRight(root,xpp);? ? ? ? ? ? ? ? ? ? }? ? ? ? ? ? ? ? }? ? ? ? ? ? }? ? ? ? }// 如果x的父節(jié)點是祖父結(jié)點的右孩子else{if(xppl!=null&&xppl.red) {xppl.red=false;xp.red=false;xpp.red=true;x=xpp;? ? ? ? ? ? }else{if(x==xp.left) {root=rotateRight(root,x=xp);xpp=(xp=x.parent)==null?null:xp.parent;? ? ? ? ? ? ? ? }if(xp!=null) {xp.red=false;if(xpp!=null) {xpp.red=true;root=rotateLeft(root,xpp);? ? ? ? ? ? ? ? ? ? }? ? ? ? ? ? ? ? }? ? ? ? ? ? }? ? ? ? }? ? }}

HashMap中紅黑樹的左右旋操作

static<K,V>TreeNode<K,V>rotateLeft(TreeNode<K,V>root,TreeNode<K,V>p) {// pp是祖父結(jié)點// p是待旋轉(zhuǎn)結(jié)點// r是p的右孩子結(jié)點// rl是r的左孩子結(jié)點TreeNode<K,V>r,pp,rl;if(p!=null&&(r=p.right)!=null) {// 如果rl不為空搁凸，則設(shè)置p.right=rlif((rl=p.right=r.left)!=null)rl.parent=p;// 如果祖父結(jié)點為null媚值，那么r設(shè)置為黑色，r左旋之后即為root節(jié)點if((pp=r.parent=p.parent)==null)(root=r).red=false;// 如果待旋轉(zhuǎn)結(jié)點是左孩子節(jié)點elseif(pp.left==p)pp.left=r;// 如果待旋轉(zhuǎn)結(jié)點為右孩子elsepp.right=r;r.left=p;p.parent=r;? ? }returnroot;}static<K,V>TreeNode<K,V>rotateRight(TreeNode<K,V>root,TreeNode<K,V>p) {TreeNode<K,V>l,pp,lr;if(p!=null&&(l=p.left)!=null) {if((lr=p.left=l.right)!=null)lr.parent=p;if((pp=l.parent=p.parent)==null)(root=l).red=false;elseif(pp.right==p)pp.right=l;elsepp.left=l;l.right=p;p.parent=l;? ? }returnroot;}

HashMap中的樹化

finalvoidtreeify(Node<K,V>[]tab) {TreeNode<K,V>root=null;// 遍歷當前鏈表for(TreeNode<K,V>x=this,next;x!=null;x=next) {next=(TreeNode<K,V>)x.next;x.left=x.right=null;if(root==null) {x.parent=null;x.red=false;root=x;? ? ? ? }else{Kk=x.key;inth=x.hash;Class<?>kc=null;// 每遍歷一個鏈表上的元素就插入到紅黑樹中for(TreeNode<K,V>p=root;;) {intdir,ph;Kpk=p.key;? ? ? ? ? ? ? ? // 判斷待插入結(jié)點應(yīng)該插入在左子樹還是右子樹// 先比較hash值if((ph=p.hash)>h)dir=-1;elseif(ph<h)dir=1;// 如果hash值相等坪仇，然后比較k.compareTo(pk)elseif((kc==null&&(kc=comparableClassFor(k))==null)||(dir=compareComparables(kc,k,pk))==0)// 如果還相等則再比較identityHashCodedir=tieBreakOrder(k,pk);// 根據(jù)dir的值就知道了待插入結(jié)點該插在左子樹還是右子樹了TreeNode<K,V>xp=p;if((p=(dir<=0)?p.left:p.right)==null) {x.parent=xp;if(dir<=0)xp.left=x;elsexp.right=x;root=balanceInsertion(root,x);break;? ? ? ? ? ? ? ? }? ? ? ? ? ? }? ? ? ? }? ? }moveRootToFront(tab,root);}