隨機猜題

考慮下面的紅黑樹（值域為 0 ~ 99 的整數，樹內的值不得重複）：

請給一個最短的數列，依序插入此樹後，會使 84 變為紅色。

--
可能不容易 — 尤其當隨機客說 "justify your answer" 的時候 XD。

---

目前找到的一個可能的最佳解是：81, 80, 71, 76, 70, 77, 75, 74。如何 "justify" 就是另一回事了 XD。

紅黑樹

去年此時還滿有信心地說「以後應該隨時能即時推出各種規則才對（雖然可能卡一陣子 XD）」，但今年再推一次還是很辛苦 XD，所以還是趕快把我慣用的邏輯寫上來，搭配隨機客今年的投影片當作圖示，【p.xx】即為這份投影片的頁碼。

因為 recoloring 相對簡單一些，所以最高指導原則是「能夠 recoloring 就 recoloring，不能 recoloring 再考慮 rotation」。

首先是插入。

• 插入一定是把新點放到葉子，此時把新點漆成紅色就立刻維持住黑色性質，所以插入時一律把新點漆成紅色。
  • 這時候如果新點的 parent 是黑色就結束了，因為紅色性質直接成立。【p.56】
  • 如果 parent 是紅色，此時必存在 grand parent，且後者必為黑色。
    • 先試試 recoloring。Recoloring 是想把 grand parent 的黑色往下撥到 parent 和 sibling of parent，所以 sibling of parent 必須是紅色才能做 recoloring。做完 recoloring 之後，就把可能的雙紅情況上推了一層。倘若推到 root，直接把 root 塗黑就結束了。【p.58 ~ 61】
    • 不能 recoloring 的話，一定是因為 sibling of parent 是黑色。此時就照【p.62 ~ 65】的方式做 rotation。速記法是看嫡系支幹「祖父新」，把中間的數提起來、塗成固定的顏色，最後把葉子依序接回去。（隨機客不考慮單旋轉和雙旋轉，所以這樣記就行了。）至於為何嫡系旋轉後須漆成那些顏色，可考慮各「葉支」的黑色深度以及「各葉支的 root 均為黑色」的事實，最後要選擇「黑紅紅」和「紅黑黑」時，顯然前者比較好，因為後者可能繼續把雙紅的情況往上傳遞。

再來是刪除。

• 刪除時，先找到該點在中序（in-order）上的 predecessor 或 successor（即【p.71】的「舊」點），將兩點的值交換後刪除舊點。以簡單的反證法即可說明一個點的 predecessor（successor）不會有 right（left）child。
  • 如果舊點和可能非空的子點是一紅一黑，直接刪除舊點即可。【p.72】
  • 若不然，舊點和子點都是黑色。刪除舊點後，把子點漆成「雙黑」，開始調整。【p.73】
    • 先考慮 recoloring。我們想要把子點的一份黑色撥到 parent（父），但此時子點的 sibling（兄）必須也是黑色，且其 children（姪）都是黑色，才能把子點和兄點的黑色一起往上撥到父點。如果父點原本是紅色就結束了，原本是黑色的話就把雙黑上推了一層。倘若推到 root，直接忽略雙黑就結束了。【p.75】
    • 不能 recoloring，一定是因為兄點是紅色，或者兄點是黑色且有某個姪點是紅色。
      • 有某個姪點是紅色時，就得做 rotation：看「父兄姪」支幹、把中間的數提起來、塗成固定的顏色，最後把葉子依序接回去。此步做完即化解雙黑情況。可以把旋轉的邏輯想成：因為有個姪點是紅色，所以把兄點位置的黑挪到子點上面分攤雙黑時，可以把姪點位置的紅改成黑色彌補。【p.77 ~ 80】
      • 兄點是紅色的話，做個 rotation 化約成上面提過的的某一種情況。可以想成：兄點位置的紅對於黑色性質是多餘的，所以可以把該處的紅挪到子點上面。【p.74】再下一步就會結束，不會導致 infinite loop，討論如下。
        • 旋轉後若變成 recoloring 的情況，就會直接結束，因為父點由紅轉黑，不再有雙黑的情況。
        • 若變成「姪點為紅」的情況，也會直接結束。

--
"Somehow" 還是很複雜，不過至少有個理路可循 XD。