<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Red Black Tree - 紅黑樹 -------- #### 紅黑樹 紅黑樹比AVL樹的實際性能更好，紅黑樹的操作次數約是$$ log_2 n + 4 $$，而不是AVL樹的$$ O(2 \times log_2 n) $$次。盡管它們的插入/刪除/查找時間復雜度都是$$ O(log_2 n) $$。 除了基本的二叉查找樹屬性，紅黑樹還擁有以下特性： $$ (1) $$ 節點是紅色或黑色的； $$ (2) $$ 根節點是黑色的； $$ (3) $$ 葉子節點的左右孩子節點都為$$ nil $$節點，$$ nil $$節點是黑色的； $$ (4) $$ 紅色節點的左右孩子節點都是黑色的； $$ (5) $$ 根節點到任意$$ nil $$節點途中經過的黑色節點的數量相同；  紅黑樹是一種可伸縮的金字塔形狀，其中的黑色節點嚴格保持金字塔形狀，而紅色節點就像彈簧一樣。任意分支上的紅色節點和黑色節點數量（包括空節點）總滿足$$ 0 \leq n_{red} \lt n_{black} $$。 紅黑樹的插入過程與AVL樹類似，按照二分查找找到適合的位置插入新節點$$ x $$，然后從$$ x $$沿著父節點向上對每個節點檢查，若紅黑樹的屬性被破壞則通過以下規則調整自己。下面是所有需要調整的情況：      上面五種情況中，若處于$$ Red Uncle $$情況則按照$$ (1) $$進行旋轉和重新染色，再從$$ grandfather $$節點開始下一次檢查（跳過了一個節點）；若處于$$ Black Uncle $$情況則按照$$ (2) - (5) $$進行旋轉和染色，之后該樹必然滿足紅黑樹屬性，不必繼續向上依次檢查所有節點，停止檢查，插入結束。 紅黑樹刪除前半部分與AVLTree、BinarySearchTree相同，這里不再贅述。 前兩種情況中實際刪除的節點是$$ x $$，第三種情況實際刪除的節點是$$ x $$的后繼節點$$ y $$。 -------- #### Red Black Tree * http://faculty.cs.niu.edu/~freedman/340/340notes/340redblk.htm * https://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf -------- #### 源碼 [RedBlackTree.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/DataStructure/RedBlackTree.h) [RedBlackTree.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/DataStructure/RedBlackTree.cpp) #### 測試 [RedBlackTreeTest.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/DataStructure/RedBlackTreeTest.cpp)