Homework 3 - Set

課程名稱：資料結構 CS203 A
授課教師：林基成
發放時間：2020-09-29
截止時間：2020-10-06

---

題目說明

完成 Set 中使用到的紅黑樹中的部分函式。

解題思路

這次作業的結構為內部為二元紅黑樹的 Set，由於 Code 內已有註解，在此不再贅述，只說大方向的做法。

插入元素:

1. void insert(const value_type &val)

   • 函式功能： 插入一個元素到 Set 中，若元素已經存在則不插入。
   • 參考作法： 先判斷該值是否已經存在，若不存在則找到該值的 parent ( degree <= 1 )，並調整紅黑樹的平衡。
   • 參考解法：

     // Extends the container by inserting a new element,
     // effectively increasing the container size by one.
     void insert( const value_type &val )
     {
         // head -> the reference of scaryVal.myHead
         // node -> new node's parent
         // dummy -> dummy node
         TreeNode< value_type >* head = scaryVal.myHead;
         TreeNode< value_type >* node = head;
         TreeNode< value_type >* dummy = head->parent;
     
         // find new node's parent also find if the key already exists or not
         while (!dummy->isNil && node->myval != val)
             node = dummy, dummy = keyCompare(val, dummy->myval) ? dummy->left : dummy->right;
             
         // if the key already exists
         if (val == node->myval) return;
     
         // new node's color should be red first
         auto newNode = new TreeNode< value_type >{ head, node, head, red, false, val };
         ++scaryVal.mySize;
     
         // connect node and new node, if new node is the root, update head's parent
         if (node->isNil) head->left = head->right = head->parent = newNode;
         else keyCompare(val, node->myval) ? node->left = newNode : node->right = newNode;
     
         // update head's pointers
         if (keyCompare(val, head->left->myval)) head->left = newNode;
         if (keyCompare(head->right->myval, val)) head->right = newNode;
     
         scaryVal.reBalance(newNode);
     }

2. void reBalance(TreeNode< value_type > *node)

   • 函式功能： 調整插入元素後造成的失衡。node->color 必為紅色。
   • 參考作法： 根據基哥上課時講解的情況完成即可，在此不多贅述。
   • 參考解法：

     // rebalance for insertion
     void reBalance( TreeNode< value_type > *node )
     {   // node->parent cannot be the root
         // refer to the video of class and the internet
         // p -> parent, g -> grand, u -> uncle
         TreeNode< value_type >* p = node->parent;
         TreeNode< value_type >* g = node->parent->parent;
         TreeNode< value_type >* u = p == g->left ? g->right : g->left;
         
         // Case 1 -> node is the root, make node black
         if (p->isNil) { node->color = black; return; }
     
         // boundary condition of Case 2
         if (p->color == black) return;
     
         // XYr
         if (u->color == red)
         {   // Case 2 -> LLr, LRr, RLr, or RRr
             p->color = u->color = black;
             g->color = red;
             // do the same thing to g
             reBalance(g);
             return;
         }
     
         // XYb
         if (p == g->left && node == p->left)
         {   // Case 3 -> LLb
             LLRotation(p); // rotate right at g
             swap(p->color, g->color);
             return;
         }
     
         if (p == g->right && node == p->right)
         {   // Case 4 -> RRb
             RRRotation(p); // rotate left at g
             swap(p->color, g->color);
             return;
         }
     
         if (p == g->left && node == p->right)
         {   // Case 5 -> LRb
             // rotate left at p first, then rotate right at g
             LRRotation(node);
             swap(node->color, g->color);
             return;
         }
     
         if (p == g->right && node == p->left)
         {   // Case 6 -> RLb
             // rotate right at p first, then rotate left at g
             RLRotation(node);
             swap(node->color, g->color);
         }
     }

3. LLRotation(TreeNode< value_type > *p)

   • 函式功能： 在 g 右旋轉，p = g->left 且 node = p->left。建議搭配圖片來看會較清楚。
   • 參考作法： 將對應的 node 相連即可，需要注意的是若 p->right 為 nil node，則不能更改 p->right->parent，因為會改動到 myHead->parent，使得找不到 root。並且若 g 原本為 root，則 p 頂替 g 的位置時需要改變的是 myHead->parent，而不是 left 或 right。
   • 參考解法：

     // rotate right at g, where p = g->left and node = p->left
     //void set< Kty >::LLbRotation( TreeNode< value_type > *node )
     void LLRotation( TreeNode< value_type > *p )
     {
         TreeNode< value_type >* g = p->parent;
     
         // connect g and p's right child
         g->left = p->right;
         if (!p->right->isNil) p->right->parent = g;
     
         // connect g's parent and p
         if (g->parent->isNil) myHead->parent = p;
         else g == g->parent->left ? g->parent->left = p : g->parent->right = p;
         p->parent = g->parent;
     
         // connect p and g
         p->right = g;
         g->parent = p;
     }

4. void RRRotation(TreeNode< value_type > *p)

   • 函式功能： 在 g 左旋轉，p = g->right 且 node = p->right。建議搭配圖片來看會較清楚。
   • 參考作法： 與上面的右旋轉差不多，在此不多贅述。
   • 參考解法：

     // rotate left at g, where p = g->right and node = p->right
     //void set< Kty >::RRbRotation( TreeNode< value_type > *node )
     void RRRotation( TreeNode< value_type > *p )
     {
         TreeNode< value_type >* g = p->parent;
     
         // connect g and p's left child
         g->right = p->left;
         if (!p->left->isNil) p->left->parent = g;
     
         // connect g's parent and p
         if (g->parent->isNil) myHead->parent = p;
         else g == g->parent->left ? g->parent->left = p : g->parent->right = p;
         p->parent = g->parent;
     
         // connect p and g
         p->left = g;
         g->parent = p;
     }

5. void LRRotation(TreeNode< value_type > *node)

   • 函式功能： 先在 p 左旋轉，接著在 g 右旋轉，g 為左旋轉前的 g。p = g->left 且 node = p->right。
   • 參考作法： 呼叫上面的函式即可，需要注意的是該傳入哪個 node，搭配圖片看就很清楚了。
   • 參考解法：

     // LR rotation; p = g->left and node = p->right
     void LRRotation( TreeNode< value_type > *node )
     {   // LRb rotation
         RRRotation(node); // rotate left at p first
         LLRotation(node); // then rotate right at g
     }

6. void RLRotation(TreeNode< value_type > *node)

   • 函式功能： 先在 p 右旋轉，接著在 g 左旋轉，g 為右旋轉前的 g。p = g->right 且 node = p->left。
   • 參考作法： 與上面的先左旋轉再右旋轉相同，在此不多贅述。
   • 參考解法：

     // RL rotation; p = g->right and node = p->left
     void RLRotation( TreeNode< value_type > *node )
     {   // RLb rotation
         LLRotation(node); // rotate right at p first
         RRRotation(node); // then rotate left at g
     }

---

刪除元素:

7. size_type erase(const key_type &val)

   • 函式功能： 刪除 Set 中值為 val 的元素，並回傳刪除的元素數量。
   • 參考作法： 先判斷值是否存在，若不存在直接回傳 0。若存在則判斷該 node 是否存在兩個 child，若存在兩個 child 則從 node 的右子樹中找到最左邊的 node 的值來取代要刪除的 node，接著刪除剛剛找到的 node。若為 leaf node 或只存在一個 child，則直接刪除 ( 呼叫 eraseDrgreeOne() )。值得注意的是回傳的值必為 0 或 1，因為 Set 不允許存在兩個相同值的元素，所以最多只會找到一個要刪除的 node。
   • 參考解法：

     // Removes from the set container a single element whose value is val
     // This effectively reduces the container size by one, which are destroyed.
     // Returns the number of elements erased.
     size_type erase(const key_type &val)
     {
         TreeNode< value_type >* node = scaryVal.myHead->parent; // root
     
         // find the key
         while (!node->isNil && val != node->myval)
             node = keyCompare(val, node->myval) ? node->left : node->right;
     
         // not found
         if (node->isNil) return 0;
     
         // if node has two children
         if (!node->left->isNil && !node->right->isNil)
         {   // let the node's right subtree's leftmost node's val replace node's val
             TreeNode< value_type >* RL = node->right;
             while (!RL->left->isNil) RL = RL->left;
             node->myval = RL->myval;
             node = RL; // delete RL
         }
     
         scaryVal.eraseDegreeOne(node);
     
         return 1;
     }

8. void eraseDegreeOne(TreeNode< value_type > *node)

   • 函式功能： 刪除一個 degree <= 1 的 node。
   • 參考作法： 根據基哥上課講解的情況完成即可。註解有列出情況及對應的操作，在此不多贅述。
   • 參考解法：

     // erase node provided that the degree of node is at most one
     void eraseDegreeOne( TreeNode< value_type > *node )
     {   // refer to the video of class
         // M -> the node need to delete
         // P -> M's parent, if M is the root, P is myHead
         // C -> M's only child, if M doesn't have any child, C is the nil node
         TreeNode< value_type >* M = node;
         TreeNode< value_type >* P = node->parent;
         TreeNode< value_type >* C = node->left->isNil ? node->right : node->left;
     
         // Simple Case 3 -> M and C are black, and M is the root
         if (M->color == black && C->color == black && P->isNil)
         {   // delete M and make C be the root
             myHead->parent = C;
             C->parent = myHead;
             delete M;
             --mySize;
             return;
         }
         
         // Simple Case 1 -> M is red or M is a leaf node : delete M and connect P and C
     
         // connect P and C
         M == P->left ? P->left = C : P->right = C;
         if (!C->isNil) C->parent = P;
     
         // Complex Case -> M and C are black, and M is not the root : connect P and C, then rebalance
         if (M->color == black && C->color == black && !P->isNil) fixUp(C, P);
         
         // Simple Case 2 -> M is black, C is red : delete M, connect P and C, and make C black
         if (M->color == black && C->color == red) C->color = black;
     
         delete M;
         --mySize;
         return;
     }

9. void fixUp(TreeNode< value_type > *N, TreeNode< value_type > *P)

   • 函式功能： 調整刪除 node 後造成的失衡。

   • 參考作法： 根據基哥附在作業中的 PPT 完成即可，在此不多贅述。

   • 參考解法：

     // rebalance for deletion
     void fixUp( TreeNode< value_type > *N, TreeNode< value_type > *P )
     {   // refer to Assignment 3.pptx
         TreeNode< value_type >* S = N == P->left ? P->right : P->left; // N's sibling
         
         // Case 1
         if (S->color == red && N == P->left)
         {   // Case 1.1 -> S is red and N is P's left child
             swap(P->color, S->color);
             RRRotation(S); // rotate left at P
             // update S, then go to Case 2.1, 3.1, or 4
         }
         if (S->color == red && N == P->right)
         {   // Case 1.2 -> S is red and N is P's right child
             swap(P->color, S->color);
             LLRotation(S); // rotate right at P
             // update S, then go to Case 2.2, 3.2, or 4
         }
     
         // update S
         S = N == P->left ? P->right : P->left;
     
         // Case 3
         if (S->color == black && S->right->color == black && N == P->left && S->left->color == red)
         {   // Case 3.1 -> S and SR are black, N is P's left child, but SL is red
             swap(S->color, S->left->color);
             LLRotation(S->left); // rotate right at S
             // update S, then go to Case 2.1
         }
         if (S->color == black && S->left->color == black && N == P->right && S->right->color == red)
         {   // Case 3.2 -> S and SL are black, N is P's right child, but SR is red
             swap(S->color, S->right->color);
             RRRotation(S->right); // rotate left at S
             // update S, then go to Case 2.2
         }
     
         // update S
         S = N == P->left ? P->right : P->left;
     
         // Case 2
         if (S->color == black && S->right->color == red && N == P->left)
         {   // Case 2.1 -> S is black, SR is red and N is P's left child
             swap(P->color, S->color);
             S->right->color = black;
             RRRotation(S); // rotate left at P
             return;
         }
         if (S->color == black && S->left->color == red && N == P->right)
         {   // Case 2.2 -> S is black, SL is red and N is the right child of P
             swap(P->color, S->color);
             S->left->color = black;
             LLRotation(S); // rotate right at P
             return;
         }
     
         // Case 4 -> S, SR and SL are black, but P is red
         if (S->color == black && S->right->color == black && S->left->color == black && P->color == red)
         {   // Just exchange the colors of S and of P
             swap(S->color, P->color);
             return;
         }
     
         // Case 5 -> S, SR, SL and P are black
         if (S->color == black && S->right->color == black && S->left->color == black && P->color == black)
         {
             S->color = red;
             fixUp(P, P->parent);
         }
     }

Reference

Red Black Tree: Insert(新增資料)與Fixup(修正)