紅黑樹（Red–Black Tree）

properties

• 自平衡二元搜尋樹
• 每個點非黑即紅
• root 是黑色的
• left (NIL) 是黑色的
• 如果當前點為紅色的，則左有兩個 children 為黑
• 從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點

確保從根到葉子的最長的可能路徑不多於最短的可能路徑的兩倍長，因此有著良好的最壞情況執行時間，O(log n) 時間內完成尋找，插入和刪除

Rotate Operation

• 紅黑樹利用旋轉操作來保持其結構平衡
• 旋轉操作可切換父子關係

left Rotate

LEFT-ROTATE(T, x)
    y = x.right
    x.right = y.left
    if y.left != T.nil
        y.left.p = x
    y.p = x.p
    if x.p == T.nil
        T.root = y
    else if x == x.p.left
        x.p.left = y
    else
        x.p.right = y
    y.left = x
    x.p = y