紅黑樹

為什么要發明紅黑樹

平衡二叉樹AVL：插入/刪除很容易破壞平衡性，需要頻繁調整樹的形態。如：插入操作導致不平衡，則需要先計算平衡因子，找到最小不平衡子樹（時間開銷大），在進行LL/RR/LR/RL調整

紅黑樹RBT：插入/刪除很多時候不會破壞“紅黑”特性，無需頻繁調整樹的形態。即使需要調整，一般都可以在常數級時間內完成

平衡二叉樹：適用于以查為主，很少插入/刪除的場景

紅黑樹：適用于頻繁的插入/刪除的場景

大概會怎么考？

紅黑樹的定義和性質 – 選擇題

紅黑樹的插入/刪除 – 要能手繪插入過程（不太可能考代碼），刪除操作比較麻煩，也許不考

紅黑樹的定義和性質

紅黑樹的定義

struct RBnode{int key;RBnode* parent;RBnode* lchild;RBnode* rchild;int color;		//結點顏色，如：可用0/1表示紅/黑，也可以使用枚舉型enum表示顏色
};

結點的黑高bh – 從某結點出發（不含該結點）到達任一葉結點的路徑上黑節點的總數

紅黑樹的插入

插入方法

①先查找，確定插入位置（原理同二叉排序樹），插入新結點

【與黑高bh相關的推論】

如果根結點的黑高為h，內部結點數（關鍵字）至少為多少個？

內部結點數最少的情況→總共h層黑結點的滿樹形態

若根結點黑高為h，內部結點數（關鍵字）至少有2^h-1個

紅黑樹的刪除

重要考點:

①紅黑樹刪除操作的時間復雜度=O(log2n)

②在紅黑樹中刪除結點的處理方式和“二叉排序樹的刪除’一樣

③按②刪除結點后，可能破壞“紅黑樹特性”，此時需要調整結點顏色、位置，使其再次滿足“紅黑樹特性”。