Please enable JavaScript.
Coggle requires JavaScript to display documents.
Ý TƯỞNG:đảm bảo rằng chiều cao của cây con trái và cây con phải của mỗi…
Ý TƯỞNG:đảm bảo rằng chiều cao của cây con trái và cây con phải của mỗi nút không chênh lệch quá 1. Khi chèn hoặc xóa một phần tử, cây tự động điều chỉnh để đảm bảo cân bằng bằng cách thực hiện các phép xoay.
Độ phức tạp
Tốt nhất : O(log2 n)
Trung bình:O(log n)
Xấu nhất: O(n)
Đặt vấn đề
Giả sử chta có một dãy số 6, 3, 9, 2, 5, 8, 10, 1. Ta sẽ chèn các số này vào một cây AVL để tạo ra một cây cân bằng. Bắt đầu với cây rỗng, thao tác chèn từng số vào cây và thực hiện các phép xoay khi cần thiết để duy trì cân bằng chúng.
Ví dụ
Kỹ thuật quay phải – áp dụng khi cây bị lệch trái
Giải quyết vấn đề
-Bắt đầu từ gốc của cây, so sánh giá trị của nút mới với giá trị của nút hiện tại.
-Nếu giá trị của nút mới nhỏ hơn giá trị của nút hiện tại, ta di chuyển sang nút con trái và tiếp tục so sánh.
-Nếu giá trị của nút mới lớn hơn giá trị của nút hiện tại, ta di chuyển sang nút con phải và tiếp tục so sánh.
-Lặp lại quá trình này cho tới khi ta đến một vị trí trống trong cây, tức là không có nút con trái hoặc nút con phải.
Thuật toán
Thuật toán cân bằng cây sau khi thực hiện thao tác chèn một nút mới. Khi chèn một nút mới vào cây AVL, cây bị lệch về bên phải, và thuật toán cân bằng sau sẽ kiểm tra và điều chỉnh lại cây để đảm bảo rằng nó vẫn duy trì tính chất cân bằng.
.
Node
rightRotate(Node
y) {
Node* x = y->left;
Node* T2 = x->right;
// Thực hiện quay phải
x->right = y;
y->left = T2;
// Cập nhật chiều cao
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
return x;
void inOrder(Node* node) {
if (node != nullptr) {
inOrder(node->left);
cout << node->key << " ";
}
// Hàm quay phải
}
// Hàm in-order traversal để in ra cây AVL
