紅黑樹

1. 紅黑樹本質是一個二叉搜尋樹（BST），了解紅黑樹之前需要先了解 BST 的特性
   1. BST 的特性隻有一個：在 BST 中，任何一個根節點都大于等于所有 left children，都小于所有 right children，依據這一特性，BST 可以推出以下特性：
      1. BST 中序周遊的結果為一個有序的清單
      2. 查找 key：從根節點查找，小于目前節點再從left child 開始查找，大于目前節點則從right child 開始查找，直到查找到或者到葉子結點為止
      3. 最小值：二叉樹的最左節點
      4. 最大值：二叉樹的最大節點
      5. 前驅：
         1. 如果有left child，則為以left child 為根的最大值
         2. 如果沒有 left child，再判斷目前節點是否為root
            1. 如果是，沒有前驅
            2. 如果不是，找到目前節點為 parent 的 right child 的那個 parent 節點，如果沒有那個 parent，就沒有前驅
      6. 後繼：
         1. 如果有right child，則為以right child 為根的最小值
         2. 如果沒有 right child，再判斷目前節點是否為root
            1. 如果是，沒有後繼
            2. 如果不是，找到目前節點為 parent 的 left child 的那個 parent 節點，如果沒有那個 parent，就沒有後繼
      7. 插入操作：要插入的 key 小于等于目前節點以 left child 為目前節點繼續遞歸插入，要插入的 key 小于目前節點以right child 為目前節點繼續遞歸插入，直到 child 為null 位置，child 為null 的位置就是要插入的位置。
      8. 删除操作：
         1. 如果要删除的節點沒有 child，直接删除
         2. 如果隻有一個 child，用 child 代替要删除的節點
         3. 如果有兩個 child，找到後繼節點，用後繼節點的 key 替換要删除的那個節點的 key，接着遞歸删除後繼節點操作
2. 了解紅黑樹之前，還需要知道兩個操作，左旋和右旋
   1. 左旋：以parent 為支點，原parent 變成 原 right child 的 left child，原 right child 變成 parent，原 right child 的 left child 變成原parent 的 right child，左旋完成後 BST 的特性不變
   2. 右旋：以parent 為支點，原parent 變成 原 left child 的right child，原 left child 變成 parent，原 left child 的 right child 變成原parent 的 left child，右旋完成後 BST 的特性不變
3. 紅黑樹特性
   1. 每個 node 隻能是 red 或 black
   2. 根節點是black
   3. leaf 節點資料為 NIL 且每個 leaf 結點是 black
   4. 如果一個 node 是 red，則它的 children 必須是 black
   5. 從一個 node 到其 children 的所有路徑上包含相同的 black node 數量
4. 紅黑樹操作 -- 添加：
   1. 将紅黑樹視為 BST，将節點插入
   2. 将插入的節點标記為 red
   3. 通過一系列插入修正操作，使之重新成為一顆紅黑樹
5. 紅黑樹操作 -- 添加時的插入修正操作：紅黑樹添加得第3步的具體插入修正操作可以分成3類：
   1. 被插入的節點是根節點：直接标記為 black
   2. 被插入的節點的 parent 節點是 black：什麼都不做
   3. 被插入的節點的 parent 是 red：此時，又可根據 uncle 節點來分為3類操作
      1. 目前節點的 parent 節點是紅色，且 uncle 節點也是紅色，操作流程為：
         1. 将 parent 和 uncle 标為黑色
         2. 将 grandparent 标為 紅色
         3. 以 grandparent 為目前節點繼續遞歸修正
      2. 目前節點的 parent 是 red，且是其 parent 的 left child，uncle 是 black ，操作流程為：
         1. 将 parent 設定為 black
         2. 将 grandparent 标為 red
         3. 以 grandparent 為支點右旋
      3. 目前節點的 parent 是紅色，且是其 parent 的 right child，操作流程為：
         1. 以 parent 為支點進行左旋
         2. 左旋完成後變成情況2，按情況2 繼續調整即可
      注意：上述 3 種情況都是以插入到 parent 的 left child 為前提的，如果是插入到 right child，執行與上述情況的鏡像操作即可
6. 紅黑樹操作 -- 删除：
   1. 将紅黑樹視為一個 BST 來删除節點，這有3類情況：
      1. 待删除的節點是 red，直接删除即可
      2. 待删除的節點是 black，要頂替的節點是 red， 先删除，然後将要頂替的節點變成 black 即可
      3. 待删除的節點是 black，要頂替的節點也是 black，此時先删除，然後以要頂替的節點 為 x，通過一系列删除修正操作，使之重新成為一顆紅黑樹
7. 紅黑樹操作 -- 删除修正：紅黑樹的删除修正可分為以下 6 種情況：
   1. x 是 root 節點，什麼都不用做
   2. x 的 parent、sibling、nephews 都是 black
      1. 把 x 的 sibling 變成 red 即可
      2. 以 x 的 parent 為目前節點繼續遞歸進行删除修正操作
   3. x 的 parent 是 red，sibling 和 nephews 是 black
      1. 将 parent 變成 black，此時變成了情況1，再按情況1 繼續調整即可
   4. x 的 parent 顔色随意，sibling 是 black，sibling 的 right child 是 red
      1. 以 x 的 parent 為支點左旋
      2. 原 parent 和 原 sibling 顔色交換，原 sibling 的 right child 變為 black
   5. x 的 parent 顔色随意，sibling 是 black，sibling 的 left child 是 red
      1. 以 sibling 為支點右旋，
      2. 原 sibling 标為 red，原 sibling 的 left child 标為 black
      3. 此時變成了情況3，再按情況3 繼續調整即可
   6. x 的 sibling 是 red
      1. 以 x 的 parent 為支點進行左旋