Cây Đỏ Đen (Red-Black Tree) – Phần 2 (Insert)
Ở bài trước, chúng ta đã tìm hiểu sơ qua về cây đỏ đen – Red Black Tree. Còn trong bài viết này, ta sẽ cùng nhau đi tìm hiểu cách để thêm (insert) một node vào cây đỏ đen.
Phần 1: Cây Đỏ Đen (Red-Black Tree) – Phần 1 (Giới thiệu)
NỘI DUNG BÀI VIẾT
1. Ôn lại kiến thức và Quy ước gọi tên
Trước khi bắt đầu thì chúng ta nên ôn lại kiến thức một tý: cây đỏ đen là gì? Nó như thế nào? Có những quy tắc chi? Cây đỏ đen là cây mà mọi node đều có thêm thuộc tính bit – quy định màu sắc (đỏ hoặc đen). Trong đó có 2 trong 5 quy tắc rất quan trọng:
-
-
-
- Không có hai node đỏ liền kề (Một node đỏ thì không thể có cha đỏ hoặc con đỏ).
- Mọi đường dẫn từ một node đến bất kì node NULL (thuộc con của nó ) thì đều có cùng số lượng node đen.
-
-
Về cách gọi tên các Node:
x->parent: đây được gọi là Node cha của x.
x->parent->left: đây là Node anh em của x (có thể right, tùy trường hợp)
x->parent->parent: chính là Node ông của x
x->parent->parent->left: được gọi là Node chú của x (có thể right, tùy trường hợp)
Note: Root (R viết hoa) là từ dùng để chỉ root của cả cây đỏ đen. Còn root thì dùng để chỉ node đang nằm trong các hàm.
2. Cấu trúc dữ liệu và cách để insert
a) Nhắc lại cây AVL
Đối với cây AVL mình chỉ cần tạo một struct Node rồi sau đó sử dụng đệ quy để thêm vào cây. Bởi vì tất cả các node của cây AVL đều có vai trò như nhau, bình đẳng nhau (kể cả root) nên mới sử dụng đệ quy như vậy được.
|
1 2 3 4 5 6 |
struct Node { int data; Node* left; Node* right; int height; }; |
|
1 2 3 4 5 6 7 8 9 10 11 |
Node* Insert(Node* root, int value) { // Tìm kiếm vị trí rồi thêm vào if (root == NULL) return new Node{ value, NULL, NULL, 1 }; // Trả về Node có height = 1 if (value > root->data) root->right = Insert(root->right, value); else if (value < root->data) root->left = Insert(root->left, value); else return root; // Neu bang thi khong them // Xử lí ... |
b) Về Red-Black Tree
Đối với cây đỏ đen, ta không cần biết chiều cao của cây bằng bao nhiêu như cây AVL. Thay vào đó ta cần phải biết node cha (parent) màu gì? Có cùng màu đỏ với con hay không? Vậy nên phải thêm vào một con trỏ nữa, và tất nhiên là không thể thiếu thuộc tính color – chỉ màu sắc của một node với:
-
-
-
-
-
- 1 – True : Chỉ màu đỏ
- 0 – False: Chỉ màu đen
-
-
-
-
|
1 2 3 4 5 6 7 8 |
struct Node { int data; Node* left; Node* right; Node* parent; bool color; //1 -> Red | 0 -> Black }; |
Tuy nhiên, khác với cây AVL, các node của RBTree không bình đẳng. Có một node đặc biệt, đó chính là Root. Node Root luôn luôn phải mang màu đen – quy tắc 2. Do đó mình sẽ tạo thêm một struct RBTree nhằm kiểm soát được Root.
Các bạn đọc sơ qua code, rồi xem kĩ lại theo thứ tự phía dưới nha:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
struct RedBlackTree { Node* Root; RedBlackTree() { Root = NULL; } Node* insertHelp(Node* root, int key) { if (root == NULL) { // Luôn luôn thêm node đỏ return new Node{ key, NULL, NULL, NULL, 1 }; // RED Node } else if (root != NULL && key < root->data) { // Node X : root->left // X->parent : root root->left = insertHelp(root->left, key); root->left->parent = root; } else { // Node X : root->right // X->parent : root root->right = insertHelp(root->right, key); root->right->parent = root; } return root; } void Insert(int key) { if (Root == NULL) { // Root luôn màu đen Root = new Node{ key, NULL, NULL, NULL, 0 }; } else { Root = insertHelp(Root, key); if (Root->color == 1) Root->color = 0; } } |
- Node* Root: mình phải luôn luôn kiểm soát được màu sắc Node này.
- RedBlackTree(): đây là Constructor – hàm khởi tạo (xem thêm tại Lập trình hướng đối tượng). Hiểu đơn giản là khi mình khởi tạo 1 đối tượng RedBlackTree tree. Thì khi đó mặc định tree->Root = NULL.
- Insert(): Hàm này dùng để thêm 1 node vào nhưng… nó chỉ quan tâm đến node Root. Nếu Root == NULL thì gán vào Root với màu đen. Ngược lại nếu Root != NULL thì chỉ cần giao cho một hàm khác giải quyết – insertHelp(). Giả sử hàm này vô tình đổi màu Root thành màu đỏ thì chỉ cần tô lại đen.
- insertHelp(): Khi Root đã được xử lí riêng thì tất cả các node còn lại đều bình đẳng. Do đó ta chỉ cần sử dụng đệ quy như cây AVL để thêm node mới vào. Tuy nhiên, vì có thêm thuộc tính parent nên sau thêm ta phải gán giá trị của parent vào.
Lưu ý: Các node mới được thêm vào luôn luôn màu đỏ.
Tại sao ư? Ở bài trước, mình có nói: không thể có 3 node đen liên tiếp. Giả sử bạn thêm một node đen vào thì phải kiểm tra node cha có màu đen hay không? Node ông có màu đen không? Chưa kể, bạn phải kiểm tra các đường đi có số node đen bằng nhau không? Quá phức tạp.
Tuy nhiên nếu mình thêm node đỏ thì sao? Các đường đi vẫn đảm bảo số node đen bằng nhau vì mình chả thêm node đen nào cả. Và mình chỉ cần kiểm tra node cha, nếu màu đen thì ok – ổn, còn nếu màu đỏ thì chỉ cần xử lí xung đột đỏ.
3. Các phép quay cây đỏ đen
Hoàn toàn tương tự như cách quay cây AVL, RBTree cũng có hai cách quay đó là: quay phải, quay trái. Khác một tý là các bạn phải gán lại parent cho những node bị thay đổi. Và ngoài ra, lúc quay không đụng gì đến màu sắc nên bạn không cần phải để ý đâu.
a) Kỹ thuật quay phải – rotateRight
Gọi Node x, y lần lượt là các con trái, phải của root. Bây giờ, ta chỉ cần chú ý đến 3 Node: root, x, x.right.
Con trái của root không còn là x nữa mà là x.right hay root.left = x.right
Nếu x.right != NULL thì x.right->parent = root
X sẽ lên làm Node cha với con phải là root hay x.right = root
Khi đó cha của root là x ==> root.parent = x
Trả về x
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Node* rotateRight(Node* root) { Node* x = root->left; // Gán x->right vào left root root->left = x->right; if (x->right != NULL) x->right->parent = root; // Gán root vào x.right x->right = root; root->parent = x; // Trả về x return x; } |
b) Kỹ thuật quay trái – rotateLeft
Hoàn toàn tương tự, gọi x y lần lượt là các con trái phải của root. Và ta chỉ cần quan tâm 3 Node: root, y, y.left
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Node* rotateLeft(Node* root) { Node* y = root->right; // Gán y->left vào right root root->right = y->left; if (y->left != NULL) y->left->parent = root; // Gán root vào y.left y->left = root; root->parent = y; // Trả về y; return y; } |
4. Xử lí xung đột đỏ – insertHelp()
Khi ta thêm một node đỏ X vào cây, sẽ có 3 trường hợp xảy ra:
-
- Node cha màu đen. (Hoàn toàn ok – không cần xử lí gì cả)
- Node cha màu đỏ, Node chú cũng màu đỏ.
- Node cha màu đỏ, Node chú màu đen
Note: Node cha đỏ thì Node ông chắc chắn màu đen
1. Cha đỏ – Chú đỏ
Cách xử rất đơn giản, chỉ cần đổi màu 3 node sau:
-
- Node cha: đỏ => đen
- Node chú: đỏ => đen
- Node ông: đen => đỏ
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// root chính là X->parent nha if (root->parent->right == root){ // Nếu X->parent là con phải của Node ông root->color = root->parent->left->color = 0; if (root != Root) root->parent->color = 1; } else{ // Nếu X->parent là con trái của Node ông root->color = root->parent->right->color = 0; if (root != Root) root->parent->color = 1; } |
Về cơ bản thì cây con trên đã cân bằng và thỏa mãn 5 qui tắc cây đỏ đen. Tuy nhiên sẽ có người hỏi rằng: Node ông màu đỏ, nếu cha của node ông cũng màu đỏ thì sao? Thì mình sẽ xử lí tiếp thôi, ở đây mình sử dụng đệ quy nên nó sẽ dần dần truy hồi đến các Node tổ tiên. Gặp xung đột đỏ ở đâu thì xử lí ở đó.
2. Cha đỏ – Chú đỏ
Sẽ có 4 trường hợp: Trái trái, Trái phải, Phải phải, Phải phải, Phải trái. Cách xử lí thì hoàn toàn tương tự cây AVL chỉ thêm bước tô màu.
a) Trái trái – Left left case
Xảy ra khi:
Node cha: là con trái của ông
Node X : là con trái của cha
Xử lí:
-
-
- Quay phải Node ông
- Node cha: đỏ -> đen
- Node ông: đen -> đỏ
-
b) Trái phải – Left right case
Xảy ra khi:
Node cha: là con trái của ông
Node X : là con phải của cha
Xử lí:
-
-
- Quay trái Node cha (Đưa về Left left case)
- Xử lí y như trường hợp Trái trái
-
c) Phải phải – Right right case
Xảy ra khi:
Node cha: là con phải của ông
Node X : là con phải của cha
Xử lí:
-
-
- Quay trái Node ông
- Node cha: đỏ -> đen
- Node ông: đen -> đỏ
-
d) Phải trái – Right right case
Xảy ra khi:
Node cha: là con phải của ông
Node X : là con trái của cha
Xử lí:
-
-
- Quay phải Node cha (Đưa về Right right case)
- Xử lí y như trường hợp Phải phải
-
5. Code chính
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 |
#include <iostream> #include <cmath> using namespace std; #define COUNT 10 struct Node { int data; Node* left; Node* right; Node* parent; bool color; //1 -> Red | 0 -> Black }; Node* rotateRight(Node* root) { Node* x = root->left; // Gán x->right vào left root root->left = x->right; if (x->right != NULL) x->right->parent = root; // Gán root vào x.right x->right = root; root->parent = x; // Trả về x return x; } Node* rotateLeft(Node* root) { Node* y = root->right; // Gán y->left vào right root root->right = y->left; if (y->left != NULL) y->left->parent = root; // Gán root vào y.left y->left = root; root->parent = y; // Trả về y; return y; } struct RedBlackTree { Node* Root; bool ll = false; bool rr = false; bool lr = false; bool rl = false; RedBlackTree() { Root = NULL; } Node* insertHelp(Node* root, int key) { // f đúng khi có xung đột RED RED bool f = false; if (root == NULL) { return new Node{ key, NULL, NULL, NULL, 1 }; // RED Node } else if (key < root->data) { root->left = insertHelp(root->left, key); root->left->parent = root; // root->left = Node X // root = X->parent if (Root != root) { if (root->color == root->left->color == 1) f = true; } } else { root->right = insertHelp(root->right, key); root->right->parent = root; // root->right = Node X // root = X->parent if (Root != root) { if (root->color == root->right->color == 1) f = true; } } // Xử lý 4 TH lệch // *** Khi này (ll, lr, rr, rl = false) nên chưa xử lí liền // *** Sau khi thoát 1 vòng đệ quy thì: root = X->parent->parent // *** Tức là Node ông, lúc này ta quay Node ông // Case 1 : Left left - Trái trái if (ll) { root = rotateRight(root); root->color = 0; root->right->color = 1; ll = false; } // Case 2 : Right right - Phải phải else if (rr) { root = rotateLeft(root); root->color = 0; root->left->color = 1; rr = false; } // Case 3 : Left right - Phải trái else if (lr) { root->left = rotateLeft(root->left); root->left->parent = root; root = rotateRight(root); root->color = 0; root->right->color = 1; lr = false; } // Case 4 : Right left - Phải trái else if (rl) { root->right = rotateRight(root->right); root->right->parent = root; root = rotateLeft(root); root->color = 0; root->left->color = 1; rl = false; } // Xử lí xung đột đỏ - RED RED if (f) { if (root->parent->right == root) { if (root->parent->left == NULL || root->parent->left->color == 0) { // Cha đỏ - chú đen (rr or rl) if (root->left != NULL && root->left->color == 1) rl = true; if (root->right != NULL && root->right->color == 1) rr = true; } else { // Cha đỏ - chú đỏ root->color = root->parent->left->color = 0; if (root != Root) root->parent->color = 1; } } else { if (root->parent->right == NULL || root->parent->right->color == 0) { // Cha đỏ - chú đen (ll or lr) if (root->left != NULL && root->left->color == 1) ll = true; if (root->right != NULL && root->right->color == 1) lr = true; } else { // Cha đỏ - chú đỏ root->color = root->parent->right->color = 0; if (root != Root) root->parent->color = 1; } } f = false; } return root; } void Insert(int key) { if (Root == NULL) { Root = new Node{ key, NULL, NULL, NULL, 0 }; } else { Root = insertHelp(Root, key); if (Root->color == 1) Root->color = 0; } } }; string getColor(Node* root) { if (root->color == 1) return "RED"; return "BLACK"; } // In - Print 2D ra console void print2DUtil(Node* root, int space) { if (root == NULL) return; space += COUNT; print2DUtil(root->right, space); cout << endl; for (int i = COUNT; i < space; i++) cout << " "; cout << root->data << " (" << getColor(root) << ") " << "\n"; print2DUtil(root->left, space); } void print2D(Node* root) { print2DUtil(root, 0); } int main() { RedBlackTree RBTree; RBTree.Insert(1); RBTree.Insert(4); RBTree.Insert(6); RBTree.Insert(3); RBTree.Insert(5); RBTree.Insert(7); RBTree.Insert(8); RBTree.Insert(2); RBTree.Insert(9); print2D(RBTree.Root); return 0; } |
Kết quả:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
9 (RED) 8 (BLACK) 7 (RED) 6 (RED) 5 (BLACK) 4 (BLACK) 3 (RED) 2 (BLACK) 1 (RED) |
Cảm ơn các bạn đã đọc bài viết của mình. Nếu thấy hay thì hãy chia sẽ nó cho mọi người cùng đọc nhé! Ngoài ra, bạn nào muốn tham khảo code các ngôn ngữ khác thì hãy truy cập vào Geeks for geeks – Red Black Tree – Set 2 | Insert.
Nguồn tham khảo: Geeks for Geeks
Bài tiếp theo, cũng là bài cuối của cây đỏ đen: Cây Đỏ Đen – Phần 3 (Delete)
