# 一、概念 ### 1.定義與性質 （1）定義 紅黑樹字義：滿足(a)每個結點或是紅的，或是黑的(b)根結點是黑的(c)每個葉結點（NIL）是黑的(d)如果一個結點是紅的，則它的兩個兒子是黑的(e)對每個結點，從該結點到其子孫結點的所有路徑上包含相同數目的黑結點的二叉查找樹稱為紅黑樹。 黑高度定義：從某個結點x出發（不包括該結點）到達一個葉結點的任意一條路徑上的黑色結點的個數稱為x的黑高度。 （2）性質 紅黑樹確保沒有一條路徑會比其它路徑長出兩倍。 一棵有n個內結點的紅黑樹的高度至多為2lg(n+1) ### 2.結構 （1）紅黑樹結點結構 ~~~ struct node { node *left; node *right; node *p; int key; bool color; }; ~~~ （2）紅黑樹結構 ~~~ struct Red_Black_Tree { node *root;//根結點 node *nil;//哨兵 }; ~~~ ### 3.紅黑樹上的操作 SEARCH PREDECESSOR MINIMUM MAXIMUM INSERT DELETE # 二、代碼 [頭文件](https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/include/chapter13/redBlackTree.h) [產品代碼](https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter13/redBlackTree.cpp) [測試代碼](https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/tst/chapter13/redBlackTreeTest.cpp) 代碼說明： 1.使用NIL作為葉子結點，代替NULL，這樣可以少一些特殊處理 2.刪除一個結點,delete改為remove，一方面是避免與關鍵字沖突，另一方面，覺得remove語義更符合 3.insert和remove使用int key代替node *z作為參數，覺得這樣使用更方便 # 三、練習 ### 13.1 紅黑樹的性質 13.1-1 黑高度是指從根結點到葉結點的路徑上黑色結點的個數，需要注意的是，計算黑高度時，出發的結點不計算在內，葉結點是指nil結點  13.1-2 不是，因為違反性質4 不是，因為違反性質5 13.1-3 是 13.1-4  [http://zh.clrs-ans.wikia.com/index.php?title=13.1_%E7%BA%A2%E9%BB%91%E6%A0%91%E7%9A%84%E6%80%A7%E8%B4%A8&variant=zh-cn](http://zh.clrs-ans.wikia.com/index.php?title=13.1_%E7%BA%A2%E9%BB%91%E6%A0%91%E7%9A%84%E6%80%A7%E8%B4%A8&variant=zh-cn) 葉子深度為黑高度 13.1-5 bh(x)為黑高度，相應的定義rh(x)為紅高度，根據RB樹性質 rh(x)<=bh(x)，而每條路徑的bh(x)都想等，最長可能路徑bh(x)+rh(x)，最短可能路徑bh(x)，故最長是最短的至多兩倍。 13.1-6 最多：2^(2k+1)-1 高少：2^(k)-1 13.1-7 比值最大為2：1，奇數層的結點為紅色，偶數層的結點為黑色。n為奇數。 比值最小為0，全部結點都為黑色 ### 13.2 旋轉 ~~~ 13.2-1，代碼見上文 RIGHT-ROTATE 1 y <- left[x] 2 left[x] <- right[y] 3 if right[y] != nil[T] 4 then p[right[y]] <- x 5 p[y] <- p[x] 6 if p[x] = nil[T] 7 then root[T] <- y 8 else if x = right[p[x]] 9 then right[p[x]] <- y 10 else left[p[x]] <- y 11 right[y] <- x 12 p[x] <- y 13.2-3 a的深度+1，b的深度不變，c的深度-1 ~~~ ### 13.3 插入 13.3-1 1樓說得很好 ~~~ 不是因為違反了性質5才不會采用把節點標志位黑色。如果只是因為違反了性質5，完全可以調整，就跟RB-INSERT中將插入的節點標志位紅色違反了性質4或者2一樣，都是可以通過跳整來符合要求。其原因是插入節點共有六種情況（通過RB-INSERT-FIXUP中的判斷語句可以看出：插入節點z的父節點為左孩子有三種，為右孩子也有三種。舉父節點為左孩子為例：第一種為如果z的叔叔為紅是第一種情況，如果叔叔為黑且z為右孩子為第二種情況，如果叔叔為黑且z為左孩子為第三種情況），前三種情況中只有第二種z最終為黑色節點，其余兩種z最終為紅色。z最終為紅色的比例較高，（4:2），所以一開始將z定義為紅色，最后不用修改的概率較高，這是考慮到代碼的優化而不是因為違反了性質5。 ~~~ 13.3-2 運行以上程序能得到結果 13.3-6 見[算法導論-13.3-6](http://blog.csdn.net/mishifangxiangdefeng/article/details/7727271) 令待插入的元素是z。在插入的過程記錄從根結點到z的路徑，并用棧存儲。那么z的父結點就是棧頂元素，z的祖父結點就是棧的次頂元素。 在向上迭代的過程同時出棧，控制好出棧的時間，就能正確實現RB-INSERT ### 13.4 刪除 ~~~ 13.4-3 運行以上程序能得到結點 13.4-4 （1）某黑色結點被刪除后，第一個被調整的點是被刪除結點的孩子（這個被刪除的結點最多只有一個孩子），若這個被刪除結點沒有孩子，那么第一個被高速的點是nil （2）x的兄弟w沒有孩子，或左旋時w沒有左孩子，或右旋時w沒有右孩子 13.4-7 可能不相同。 （1）新加入結點后可能會導致某些旋轉操作，刪除后不會轉回來 （2）即使樹的結構不變，結點的顏色也有可能會改變 ~~~ # 四、思考題 ### 13-1 動態持久集合 見[算法導論-13-1-持久動態集合](http://blog.csdn.net/mishifangxiangdefeng/article/details/7903794) ### 13-2 紅黑樹上的連接操作 見[算法導論-13-2-紅黑樹上的連接操作](http://blog.csdn.net/mishifangxiangdefeng/article/details/7904581)