紅黑樹是怎么來的-有解無憂

平衡的關鍵

書接前文，

在前文《二叉搜索樹的本質》中我們提到，二叉搜索樹在實踐中有個很大的問題：樹傾斜，按如下順序插入資料會讓二叉搜索樹退化成普通鏈表，進而相關操作的時間復雜度退化到 O(n)：

怎樣讓這棵樹在寫操作后仍然保持平衡呢？

R 教授一邊呷著黑咖啡，一邊盯著這棵“畸形”的二叉樹發愣，

“要怎樣才能在添加新節點的時候不會破壞樹的平衡性呢——或許應該這樣問：添加新節點的程序是如何破壞樹的平衡性的？”R 教授緊鎖雙眉喃喃道，

忽然，他兩眼放光，好像發現了什么！

“對！問題就出現在這：向下生長，”R 教授發現，每次添加新節點，都會給現有的葉節點生成新的孩子節點，如此，每次添加一個新節點，都使得樹的高度加 1，最終變成上圖中的鏈表，

“那么，如果不讓這棵樹向下生長呢？”這是個大膽的想法，

比如，添加元素 2 時，不是作為節點 1 的孩子節點，而是和 1 放在一起（按序）呢？像這樣：

如此，樹便不再生長了，繼續：

樹高度是不再生長了，但有個問題：整棵樹只有一個節點了，不就退化成陣列了嗎？

既然它叫樹，就必然需要生長，

“既然它要生長，又不能向下長，便只能向上長了，”

如何讓樹向上生長呢？

回想一下前文《二叉搜索樹的本質》中我們如何通過二分法將有序陣列構造成二叉樹？

我們取有序陣列的中間元素作為父節點 P，將左右子陣列分別作為 P 的左右子樹，通過這種方式我們最終構造出了一棵平衡二叉樹，

這里我們不妨也借鑒這種思想試試，

當節點中元素數量達到 3 個時，我們取中間的元素作為父節點 P，兩邊的元素分別作為 P 的左右子節點，

如上圖，原來包含 3 個元素的節點裂變成了三個節點，以該節點為根的子樹高度加 1，

為啥選擇在包含 3 個元素的時候裂變，而不是 2 個或者更多呢？我們選擇在奇數元素數的時候裂變，好進行左右對稱操作，3 是自然數中除 1 以外最小的奇數，操作起來足夠簡單（至少理論上是），
我們當然可以選擇在節點包含 n 個元素的時候裂變，

也就是說，在我們設計的這種裂變型的搜索樹中，一個節點最多可以包含 2 個元素，最少包含一個元素，當元素數超過 2 個時便會發生裂變，導致樹（可能）向上生長——向上生長的含義是，裂變程序產生的父節點 P 總是向上冒泡，它可能在上層生成一個新節點（當原本上層沒有節點時），也可能和上層的節點合并（當原本上層有一個單元素節點時），也可能導致上層節點繼續裂變（當上層原本是 2 元素節點時），

在二叉搜索樹中，每個節點 P 最多可以有兩個孩子節點：左孩子的值小于等于 P 的值，右孩子的值大于等于 P 的值，在我們新型搜索樹中，一個節點最多可以有兩個元素，當有兩個元素 a, b 時，是可以表示三個區間的：小于 a 的元素集合 [,a)、介于 a,b 之間的元素集合 [a,b) 以及大于等于 b 的元素集合 [b,)，所以，當某節點 P 有兩個元素時，它最多可以有三個子節點（想象成有序陣列中兩個元素分割開的三個區域），

因而，在這種新型搜索樹中，一個節點最多可能有 2 個或者 3 個子節點，我們“望文生義”地給它起個名字就叫 2-3 樹，

我們按照上面的思想按序插入 1 ~ 11 的元素，看看最終生成的 2-3 樹是怎樣的，

在上圖中，我們總是將新元素添加到已有的葉節點中，而不是直接創建新節點，所以添加元素本身并不會導致樹高度發生改變（甚至不會導致節點數量發生改變），只是在添加新元素后，可能導致既有節點分裂，進而導致節點數以及數高度發生變化，

進一步，我們發現，只有一種情況會導致樹高度增加：根節點分裂——當根節點填入第三個元素時，會將中間的元素提升作為新根，而該元素左右兩邊的元素分別裂變成左右子樹，該程序是對稱的（左右子樹高度同時加 1），因而無論如何裂變，整棵樹都是平衡的，

也就是說，通過自下而上裂變式生長，真的能保證搜索樹的平衡性（至少插入元素時是這樣）——發現這點后，R 教授樂壞了，趕緊開瓶香檳以示慶祝，

2-3 樹的問題

R 教授一邊呷著香檳一邊試圖實作這種神奇的搜索樹，

不過在實作上他遇到了問題，

他發現這種看似很簡單的資料結構，實作起來特復雜，需要分別考慮 2 節點和 3 節點的情況，寫出來的代碼又臭又長，

他在寫洗掉邏輯的時候終于忍無可忍，將一大瓶香檳扔進了垃圾桶里，

“難道喝高了？不能啊，真理應該是簡單的才對，這坨 SHIT 算個什么東西！”

于是他找來 L 教授幫忙，

“我覺得問題就出現在 2-3 上，它給人一種搖擺不定感，完美的設計應該是對稱的，” L 教授故弄玄虛，

“但我沒有什么好辦法讓它變成二叉樹或者三叉樹，一個節點在成為 3 節點之前必然要先成為 2 節點，所以這兩種節點都必然會實際存在，”

“嗯，所以兩類節點并存屬于邏輯事實，” L 教授盯著面前的 2-3 樹若有所思，

“不過我們能否在實作上消除一類節點呢——我的意思是，能否用 2 節點來表示 3 節點？”

“這是什么鬼？” R 教授疑惑地望著 L 教授，

L 教授解釋道：“無論是 2 節點還是 3 節點，它們在邏輯上都是等價的：都是表示有序序列（有序陣列），而且相互之間很容易轉化，”

我們可以用如下三種代碼來說明情況：

/**
 * 最基本的陣串列示法
 */
var arr = [...[-∞, a), a, ...[a, b), b,  ...[b, ∞)]

/**
 * 2-3 搜索樹的 3 節點表示法
 */
var node = {
  // 本節點元素數量
  size: 2,
  // 元素陣列，升序排列
  elements: [a, b],
  // 子節點陣列
  // node1 子樹中元素范圍：[-∞, a)
  // node2 子樹中元素范圍：[a, b)
  // node3 子樹中元素范圍：[b, ∞)
  children: [node1, node2, node3]
}

/**
 * 二叉搜索樹表示法
 */
var nodeB = {
  element: b,
  left: nodeA,
  // nodeZ 子樹的元素范圍：[b, ∞)
  right: nodeZ
}

var nodeA = {
  element: a,
  // nodeX 子樹的元素范圍：[-∞, a)
  left: nodeX,
  // nodeY 子樹的元素范圍：[a, b)
  right: nodeY
}

L 教授畫出如下草圖：

“如此，便可以用 2 節點來表示 3 節點，只不過我們將 a、b 之間的連線用特殊顏色標記以示區分，也就是說，我們完全可以用二叉樹來表示 2-3 樹！” L 教授語調高亢，得意之神情溢于言表，

為了著重表示左邊的 3 節點如何拆分成右邊的 2 節點，L 教授將 a、b 之間的連線用紅色筆畫出，

“有點意思！” R 教授看到這里兩眼放光，不知是因為喝高了，還是因為興奮，

“所以待分裂的 4 節點可以用兩條紅線來表示，” R 教授順著 L 教授的思路畫了下圖：

如上圖，四節點可以用連續兩條紅線表示 a、b、c 之間的關系，不過由于最終不可能存在 4 節點，也就意味著不可能存在兩條連續的紅線，它最侄訓裂變成 3 個 2 節點，

“不過，這種轉換有何用？我們不過是把 2-3 樹又變成了二叉樹而已，” R 教授興奮過后兩眼又泛起了疑惑，

“我們可以將 2-3 平衡二叉樹的特性應用于等價二叉搜索樹上，如此，理論上便能保持二叉樹的平衡性——既然它是由 2-3 樹轉換來的，”

“不過在繼續之前，我們先做個小小的優化，” L 教授繼續道，“因為我們編碼的時候是基于節點（而不是邊）來編碼的，所以我們可以將邊的顏色轉移給兩端之一的節點——我們決定統一轉給下端節點，”

如下圖：

至此，這棵轉換來的二叉搜索樹中存在兩種節點：紅色節點和黑色節點，為了避免每次都叫“轉換后的二叉樹”，我們給它起個名字，不妨就叫紅黑樹吧，

“很形象的名字！”

紅黑樹的特性

我們前面已經得到了一個特性：由于 2-3 樹中不可能存在 4 節點（擁有 3 個元素，4 個子節點的節點），對應地，紅黑樹中不可能存在兩個連續的紅節點，

“對，這是個顯而易見卻十分重要的特性，” R 教授接茬道，“另一個重要問題是：紅黑樹中如何表示 2-3 樹的平衡特性，即所有的葉子節點到根節點的簡單路徑相等，”

L 教授盯著 2-3 樹和轉換后的紅黑樹思索良久，道：“2-3 樹中所有葉子節點到根節點形成的簡單路徑上擁有的節點數量都相等，對于 2 節點，由于和紅黑樹中的（黑色）節點一一對應，不難處理；對于 3 節點，它在紅黑樹中其實由兩個節點——一紅一黑——構成，如果我們將這兩個節點合二為一，那么紅黑樹中從任何葉節點到根節點的簡單路徑上節點數量也應該都是相同的，”

“也就是說，紅黑樹中，從任何葉節點到根節點的簡單路徑上，忽略掉所有紅色節點后，剩下的節點——也就是黑色節點——數量是相同的，”

至此，我們得到了紅黑樹兩條最重要的特性（核心特性）：

特性 1: 不能存在兩個連續的紅節點；
特性 2: 從任何葉節點到根節點的簡單路徑上的黑節點數量是相同的；

因為 2-3 搜索樹的任何子樹也是 2-3 搜索樹，所以以上兩條性質對于紅黑樹的任何子樹也都成立，

另外，顯而易見，樹根節點一定是黑色的——因為它的上游不可能有節點跟它組成 2-3 樹中的 3 節點，

特性 3: 樹根節點是黑色的，

L 教授繼續道：“我想再加個人為的限制，前面我們將 2-3 樹轉成二叉樹的時候發現，那條紅線既可以往左傾，也可以往右傾，為了處理方便，我們限制只能往左傾，也就是讓兩個元素中大的那個作為父節點（黑色），小的作為左子節點（紅色），這樣的紅黑樹不妨叫左傾紅黑樹，”

特性 4: 紅節點必須是其父節點的左子節點，

最后，我們將一棵 2-3 樹用紅黑樹完整表示出來：

“嗯，性質 1 和 2 確實滿足，不過有個大問題：轉成紅黑樹后，樹的平衡性被破壞了！” R 教授盯著這棵紅黑樹大失所望，

“的確，3 節點轉成二叉樹中的兩個 2 節點后，有可能增加樹高度，因為二叉樹本質上仍然是自上而下生長的（而非自下而上裂變的），所以注定了它不可能是一棵完美的平衡樹，我們所追求的是實踐意義上的近似平衡性，” L 教授略顯尷尬地解釋道，

“嗯，那就將真理交給實踐去檢驗吧，現在我們不妨探索如何添加和洗掉元素，”

插入元素

先看看插入元素 1.5，

在 2-3 樹中的插入操作：

轉成紅黑樹：

貌似很簡單（先不管紅黑樹中為何 1 和 1.5 調換了位置），

再看看插入元素 11，

首先找到相關葉節點 node(9,10)，插入 11 得到 node(9,10,11)，這是個 4 節點，會發生分裂，將 10 提升到上層構成 node(6,8,10)，這仍然是個 4 節點繼續發生分裂，最終波及到根節點，如圖：

在這個例子中，無論 2-3 樹還是紅黑樹的結構都發生了很大的變化，看來這“級聯炸彈”威力不小，

“雖然我們總能夠先操作 2-3 樹，然后將結果映射到紅黑樹，但這在實作上并不可行——到目前為止我尚未發現將 2-3 樹轉換成紅黑樹其實作意義何在，” R 教授一本正經，

“的確，如果紅黑樹不能降低 2-3 樹在實作上的復雜性，便沒有半毛錢的意義，所以我們必須從二叉搜索樹本身來解決元素操作問題，不過，先容我喝杯咖啡提提神，” L 教授說著走向咖啡機，

神奇的三板斧

喝完咖啡，聽了段莫扎特，兩位教授繼續研究紅黑樹，

插入或者洗掉節點后，必須對紅黑樹執行一系列操作來維護紅黑樹的特性，由于紅黑樹是二叉搜索樹，所以操作后必須同時滿足二叉搜索樹的性質，

“我發現前面插入元素 11 后，雖然導致整棵紅黑樹結構變化很大，不過還是有規律的，我感覺好像將節點 4 圍繞節點 8 逆時針旋轉了一下，將 4 和 8 調換了父子關系，然后將 8 的左子節點給 4，整個二叉搜索樹性質并未改變，” R 教授驚喜的說到，

“對！這真是個奇怪但有用的性質，我們不妨稱它為左旋吧——因為被旋的節點在軸的左邊，” L 教授補充道，

對應地就有右旋：

左右旋能保證二叉搜索樹性質不變（請仔細分析上兩圖中字母大小關系，其中橢圓節點表示子樹），如果在旋轉中同時保證所涉及路徑上的黑色節點數量不變，則旋轉操作便可以用于維護紅黑樹性質，

另外還有一種顯而易見的操作：顏色翻轉，如圖：

上圖左側，假設所有葉節點到根節點構成的簡單路徑上黑節點數量都相同，但 9 和 10 都是紅節點，不符合特性 1，由于黑節點 8 的兩個子節點都是紅節點，我們將黑節點 8 和它兩個子節點顏色交換，整棵樹仍然滿足紅黑樹性質，

接下來我們看看能否通過上面介紹的左旋、右旋和顏色翻轉來維護紅黑樹的性質（包括二叉搜索樹的性質），

細談插入

當我們向紅黑樹中插入一個新元素時，首先要決定該元素的初始顏色，

假設新節點初始化為黑色，那么它必然會導致某條路徑的黑色節點數加 1，進而破壞紅黑樹性質，

如果初始化為紅色，那么它本身不會導致黑節點增加（不違反特性 2），但可能會違反特性 1，即出現兩個連續的紅色節點（當其父節點也是紅色時），但也有可能不違反任何特性，

所以我們決定讓新節點初始化為紅色，然后試圖通過“三板斧”來修復特性 1，

場景一：待插入節點的父節點是黑色（有兩種情況）：

注意上圖第二種情況，左旋后，由于 x 原本的黑色轉移給了其父節點 y，自己變成了紅色，所有經過 x 的簡單路徑（也必然經過 y）上的黑節點數并沒有發生變化，

場景二：待插入節點的父節點是紅色（也有兩種情況，不過我們可以通過左旋操作讓其變成一種情況）：

我們將 x 的父節點 P 圍繞 x 右旋看看情況：

如上圖，右旋并適當調整節點顏色后，在保持二叉搜索樹性質的前提下， α 子樹和 β 子樹中任何葉節點到根節點簡單路徑上的黑節點數量并沒有發生變化，而且就圖中幾個節點而言，不再有兩個連續的紅節點了，

不過，我們得考察一下 α 子樹和 β 子樹，

由于原先 x 是紅節點，所以 β 子樹的樹根必然是黑節點，然而 α 子樹的樹根既可能是黑節點也可能是紅節點，

如果 α 子樹的樹根是紅節點，則節點 P 的顏色違反了特性 1，

我們再觀察節點 x、a、P 的顏色關系，發現可以翻轉：

如圖，翻轉顏色后，不會改變 x 子樹中任何一條路徑上黑節點數量，而且解決了 P 和 α 子樹可能的顏色沖突，

不過，細心的你肯定發現問題了，顏色翻轉并沒有解決問題，只是將可能的沖突從下面轉移到了上面：翻轉后，x 的顏色有可能跟其父節點顏色沖突（同為紅色），

另外，如果 x 是 x.parent 的右子節點，則違反了特性 3——不過這一點倒可以通過左旋解決，

因而，翻轉顏色后，我們還要判斷 x.parent 的顏色，如果是黑色則萬事大吉，倘若是紅色，則需要遞回處理，直到整棵樹的根節點，

透過現象看本質，場景二（連續兩個紅節點）情況下，我們的目的是讓兩個紅節點向上合并成一個紅節點以消除沖突，向上合并的程序有可能造成新的沖突（新的連續紅節點），所以處理程序是遞回的，有可能一直遞回到整棵樹的根節點，該向上合并的程序，類比到 2-3 樹就是向上裂變的程序（因為連續兩個紅節點對應到 2-3 樹上就是一個待裂變的 4 節點），裂變也是遞回的，最終可能波及到根節點，

紅節點合并與裂變的對應關系如下：

上圖中一些特殊情況：

如果 P 節點不存在，則 b 會成為新的根（在紅黑樹中，需要將它再變成黑色）；
否則，在 2-3 樹中，b 提升后至少會形成 3 節點，對應紅黑樹中紅色 b 節點；
b 提升后也可能形成 4 節點（當原本的 P 就是 3 節點時），此時會繼續裂變，對應到紅黑樹中就是紅色 b 的父節點仍然是紅色；

最后一個問題是，當紅色合并操作遞回到整棵樹的根節點時會發生什么？

答案是：直接將根節點變成黑色，然后結束戰斗，

我們看看遞回到根節點時的幾種情況：

無論是哪種情況，將根節點變成黑色后都仍然滿足紅黑樹的性質：

不存在連續的紅節點；
當原本根節點是黑色時，自然沒問題；
當原本根節點時紅色時，變成黑色后，所有路徑上黑節點數都加 1，仍然滿足紅黑樹的性質；

再談三板斧

從上面例子可知，當我們想將右傾紅節點變成左傾紅節點以滿足特性 4 時要用到左旋，旋轉后，父節點位置的顏色保持不變，原先右邊的紅色跑道左邊去了，如圖：

代碼實作（TypeScript）：

/**
 * 將 h 圍繞其右子節點左旋，
 * @returns 回傳新的父節點
 */
function rotateLeft(h: Node): Node {
    assert(h && h.right)

    const x = h.right
    h.right = x.left
    x.left = h

    x.color = h.color
    h.color = 'RED'

    return x
}

對稱地，右旋如下：

代碼實作：

/**
 * 將 h 圍繞其左子節點右旋，
 * @returns 回傳新的父節點
 */
function rotateRight(h: Node): Node {
    assert(h && h.left)

    const x = h.left
    h.left = x.right
    x.right = h

    x.color = h.color
    h.color = 'RED'

    return x
}

顏色翻轉代碼實作：

/**
 * 將 h 和其兩個子節點執行顏色翻轉
 * 要求 h 的兩個子節點顏色相同而且和 h 的顏色不同
 */
function flipColors(h: Node) {
    assert(h && h.left && h.right)
    assert(h.left.color === h.right.color && h.left.color !== h.color)

    const hColor = h.color
    h.color = h.left.color
    h.left.color = hColor
    h.right.color = hColor
}

經分析發現，以上三種操作既不會破壞二叉搜索樹的性質，也不會導致任何一條“葉-根”路徑上黑節點數量發生改變，近乎完美——除了可能導致出現兩個連續的紅節點（破壞特性 1），因而實際使用中需要自下而上遞回處理，

插入操作的代碼實作

至此，我們完整實作一下紅黑樹的元素插入代碼：

interface Value {
    key: number;
    val: unknown;
}

/**
 * 定義樹的節點
 */
interface Node extends Value {
    left: Node | null;
    right: Node | null;
    color: 'RED' | 'BLACK';
}

class RedBlackTree {
    protected root: Node | null
    // 樹節點數量
    protected _size: number

    public constructor() {
        this.root = null
        this._size = 0
    }

    /**
     * 插入元素
     * 從根節點往下找，直到找到合適的位置后插入
     * 
     * @param key - 關鍵字
     * @param val - 衛星資料
     */
    public insert(key: number, val: unknown) {
        this.root = this.innerInsert(this.root, { key, val })
        // 處理完成后，將根節點變成黑色，結束戰斗
        this.root.color = 'BLACK'
        this._size++
    }

    /**
     * 遞回地往 p 子樹插入元素 value，并維護紅黑樹性質
     * @param p 
     * @param value
     * @returns 回傳子樹 p 新的根（插入并維護紅黑性質后，新的根節點不一定還是原來的那個節點了）
     */
    private innerInsert(p: Node | null, value: Value): Node {
        if (p === null) {
            // p 子樹是個空指標（空樹），創建并回傳新節點
            return this.newNode(value.key, value.val)
        }

        // p 是非空子樹，則視情況將 value 插入到 p 的左子樹或者右子樹中
        if (value.key < p.key) {
            p.left = this.innerInsert(p.left, value)
        } else {
            p.right = this.innerInsert(p.right, value)
        }

        // 修復 p 子樹的紅黑性質
        return this.balance(p)
    }

    /**
     * 對以 p 為根的子樹執行紅黑平衡修復讓該子樹符合紅黑樹的性質
     * 注意：情況一、二、三必須按順序執行，因為前面情況的解決可能帶來后面的情況
     * @param p 子樹的根
     * @returns 修復完成后回傳新的根（不一定是原先那個 p 了）
     */
    private balance(p: Node): Node {
        // 情況一（右傾），執行左旋
        if (!this.isRed(p.left) && this.isRed(p.right)) {
            p = this.rotateLeft(p)
        }

        // 情況二：連續兩個左傾的紅節點
        if (this.isRed(p.left) && this.isRed(p.left.left)) {
            p = this.rotateRight(p)
        }

        // 情況三：一個黑節點下面掛兩個紅節點，其中右邊的紅節點違反了“左傾”原則，通過翻轉顏色解決
        if (this.isRed(p.left) && this.isRed(p.right)) {
            this.flipColors(p)
        }

        return p
    }

    /**
     * 新節點默認是紅色
     */
    protected newNode(key: number, val: unknown): Node {
        return { key, val, left: null, right: null, color: 'RED', size: 1 }
    }

    /**
     * 讓節點 h 相對于 h.right 執行左旋
     */
    protected rotateLeft(h: Node): Node {
        // 見前面實作
    }

    /**
     * 讓節點 h 相對于 h.left 執行右旋
     */
    protected rotateRight(h: Node): Node {
        // 見前面實作
    }

    /**
     * 翻轉顏色
     */
    protected flipColors(h: Node) {
        // 見前面實作
    }

    /**
     * 判斷節點 node 是否為紅色
     * 規定 null 節點是黑色
     */
    protected isRed(node: Node | null): boolean {
        if (!node) {
            return false
        }

        return node.color === 'RED'
    }
}

洗掉

樹形資料結構中，洗掉操作總是最復雜的，紅黑樹也不例外，

“初步看，洗掉得分兩種情況：被洗掉的節點是葉子節點，或者是非葉子節點......”

“你等等，我好像發現了個重大問題！” R 教授突然打斷了 L 教授的滔滔不絕，

“啥？”被這樣硬生生地打斷，L 教授顯然有些不爽，

“你說葉子節點——這里有問題！” R 教授指著下面這棵紅黑樹：

現在刪掉葉子節點 7，會怎樣？

“嗯......不會怎樣，仍然滿足紅黑樹全部特性，換句話說，它仍然是一棵紅黑樹，” L 教授若有所思，他好像也意識到了什么，

“這正是問題所在，這棵樹刪掉節點 7 后仍然是一棵合法的紅黑樹，但它卻無法轉換成 2-3 樹！” R 教授道，

所以我們必須保證任何一條路徑不會因為刪掉一個節點而消失，上圖中如果路徑（7-6-8-4）不因洗掉 7 而消失，那么刪掉 7 以后這個路徑便少了一個黑節點，從而不再滿足紅黑樹的性質，

“或許我們可以引入哨兵——具體來說，我們讓每個實節點都必須有兩個子節點，如果沒有，則用哨兵節點代替，為了不讓哨兵的顏色影響實節點的顏色，哨兵節點必須是黑色（如實節點是紅色，如果哨兵也是紅色，則會違反特性 1），” L 教授說道，

“這是個好主意，既然這些哨兵都出現在空節點的位置上，不妨就稱這些哨兵為 nil 節點吧，” R 教授說著畫出添加哨兵后的紅黑樹：

也就是說，特性 2 所提及的“葉節點”實際上是指哨兵節點（nil），而不是最下面的實節點，

2-3 樹必須是完全平衡的搜索樹，而上面這個（刪掉節點 7 后）有問題的 2-3 樹并不是一棵平衡樹，不過這點從圖中并不能明顯地看出來，如果轉成代碼則較明顯：
var node = {
 // 本節點元素數量
 size: 2,
 // 元素陣列，升序排列
 elements: [6, 8],
 // 子節點陣列
 // node1 的值是 [5]
 // node2 是 null
 // node3 的值是 [9, 10]
 children: [node1, null, node3]
}
如上表示節點 node(6,8)，從 children 可見，第二個子節點是 null，而其它兩個均有實際子節點，因而這里不再平衡，
所以，實際上在設計 2-3 樹的時候就應該引入哨兵節點的概念了，如果 2-3 樹引入了哨兵節點，那么轉換為紅黑樹后，自然將哨兵的概念帶過來了，

那么，我們如何洗掉上面的節點 7 呢？

我們知道，對于一條路徑，洗掉路徑上的紅色節點不會影響路徑上黑色節點數量，

所以，如果我們能先將節點 7 變成紅色，然后再洗掉就行了，

如果節點 7 本身就是紅色的，那么直接洗掉就行了，

如果節點 7 是黑色的（如上圖所示），怎樣將 7 變成紅色節點呢？

我們只看節點 7 到根節點這條路徑：