紅黑樹的插入操作過程詳細圖解

說在前面

對于文章中提到的左旋右旋等旋轉詳細過程請參考我的上一篇部落格平衡二叉樹插入操作的詳細過程中的解決失衡的口訣方法，其中有旋轉的詳細圖解過程

紅黑樹

• 定義與性質

  • 紅黑樹是一種含有紅黑結點并能自平衡的二叉查找樹
  • 任意結點都有顔色，紅色或者黑色
  • 紅黑樹中根節點一定是黑色的
  • 紅黑樹中的 null 位置看作是黑色
  • 紅黑樹中紅色不能與紅色相鄰
  • 從根到所有 null 的路徑上黑色結點的個數相同
  • 紅黑樹中，最長的路徑的長度，不會超過最短的路徑的長度的2倍
  • 時間複雜度：Olog（n）

• 插入操作過程

  • start：一顆紅黑樹
  • 按照搜尋樹的特征進行插入
  • 插入時：插入的結點一定是紅色的，如果為黑色，會破壞第五條規則
    • 如果插入的結點是根節點，将顔色改為黑色
    • 插入的結點的父結點是黑色的，則插入完成
    • 插入的結點的父結點是紅色的，則需要修複，且繼續向上調整，直到為根或滿足規則
    • 如果根修改之後為紅色，一定要改過來，改為黑色
  • end：一顆紅黑樹

• 修複方法

  • 前提條件：插入的結點（cur）是紅色，cur的父結點（parent）是紅色的，這樣的需要修複
  • 修複要點：保證修複操作前和修複操作後的黑色結點的數量不變
  • 可推斷出：cur 的祖父結點即父親的父親（grandpa）一定是黑色，否則插入目前結點之前已經違反了紅黑樹的規則
  • 如圖：

    

  • • 情況1：uncle 存在（uncle != null），并且 uncle 的顔色是紅色
      • 修複方法：grandpa 由黑變紅，parent & uncle 由紅變黑；
      • eg：

        

    • • 情況2.1：cur 是 parent 左孩子，且 parent 是 grandpa 的左孩子**
        • 修複方法： grandpa 右旋之後顔色變為紅色，parent 的顔色變為黑色

        • 

      • 情況2.2：cur 是 parent 的右孩子，且 parent 是grandpa 的右孩子
        • 修複方法：grandpa 左旋後顔色變為紅色，parent 顔色變為黑色
        • eg:

          

    • 情況2.3：cur 是 parent 的右孩子 ，parent 是 grandpa 的左孩子
      • 修複方法：對 parent 左旋之後将 parent 和 cur 的名稱交換，再按照2.1的情況處理

      • 

    • 情況2.4： cur 是 parent 的左孩子 ，parent 是 grandpa 的右孩子
      • 修複方法：對 parent 右旋之後将 parent 和 cur 的名稱交換，再按照2.2的情況處理

      • 

• 示範

• 應用：TreeMap的底層實作