2023q1 Homework4 (quiz4)

contributed by < paul90317 >

題目連結

?

可以先理解 2,3,4 樹的插入和刪除流程，再將其轉換成如果是紅黑樹要怎麼做。以下是節點的轉換 (子節點必須是黑色，意味下一層的 2,3,4 節點)
2 節點

 b
/ \

3 節點 (左傾的三節點可以幫助插入和刪除少探討一些情況)

  b
 / \
 r
/ \

4 節點 (後來發現這棵樹沒有四節點)

  b
 / \
 r  r
/ \/ \

該樹的假設

這是我後來的發現，該樹除了傳統左傾紅黑樹的定義以外還多了沒有 4 節點的假設，所以該樹插入刪除更像 23 樹。為求方便，我們可以將沒有4節點的條件換成紅節點只可以接在黑節點的右邊。

插入演算法證明

在插入前，必須要找到需要插入的 NIL 節點，這是 top-down 的過程。插入的節點會是紅色的，因為在 2,3,4 樹中，會把新的 key 放到最底一層的 2,3,4 節點中。這會造成兩個紅色節點相連，也就是 buttom-up 要解決的問題。
因為一開始插入的紅節點本身是一顆合理的樹 (下面的歸納法會定義何謂合理的樹)，所以會跳過所插入的紅色節點，從其親節點開始走訪。對於所有即將走訪的節點無非是以下這幾種情況，其中 b 是程式跳過的情況，我也會證明跳過不影響程式正確性(電腦繪圖待補)。

Basic: 第一次走訪只會是 b,e,f 三種情況之一。
Induction: 演算法走訪時會出現 a,b,c,d,e,f 幾種情況 (已經列舉所有情況)。其中 b,f 情況 cnode 的顏色是未知的，我將其分成 b1,b2,f1,f2 以方便證明。經過觀察可得:

1. 子樹經過走訪後，其高度不變
2. 子樹經過走訪後，不出現紅色節點連續兩個的情況。
3. 當上述兩點為真，迴圈可以在 a,d 情況結束 (前一走訪子樹的根是黑色)。
4. 當程式到整棵樹的根 (沒進 a,d)，可以將根節點變成黑色，整棵樹會是紅黑樹。

第一點 a-f 處理後都可以達成，然而第二點 b2, f2 無法達成，但是下次走訪經過 c 或 e 處理後就可以達成第二點。注意 b2, f2 不會進到 f1, f2，因為 b2 的 cnode 沒有變色及旋轉，所以它之上的 edge 會維持該樹假設:

• 紅節點只能接在黑節點右邊

---

AAAA 在情況 c，要填入把左左節點變成黑色的程式碼，故是 rbtn_black_set。
BBBB, CCCC 在情況 f，BBBB 是 tred，CCCC 是 rbtn_red_set。

移除演算法證明

如果欲移除的節點是 internal node 會不方便移除。在題目程式碼中，會先找到它的 upper bound 跟欲移除節點交換位置。再將欲移除節點移除。找到某節點的 upper bound 方法如下:

1. 找到目標節點，存入 nodep->node (讓 nodep 指向 path 的特定位置)
2. 往右走
3. 往左走到底，找到 pathp->node

於是 DDDD 是 nodep->node (目標節點) 下一節點的方向，是 1。
接著要指派他們在 path 及樹上的位置和顏色。

        /* nodep->node 與 node 應指向同一塊記憶體 */
        assert(nodep->node == node);                                           \
        pathp--;                                                               \
        if (pathp->node != node) {                                             \
            /* Swap node with its successor. */                                \
            /* 若 pathp->node 如果與目標 node 不同 */
            /* 會將 pathp->node 的子節點與顏色指派成 node 的 */
            bool tred = rbtn_red_get(x_type, x_field, pathp->node);            \
            rbtn_color_set(x_type, x_field, pathp->node,                       \
                           rbtn_red_get(x_type, x_field, node));               \
            rbtn_left_set(x_type, x_field, pathp->node,                        \
                          rbtn_left_get(x_type, x_field, node));               \
            /* If node's successor is its right child, the following code */   \
            /* will do the wrong thing for the right child pointer.       */   \
            /* However, it doesn't matter, because the pointer will be    */   \
            /* properly set when the successor is pruned.                 */   \
            rbtn_right_set(x_type, x_field, pathp->node,                       \
                           rbtn_right_get(x_type, x_field, node));             \
            rbtn_color_set(x_type, x_field, node, tred);                       \
            /* The pruned leaf node's child pointers are never accessed   */   \
            /* again, so don't bother setting them to nil.                */   \
            nodep->node = pathp->node;                                         \
            pathp->node = node;                                                \
            /* 指派 nodep->node 親節點 */
            if (nodep == path) {                                               \
                rbtree->root = nodep->node;                                    \
            } else {                                                           \
                if (nodep[-1].cmp < 0) {                                       \
                    rbtn_left_set(x_type, x_field, nodep[-1].node,             \
                                  nodep->node);                                \
                } else {                                                       \
                    rbtn_right_set(x_type, x_field, nodep[-1].node,            \
                                   nodep->node);                               \
                }                                                              \
            }                                                                  \
        } else {                                                               \
            /* 如果是同一個，也就是 nodep->node 沒有右樹 */
            x_type *left = rbtn_left_get(x_type, x_field, node);               \
            if (left) {                                                        \
                /* 若有左樹 */
                /* node has no successor, but it has a left child.        */   \
                /* Splice node out, without losing the left child.        */   \
                /* node 應為黑色 */
                assert(!rbtn_red_get(x_type, x_field, node));                  \
                /* 左樹之根應為紅色，並根據紅黑樹性質 */
                assert(rbtn_red_get(x_type, x_field, left));                   \
                /* 根據紅黑樹性質，左樹應只有一個節點 */
                /* 將 3節點變成 2節點 */
                rbtn_black_set(x_type, x_field, left);                         \
                /* 指派 nodep->node 親節點 */
                if (pathp == path) {                                           \
                    rbtree->root = left;                                       \
                    /* Nothing to summarize -- the subtree rooted at the  */   \
                    /* node's left child hasn't changed, and it's now the */   \
                    /* root.                                              */   \
                } else {                                                       \
                    if (pathp[-1].cmp < 0) {                                   \
                        rbtn_left_set(x_type, x_field, pathp[-1].node, left);  \
                    } else {                                                   \
                        rbtn_right_set(x_type, x_field, pathp[-1].node, left); \
                    }                                                          \
                }                                                              \
                return;                                                        \
            } else if (EEEE) {                                                 \
                /* The tree only contained one node. */                        \
                rbtree->root = NULL;                                           \
                return;                                                        \
            }                                                                  \
        }      

EEEE 需要判斷使否只有一個節點欲刪除，在沒有子節點的情況下，pathp==path，故 EEEE 是 pathp==path。
整理一下

如果欲刪除及欲交換節點不同
    將欲交換節點取代欲刪除節點，並繼承顏色
否則
    //在此情況中，與刪除節點沒有右樹
    若有左樹
        //根據紅黑樹性質，左樹僅有一個紅色節點
        將左邊的節點變成黑色取代欲刪除節點
        紅黑樹性質符合，結束
    //在這裡已經確定欲刪除節點沒有子節點
    否則若欲刪除節點是根
        刪除它
        紅黑樹空，結束
    //否則我們刪除了黑色節點，需要透過 buttom-up 調整。

如果欲刪除的節點是紅色
    //他應是左節點，否則欲刪除節點會是交換節點右邊唯一紅節點，與該樹假設定義矛盾。
    在以上的情況下可以直接刪除，並結束
//否則刪到二節點，需要往上找一顆節點補足失去的高度。
    

我讀到 rb.h 375 行，覺得這個斷言特別奇怪，就算欲刪除的節點是紅的，它也可以在親節點的右邊啊。之後回想起 /* Split 4-node. */ 的神奇註解。最後再回頭看我 insert 的證明，發現我在情況 c 少考慮到 cnode 有邊是紅色節點的情況，如果是紅色節點，就無法維持左傾。但是只要該紅黑樹裡沒有 4-node，那麼插入演算法就可以維持樹的左傾，且他也不會產生 4-node。
總結而言，以 234樹是無法推敲這顆紅黑樹代碼的，因為這顆紅黑樹是 23樹。

已經修改前面的錯誤

接著來理解以下 rotate 巨集:

1. rbtn_rotate_left(x_type, x_field, x_node, r_node)
r_node 是輸出，會指向旋轉前 x_node 的右邊節點。旋轉後 x_node 會在 r_node 左邊。
2. rbtn_rotate_right(x_type, x_field, x_node, r_node)
r_node 是輸出，會指向旋轉前 x_node 的左邊節點。旋轉後 x_node 會在 r_node 右邊。

接下來我們需要透過 buttom-up 補足失去的高度，走訪後的每個子樹必須是 23樹。修改前的樹的根的左節點或右節點會是前一個走訪的樹，這棵樹固然是 23樹，但其高度會比其他子樹少1。每次走訪:

1. 必須透過旋轉及變色多丟一個黑節點下去，使上一走訪樹的深度增加，且滿足23樹性質。結束。
2. 或是透過旋轉及變色讓其他子樹深度少一，這樣子當前的子樹也會滿足 23 樹性質，只是要再走訪親節點補除缺少的高度。

當走訪到整棵樹的根都無法結束，我們還是維持了整棵樹是23樹的性質，但是高度少一。以下每次走訪需要判斷的情形 (電腦繪圖待補):

首先是上一個走訪的樹是左邊的情況
a. 親節點與平輩節點都是三節點，透過旋轉(及變色)可以發現前一個走訪的樹相對深度多一，相當於前一個走訪的樹向平輩借了一顆節點去補足自己失去的高度。於是這棵數變成一顆紅黑樹且高度與刪除前不變，結束。
b. 當親節點是三節點，平輩是二節，前一走訪的子樹會透過合併向親節點借一個節點補足高度。
c. 透過旋轉向平輩借一顆節點。
d. 沒人可以借，透過合併將其他子樹(三角形)的高度減一，讓下一走訪的點處理。

接下來看到前一走訪節點在右邊的情況，e,f,g,h 都是親節點是三節點，但是將23樹轉左傾紅黑樹後，會有在紅節點右邊(gh)或是黑節點右邊(ef)的情況。

剩下的親節點為二節點的情況，接下來把情況整理成 pseudo code:

若平輩為三節點
    轉過來
    結束
否則
    和下來
    若親節點從三節點變成二節點
        結束
    否則
        繼續走訪

---

FFFF 是 rbtn_rotate_left
GGGG 是 rbtn_rotate_right