Xóa Node khỏi cây đỏ đen - Cấu trúc cây
Trong hướng dẫn này mình sẽ giới thiệu các bạn cách xóa một Node khỏi cây đỏ đen. Đây là một thao tác thường gặp khi làm việc với các cấu trúc dữ liệu nói chung và cấu trúc cây đỏ đen nói riêng. Chúng ta sẽ cùng nhau tìm hiểu về cách xóa một Node khỏi cây đỏ đen và khắc phục các trường hợp vi ...
Trong hướng dẫn này mình sẽ giới thiệu các bạn cách xóa một Node khỏi cây đỏ đen. Đây là một thao tác thường gặp khi làm việc với các cấu trúc dữ liệu nói chung và cấu trúc cây đỏ đen nói riêng.
Chúng ta sẽ cùng nhau tìm hiểu về cách xóa một Node khỏi cây đỏ đen và khắc phục các trường hợp vi phạm quy tắc cây đỏ đen khi xóa Node.
1. Xóa Node khỏi cây đỏ đen
Trong thao tác chèn chúng ta dựa vào màu sắc của Node chú U để quyết định trường hợp phù hợp. Trong thao tác xóa, chúng ta dựa vào màu sắc của anh chị em Node N để thực quyết định trường hợp thích hợp.
Khi thực hiện thêm một Node mới vào ta sẽ vi phạm quy tắc số 4 đó là xảy ra xung đột đỏ - đỏ. Còn khi thực hiện thao tác xóa Node khỏi danh sách ta sẽ vi phạm quy tắc số 5 đó là sẽ làm thay đổi số Node đen tính từ Node gốc đến Node ngoài.
Việc xóa là một quá trình khá phức tạp. Khi một Node đen bị xóa, ta cần phải thay thế vào đó một Node đen khác để đảm bảo rằng chiều cao từ Node gốc đến Node ngoài không bị thay đổi.
Chúng ta sẽ thực hiện lần lược các bước sau để xóa Node khỏi cây đỏ đen: v là Node bị xóa và u là Node thay thế v
Bước 1
Ta sẽ thực hiện viết một hàm xóa một Node tương tự như xóa nốt ở cây nhị phân tìm kiếm, sẽ có 3 trường hợp đó chính là Node lá, Node có một con và Node có hai con. ta sẽ xét từng trường hợp và xóa nó. Và lưu ý rằng Node lá sẽ có hai Node ngoài là Node đen.
Bước 2
Ta xét trường hợp nếu u hoặc v là màu đỏ ta thực hiện thay thế Node con là màu đen (không thay đổi chiều cao của đen của cây). Lưu ý rằng cả u và v không thể có màu đỏ vì v là cha của u và hai màu đỏ liên tiếp không được phép trong cây đỏ đen.
Bước 3
Trong trường hợp u va v đều là Node đen, ta sẽ xét tiếp các trường hợp sau:
Trường hợp 1:
Có hai Node u là màu đen, nhiệm vụ của ta bây giờ là giảm bớt một Node đen u đi để thay thế vào Node v cần xóa ở trên nó. Nếu v là Node lá thì hai Node u cũng là Node đen và có giá trị NULL.
Trường hợp 2:
Nếu Node cần xóa có Node u là Node đen kép và nó không phải là Node gốc. khi này ta sẽ gọi s là Node anh chị em của v. Ta sẽ có 2 trường hợp con khác:
Thứ nhất: Nếu s là màu đen và một trong số con của s có màu đỏ ta sẽ thực hiện các phép quay. Ta gọi con màu đỏ của s đó là r thì việc thực hiện phép quay tùy thuộc vào vị trí của s và r.
- Trường hợp Left Left : s là con trái của cha và r là con trái của s.
- Trường hợp Left Right: s là con trái của cha và r là con phải.
- Trường hợp Right Right: s là con bên phải của cha và r là con bên phải của s.
- Trường hợp Right Left: s là con bên phải của cha và r là con bên trái của s.
Thú hai: Nếu s là màu đen và cả hai con của nó đều màu đen, ta thực hiện đổi màu và lặp lại cho cha của nó nếu cha của nó cũng màu đen. Trong trường hợp cha của nó màu đỏ thì ta không cần lặp lại, ta chỉ cần đặt lại cho nó màu đen.
Trường hợp 3:
Nếu Node cần xóa v là Node gốc, ta thực hiện đổi màu cho u thành đen và khi đó độ dài đen của cây chỉ giảm đi một.
2. Ví dụ xóa Node khỏi cây đỏ đen
Trong ví dụ này mình sẽ thực hiện thêm vào một số Node là số nguyên, sau đó xóa một vài số và hiển thị kết quả ra màn hình. Trong code mình đã có chú thích các bạn chú ý theo dõi nhé.
Full code:
#include <iostream>
#include<queue>
using namespace std;
//khai báo thuộc tính color
enum COLOR { RED, BLACK };
//tạo cấy trúc node
class Node {
public:
int val;
COLOR color;
Node *left, *right, *parent;
Node(int val) : val(val) {
parent = left = right = NULL;
// Nút được tạo trong quá trình chèn
// Nút có màu đỏ khi chèn
color = RED;
}
// trả về con trỏ tới node chú
Node *uncle() {
// Nếu không có node cha hoặc node ông, thì không có node chú
if (parent == NULL or parent->parent == NULL)
return NULL;
if (parent->isOnLeft())
// node chú bên phải
return parent->parent->right;
else
//node chú bên trái
return parent->parent->left;
}
// kiểm tra xem node có phải là node con của cha không
bool isOnLeft() { return this == parent->left; }
// trả về con trỏ cho node anh chị em
Node *sibling() {
// Node anh rỗng nếu không tồn tại node cha
if (parent == NULL)
return NULL;
if (isOnLeft())
return parent->right;
return parent->left;
}
// di chuyển nút xuống và di chuyển nút đã cho vào vị trí của nó
void moveDown(Node *nParent) {
if (parent != NULL) {
if (isOnLeft()) {
parent->left = nParent;
} else {
parent->right = nParent;
}
}
nParent->parent = parent;
parent = nParent;
}
bool hasRedChild() {
return (left != NULL and left->color == RED) or
(right != NULL and right->color == RED);
}
};
class RBTree {
Node *root;
// xoay trái node đã cho
void leftRotate(Node *x) {
// node cha mới sẽ là con bên phải của nút
Node *nParent = x->right;
// cập nhật gốc nếu nút hiện tại là gốc
if (x == root)
root = nParent;
x->moveDown(nParent);
// kết nối x với phần tử bên trái của cha mẹ mới
x->right = nParent->left;
// kết nối phần tử bên trái của cha mẹ mới với nút
// nếu nó không phải là null
if (nParent->left != NULL)
nParent->left->parent = x;
// kết nối cha mẹ mới với x
nParent->left = x;
}
void rightRotate(Node *x) {
// cha mẹ mới sẽ là con bên trái của nút
Node *nParent = x->left;
// cập nhật gốc nếu nút hiện tại là gốc
if (x == root)
root = nParent;
x->moveDown(nParent);
// kết nối x với phần tử bên phải của cha mẹ mới
x->left = nParent->right;
//kết nối phần tử bên phải của cha mẹ mới với nút
// nếu nó không phải là null
if (nParent->right != NULL)
nParent->right->parent = x;
// kết nối cha mẹ mới với x
nParent->right = x;
}
void swapColors(Node *x1, Node *x2) {
COLOR temp;
temp = x1->color;
x1->color = x2->color;
x2->color = temp;
}
void swapValues(Node *u, Node *v) {
int temp;
temp = u->val;
u->val = v->val;
v->val = temp;
}
// sửa màu đỏ đỏ tại nút nhất định
void fixRedRed(Node *x) {
// nếu x là màu gốc, nó là màu đen và trả về
if (x == root) {
x->color = BLACK;
return;
}
// khởi tạo cha mẹ, ông bà, chú
Node *parent = x->parent, *grandparent = parent->parent,
*uncle = x->uncle();
if (parent->color != BLACK) {
if (uncle != NULL && uncle->color == RED) {
// chú màu đỏ, thực hiện tô màu và đệ quy
parent->color = BLACK;
uncle->color = BLACK;
grandparent->color = RED;
fixRedRed(grandparent);
} else {
// Các hoạt động khác LR, LL, RL, RR
if (parent->isOnLeft()) {
if (x->isOnLeft()) {
// cho left right
swapColors(parent, grandparent);
} else {
leftRotate(parent);
swapColors(x, grandparent);
}
// cho left left và left right
rightRotate(grandparent);
} else {
if (x->isOnLeft()) {
// cho right left
rightRotate(parent);
swapColors(x, grandparent);
} else {
swapColors(parent, grandparent);
}
// cho right right và right left
leftRotate(grandparent);
}
}
}
}
// tìm nút không có nút con bên trái
// trong cây con của nút đã cho
Node *successor(Node *x) {
Node *temp = x;
while (temp->left != NULL)
temp = temp->left;
return temp;
}
// tìm nút thay thế nút đã xóa trong BST
Node *BSTreplace(Node *x) {
// khi nút có 2 con
if (x->left != NULL and x->right != NULL)
return successor(x->right);
// khi node lá
if (x->left == NULL and x->right == NULL)
return NULL;
// khi node có một con
if (x->left != NULL)
return x->left;
else
return x->right;
}
// xóa nút đã cho
void deleteNode(Node *v) {
Node *u = BSTreplace(v);
// Đúng khi u và v đều đen
bool uvBlack = ((u == NULL or u->color == BLACK) and (v->color == BLACK));
Node *parent = v->parent;
if (u == NULL) {
// u là NULL do đó v là lá
if (v == root) {
// v là root, làm cho root là null
root = NULL;
} else {
if (uvBlack) {
// u và v đều đen
// v là lá, sửa màu đen kép tại v
fixDoubleBlack(v);
} else {
// u hoặc v là đỏ
if (v->sibling() != NULL)
// node anh chị em không rỗng, làm cho nó màu đỏ"
v->sibling()->color = RED;
}
// xóa v khỏi cây
if (v->isOnLeft()) {
parent->left = NULL;
} else {
parent->right = NULL;
}
}
delete v;
return;
}
if (v->left == NULL or v->right == NULL) {
// v có 1 node con
if (v == root) {
// v là gốc, gán giá trị của u cho v và xóa u
v->val = u->val;
v->left = v->right = NULL;
delete u;
} else {
// Tách v khỏi cây và di chuyển u lên
if (v->isOnLeft()) {
parent->left = u;
} else {
parent->right = u;
}
delete v;
u->parent = parent;
if (uvBlack) {
// u và v đều đen, sửa hai màu đen ở u
fixDoubleBlack(u);
} else {
// u hoặc v đỏ, màu u đen
u->color = BLACK;
}
}
return;
}
// v có 2 con, hoán đổi giá trị với kế nhiệm và đệ quy
swapValues(u, v);
deleteNode(u);
}
void fixDoubleBlack(Node *x) {
if (x == root)
// x là node gốc thì return
return;
Node *sibling = x->sibling(), *parent = x->parent;
if (sibling == NULL) {
// Không có sibiling, màu đen kép được đẩy lên
fixDoubleBlack(parent);
} else {
if (sibling->color == RED) {
// Anh chị em màu đỏ
parent->color = RED;
sibling->color = BLACK;
if (sibling->isOnLeft()) {
// trường hợp left
rightRotate(parent);
} else {
// trường hợp right
leftRotate(parent);
}
fixDoubleBlack(x);
} else {
// Anh chị em đen
if (sibling->hasRedChild()) {
// ít nhất 1 trẻ em màu đỏ
if (sibling->left != NULL and sibling->left->color == RED) {
if (sibling->isOnLeft()) {
// left left
sibling->left->color = sibling->color;
sibling->color = parent->color;
rightRotate(parent);
} else {
// right left
sibling->left->color = parent->color;
rightRotate(sibling);
leftRotate(parent);
}
} else {
if (sibling->isOnLeft()) {
// left right
sibling->right->color = parent->color;
leftRotate(sibling);
rightRotate(parent);
} else {
// right right
sibling->right->color = sibling->color;
sibling->color = parent->color;
leftRotate(parent);
}
}
parent->color = BLACK;
} else {
// hai con đen
sibling->color = RED;
if (parent->color == BLACK)
fixDoubleBlack(parent);
else
parent->color = BLACK;
}
}
}
}
// in thứ tự cho node
void levelOrder(Node *x) {
if (x == NULL)
return;
queue<Node *> q;
Node *curr;
q.push(x);
while (!q.empty()) {
curr = q.front();
q.pop();
cout << curr->val << " ";
if (curr->left != NULL)
q.push(curr->left);
if (curr->right != NULL)
q.push(curr->right);
}
}
// in đệ quy order
void inorder(Node *x) {
if (x == NULL)
return;
inorder(x->left);
cout << x->val << " ";
inorder(x->right);
}
public:
RBTree() { root = NULL; }
Node *getRoot() { return root; }
Node *search(int n) {
Node *temp = root;
while (temp != NULL) {
if (n < temp->val) {
if (temp->left == NULL)
break;
else
temp = temp->left;
} else if (n == temp->val) {
break;
} else {
if (temp->right == NULL)
break;
else
temp = temp->right;
}
}
return temp;
}
// chen giá trị đã cho vào cây
void insert(int n) {
Node *newNode = new Node(n);
if (root == NULL) {
newNode->color = BLACK;
root = newNode;
} else {
Node *temp = search(n);
if (temp->val == n) {
return;
}
newNode->parent = temp;
if (n < temp->val)
temp->left = newNode;
else
temp->right = newNode;
fixRedRed(newNode);
}
}
// chức năng tiện ích xóa nút có giá trị nhất định
void deleteByVal(int n) {
if (root == NULL)
// Tree is empty
return;
Node *v = search(n), *u;
if (v->val != n) {
cout << "Không tìm thấy nút nào để xóa với giá trị:" << n << endl;
return;
}
deleteNode(v);
}
// in theo thứ tự
void printInOrder() {
cout << "In theo thứ tự: " << endl;
if (root == NULL)
cout << "cây rỗng" << endl;
else
inorder(root);
cout << endl;
}
// in theo thứ tự cấp
void printLevelOrder() {
cout << "In theo thứ tự cấp: " << endl;
if (root == NULL)
cout << "cây rỗng" << endl;
else
levelOrder(root);
cout << endl;
}
};
int main() {
RBTree tree;
//insert dữ liệu
tree.insert(7);
tree.insert(3);
tree.insert(18);
tree.insert(10);
tree.insert(22);
tree.insert(8);
tree.insert(11);
tree.insert(26);
tree.insert(2);
tree.insert(6);
tree.insert(13);
//gọi hàm in
tree.printInOrder();
tree.printLevelOrder();
cout<<endl<<"xóa các số: 18, 11, 3, 10, 22"<<endl;
//thực hiện xóa node
tree.deleteByVal(18);
tree.deleteByVal(11);
tree.deleteByVal(3);
tree.deleteByVal(10);
tree.deleteByVal(22);
//gọi hàm in
tree.printInOrder();
tree.printLevelOrder();
cout<<"
-----------------------------
";
cout<<"Chương trình này được đăng tại Zaidap.com.net";
} Kết quả:
3. Kết luận
Như vậy là chúng ta đã tìm hiểu xong cách xóa một Node khỏi cây đỏ đen, cũng như tìm hiểu cách khắc phục các trường hợp vi phạm quy tắc cây đỏ đen. Cũng như thực hiện một ví dụ xóa các số nguyên trong cây đỏ đen số nguyên. Chúc các bạn thực hiện thành công !!!
