紅黑樹

文章出處

紅黑樹可以看做是對二叉搜索樹的改進，紅黑樹的紅黑性質限制了紅黑樹的樹高 <= 2 log(N). 以此來保證，查詢，刪除，插入的時間復雜度最壞情況都是 log(N)。

一顆紅黑樹是滿足下面紅黑性質的二叉搜索樹

每個節點或是紅色的，或是黑色的。
根節點是黑色的。
每個葉節點（NIL）是黑色的。
如果一個節點是紅色的，則它的兩個子節點都是黑色的。
對每個節點，從該節點到其所有后代葉節點的簡單路徑上，均包含相同數目的黑色節點。

插入

在向一顆紅黑樹插入節點時，插入節點是著成紅色的，因為如果插入黑色節點，很明顯會破壞性質5. 除非這顆紅黑樹是空樹。
節點插入紅黑樹的過程是和二叉搜索樹插入節點的方法類似。如果插入節點的父節點是黑色時，插入節點不會破壞紅黑樹的性質。但是如果插入節點的父節點是紅色的，會破壞性質4.
這時就需要維護紅黑樹的性質了。假設插入節點為 z, z的叔節點為y.

if(z.p == z.p.p->left)

z 的叔節點為紅色。叔節點著黑，父節點著黑，祖父節點著紅， z 指向祖父節點。
z 的叔節點為黑色，且 z 為右孩子。z 指向父節點然后左旋：left-rotate(T, z) // T為樹根
z 的叔節點為黑色，且 z 為左孩子。父節點著黑，祖父節點著紅，然后右旋。right-rotate(T, z.p.p)

如果 z 的父節點為右孩子（即：z.p == z.p.p->right），與上面過程類似，是對稱的。把所有的“左”替換成“右”即可。

刪除

在從紅黑樹中刪除一個節點時，同樣和從二叉搜索樹中刪除節點相似。假設，我們始終維護節點 y 為從樹中刪除的節點或者移至樹內的節點。我們保存節點 x 的蹤跡，使它移至節點 y 的原始位置上。

當 y 為紅色時（無論時被直接刪除的節點，還是“替補”的節點），都不會破壞紅黑樹的性質。如果 y 是替補節點時（即：移至樹內的節點），把 y 著成被刪除節點的顏色。
但是，當 y 為黑色時，紅黑樹的性質會被破壞。
if(x == x.p->left)

x 的兄弟節點 w 為紅色的。 x 的兄弟節點 w 著黑，父節點著紅，然后左旋：left-rotate(T, x.p)
x 的兄弟節點 w 為黑色的。 w 的兩個孩子節點也都是黑色的。 w 節點著紅，x 指向父節點。
x 的兄弟節點 w 為黑色的。 w 的左孩子為紅，右孩子為黑。 w 著紅，w的左孩子著黑，然后右旋：right-rotate(T, w)
x 的兄弟節點 w 為黑色的。 w 的右孩子為紅。 w 節點著父節點顏色，父節點著黑，w的右孩子節點著黑, 然后左旋：left-rotate(T, x.p)
如果 x 為右孩子（即：z == z.p->right），與上面過程類似，是對稱的。把所有的“左”替換成“右”即可。