紅黑樹和平衡樹的旋轉機制

• 紅黑樹的屬性：
• 紅黑樹插入節點：
• 平衡樹旋轉機制
• • LL型
  • RR型
  • LR型
  • RL型

紅黑樹的屬性：

1、黑屬性：根必須是黑色的
2、紅屬性：紅節點的孩子必須是黑色的
3、空指針也必須是黑色的
4、任一個節點，所有孩子節點上的黑色數目（包括黑色節點和黑色指針）
都是一樣的
5、紅黑樹的高度不超過2*log2(n+1)
6、黑色高度：從某個節點到葉子節點所遇到黑色節點的個數稱為黑色高度（BH）
           

紅黑樹插入節點：

1、插入節點時，如果樹是空的，插入的節點是黑色并退出
    2、如果插入的結點是紅色的，檢查兩種情況

    情況1：如果父親是紅色的，檢查父親的兄弟是不是紅色的；
    1、如果是紅色，把父親和父親的兄弟變成黑色的，再觀察父親的父親的
    顔色，重複這個過程（如果父親是紅色的，檢查父親的兄弟是不是紅色的；
    如果是，把父親和父親的兄弟變成黑色的）。
    2、如果父親是黑色的，不要做任何操作了

    情況2：如果父親是紅色的，父親的兄弟是黑色的或者是空的
    要使用旋轉機制（LL型，LR型，RR型，RL型），再修改相應結點的顔色，
    使其符合紅黑樹的屬性
           

平衡樹旋轉機制

LL型

在左孩子的左子樹上插入結點導緻不平衡

如何旋轉：

右旋

不平衡：樹的平衡因子大于1，就是

左子樹的高度減右子樹的高度的絕對值大于1

右旋

RR型

在右孩子的右子樹上插入結點導緻不平衡

如何旋轉：

左旋

左旋

LR型

在左孩子的右子樹上插入結點導緻不平衡

如何旋轉

先左旋，再右旋

先左旋

再右旋

RL型

在右孩子的左子樹上插入結點導緻不平衡

如何旋轉

先右旋，再左旋

先右旋

再左旋