Trong phần trước, chúng ta đã tìm hiểu về cách "Thêm Node - Insertion" trong cây AVL. Trên thực tế, quá trình xóa Node trong cây AVL cũng tương tự như trong cây BST (Binary Search Tree). Tuy nhiên, để duy trì tính cân bằng của cây AVL, chúng ta cần thực hiện các bước cập nhật chiều cao và xử lý các trường hợp cây bị lệch.
1. Kiến thức cần nắm
Cây AVL là một cây tìm kiếm nhị phân (BST) được cân bằng. Nếu bạn muốn xóa một Node trong cây AVL, bạn cần nắm rõ kiến thức sau đây:
- Cách xóa một Node trong cây BST (Cây tìm kiếm nhị phân).
- Các trường hợp cây bị lệch và cách xử lý (phần thêm Node - Insertion).
2. Chuyện gì xảy ra nếu xóa một Node?
Khi xóa một Node trong cây AVL, chúng ta sẽ gặp ba trường hợp chính sau:
- Node không có con (Node lá): Chỉ cần giải phóng bộ nhớ của Node đó.
- Node chỉ có một con: Giải phóng Node đó và thay bằng Node con.
- Node có hai con: Tìm Node con nhỏ nhất bên phải hoặc lớn nhất bên trái (gọi là "temp"), gán giá trị của Node này cho Node cần xóa, sau đó xóa temp. Vì temp chỉ có một hoặc không có con, ta có thể xóa nó như hai trường hợp trên.
Sau khi xóa một Node trong cây AVL, chúng ta cần thực hiện hai việc sau:
- Cập nhật lại chiều cao của các Node.
- Xử lý các trường hợp cây bị lệch.
3. Cập nhật chiều cao
Để xóa một Node trong cây AVL, chúng ta sử dụng phương pháp đệ quy để duyệt cây và tìm Node cần xóa. Sau khi xóa, chúng ta chỉ cần cập nhật chiều cao một lần.
4. Xử lý các trường hợp cây bị lệch
Ở phần trước, chúng ta đã biết rằng cây AVL có bốn trường hợp bị lệch: Trái trái, Trái phải, Phải phải và Phải trái. Để xác định trường hợp cụ thể, chúng ta cần tính toán "giá trị cân bằng" (value balance).
4.1. Trường hợp Trái trái (Left left)
Trường hợp Trái trái xảy ra khi valueBalance(root) > 1 và valueBalance(x) >= 0. Chúng ta chỉ cần thực hiện phép quay phải (rightRotate) trên Node gốc (root) để cân bằng cây.
4.2. Trường hợp Trái phải (Left right)
Trường hợp Trái phải xảy ra khi valueBalance(root) > 1 và valueBalance(x) < 0. Đầu tiên, chúng ta thực hiện phép quay trái (leftRotate) trên Node con (x), sau đó thực hiện phép quay phải (rightRotate) trên Node gốc (root) để cân bằng cây.
4.3. Trường hợp Phải phải (Right right)
Trường hợp Phải phải xảy ra khi valueBalance(root) < -1 và valueBalance(y) <= 0. Chúng ta chỉ cần thực hiện phép quay trái (leftRotate) trên Node gốc (root) để cân bằng cây.
4.4. Trường hợp Phải trái (Right left)
Trường hợp Phải trái xảy ra khi valueBalance(root) < -1 và valueBalance(y) > 0. Đầu tiên, chúng ta thực hiện phép quay phải (rightRotate) trên Node con (y), sau đó thực hiện phép quay trái (leftRotate) trên Node gốc (root) để cân bằng cây.
5. Cập nhật code - Insert + Delete
Dưới đây là đoạn code c+ + cho việc chèn và xóa Node trong cây AVL:
#include #include using namespace std; struct Node { int data; Node* left; Node* right; int height; }; int getHeight(Node* root) { if (root == NULL) return 0; return root->height; } Node* rightRotate(Node* root) { Node* x = root->left; root->left = x->right; x->right = root; root->height = 1 + max(getHeight(root->left), getHeight(root->right)); x->height = 1 + max(getHeight(x->left), getHeight(x->right)); return x; } Node* leftRotate(Node* root) { Node* y = root->right; root->right = y->left; y->left = root; root->height = 1 + max(getHeight(root->left), getHeight(root->right)); y->height = 1 + max(getHeight(y->left), getHeight(y->right)); return y; } Node* Insert(Node* root, int value) { if (root == NULL) return new Node{ value, NULL, NULL, 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; root->height = 1 + max(getHeight(root->left), getHeight(root->right)); int valBalance = getHeight(root->left) - getHeight(root->right); if (valBalance > 1 && value < root->left->data) return rightRotate(root); if (valBalance < -1 && value > root->right->data) return leftRotate(root); if (valBalance > 1 && value > root->left->data) { root->left = leftRotate(root->left); return rightRotate(root); } if (valBalance < -1 && value < root->right->data) { root->right = rightRotate(root->right); return leftRotate(root); } return root; } Node* minValueNode(Node* root) { Node* current = root; while (current->left != NULL) current = current->left; return current; } Node* deleteNode(Node* root, int key) { if (root == NULL) return root; if (key > root->data) root->right = deleteNode(root->right, key); else if (key < root->data) root->left = deleteNode(root->left, key); else { if (root->left == NULL || root->right == NULL) { Node* temp = root->left ? root->left : root->right; if (temp == NULL) { temp = root; root = NULL; delete temp; } else { *root = *temp; delete temp; } } else { Node* temp = minValueNode(root->right); root->data = temp->data; root->right = deleteNode(root->right, temp->data); } } if (root == NULL) return root; root->height = 1 + max(getHeight(root->left), getHeight(root->right)); int valBalance = getHeight(root->left) - getHeight(root->right); if (valBalance > 1 && valueBalance(root->left) >= 0) return rightRotate(root); if (valBalance < -1 && valueBalance(root->right) <= 0) return leftRotate(root); if (valBalance > 1 && valueBalance(root->left) < 0) { root->left = leftRotate(root->left); return rightRotate(root); } if (valBalance < -1 && valueBalance(root->right) > 0) { root->right = rightRotate(root->right); return leftRotate(root); } return root; } 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 << " (" << root->height << ") " << endl; print2DUtil(root->left, space); } void print2D(Node* root) { print2DUtil(root, 0); } int main() { Node* tree = NULL; tree = Insert(tree, 10); tree = Insert(tree, 5); tree = Insert(tree, 15); tree = Insert(tree, 3); tree = Insert(tree, 12); tree = Insert(tree, 17); tree = Insert(tree, 11); print2D(tree); cout << " - Xóa Node có giá trị 3 - " << endl; tree = deleteNode(tree, 3); print2D(tree); return 0; } Kết quả in ra màn hình:
17 (1) 15 (2) 12 (3) 11 (1) 10 (2) 5 (1) - Xóa Node có giá trị 3 - 17 (1) 15 (2) 12 (3) 11 (1) 10 (2) 5 (1) Cảm ơn bạn đã theo dõi. Đây là phần kết thúc của series về cây AVL. Nếu bạn cảm thấy bài viết hữu ích, hãy chia sẻ nó để mọi người cùng đọc. Nếu bạn muốn tham khảo mã nguồn trong các ngôn ngữ khác, hãy truy cập Geeks for Geeks - AVL Tree - Set 2.
Thân mến.
