Cây AVL
Cập nhật lần cuối
Cây AVL (AVL tree) là một cây tìm kiếm nhị phân tự cân bằng. Nó hoạt động như một BST thông thường, nhưng sau mỗi lần chèn, cây kiểm tra hệ số cân bằng (balance factor) của từng nút tổ tiên, tức là chênh lệch chiều cao giữa cây con trái và cây con phải. Nếu có nút nào mất cân bằng (chênh lệch lớn hơn 1), cây thực hiện các phép xoay để khôi phục cân bằng. Nhấn Phát ở trên để xem từng giá trị được chèn vào và cây tự xoay về đúng hình dạng.
Vì không bao giờ để cây lệch quá một chút, cây AVL bảo đảm chiều cao O(log n), nên tìm kiếm, chèn và xóa luôn là O(log n), kể cả với dữ liệu đã sắp xếp vốn sẽ làm hỏng một BST thông thường. Cái giá phải trả là các phép xoay bổ sung và việc cập nhật chiều cao sau mỗi lần chèn.
Độ phức tạp thời gian và không gian
| Thao tác | Độ phức tạp | Ghi chú |
|---|---|---|
| Tìm kiếm | O(log n) | Chiều cao luôn khoảng ~1,44 log n |
| Chèn | O(log n) | Cộng thêm O(1) phép xoay |
| Xóa | O(log n) | Cộng thêm O(log n) phép xoay |
| Không gian | O(n) | Mỗi nút lưu thêm một trường chiều cao |
Bốn trường hợp xoay
| Trường hợp | Mất cân bằng | Cách sửa |
|---|---|---|
| Left-Left | Lệch về bên trái của con trái | Một phép xoay phải |
| Right-Right | Lệch về bên phải của con phải | Một phép xoay trái |
| Left-Right | Lệch về bên phải của con trái | Xoay trái, rồi xoay phải |
| Right-Left | Lệch về bên trái của con phải | Xoay phải, rồi xoay trái |
Ví dụ minh họa
Chèn lần lượt từng giá trị của [10, 20, 30, 40, 50, 25]:
| Bước | Cấu trúc | Thao tác |
|---|---|---|
Chèn 10 | 10 | Nút đầu tiên trở thành gốc; cây cân bằng |
Chèn 20 | 10(_, 20) | Đi sang phải 10; vẫn cân bằng |
Chèn 30 | 20(10, 30) | Right-Right tại 10, nên một phép xoay trái đưa 20 lên làm gốc |
Chèn 40 | 20(10, 30(_, 40)) | Đi sang phải 30; mọi hệ số cân bằng vẫn nằm trong ±1 |
Chèn 50 | 20(10, 40(30, 50)) | Right-Right tại 30, nên phép xoay trái tại 30 đưa 40 lên |
Chèn 25 | 30(20(10, 25), 40(_, 50)) | Right-Left tại 20: xoay phải cây con của 40, rồi xoay trái 20 |
Khi nào nên dùng cây AVL
| Nên dùng khi | Tránh dùng khi |
|---|---|
| Số lần tra cứu nhiều hơn hẳn số lần chèn và bạn muốn chiều cao cây thấp nhất có thể | Chèn và xóa chiếm phần lớn: các phép xoay và cân bằng lại tốn kém hơn so với cây đỏ đen |
Bạn cần bảo đảm trường hợp xấu nhất O(log n), kể cả với dữ liệu cố tình gây bất lợi hoặc đã sắp xếp | Một bảng băm thông thường là đủ: bạn không cần duyệt theo thứ tự hay truy vấn theo khoảng |
| Bạn cần các thao tác có thứ tự: duyệt trung thứ tự, tìm phần tử liền trước/liền sau, truy vấn theo khoảng | Tập dữ liệu rất nhỏ: một BST thông thường hoặc mảng đã sắp xếp đơn giản hơn và đủ nhanh |
| Dữ liệu có thể đến theo thứ tự đã sắp xếp, điều sẽ biến một BST không cân bằng thành danh sách liên kết | Bộ nhớ quá eo hẹp đến mức không thể chịu thêm trường chiều cao cho mỗi nút |
Code AVL Tree
Một cách cài đặt AVL Tree gọn gàng, chạy được ngay bằng Python, JavaScript, Java, C++, C. Chọn một ngôn ngữ, sao chép code hoặc mở sẵn trong Coddy Playground.
Code AVL Tree bằng Python
Python
1class Node:2 def __init__(self, key):3 self.key = key4 self.left = None5 self.right = None6 self.height = 17
8
9def height(node):10 return node.height if node else 011
12
13def update(node):14 node.height = 1 + max(height(node.left), height(node.right))15
16
17def rotate_right(y):18 x = y.left19 y.left = x.right20 x.right = y21 update(y)22 update(x)23 return x24
25
26def rotate_left(x):27 y = x.right28 x.right = y.left29 y.left = x30 update(x)31 update(y)32 return y33
34
35def insert(node, key):36 if node is None:37 return Node(key)38 if key < node.key:39 node.left = insert(node.left, key)40 else:41 node.right = insert(node.right, key)42 update(node)43 balance = height(node.left) - height(node.right)44 # Four imbalance cases: LL, RR, LR, RL45 if balance > 1 and key < node.left.key:46 return rotate_right(node)47 if balance < -1 and key > node.right.key:48 return rotate_left(node)49 if balance > 1:50 node.left = rotate_left(node.left)51 return rotate_right(node)52 if balance < -1:53 node.right = rotate_right(node.right)54 return rotate_left(node)55 return node56
57
58def inorder(node):59 if node is None:60 return []61 return inorder(node.left) + [node.key] + inorder(node.right)62
63
64root = None65for key in [10, 20, 30, 40, 50, 25]:66 root = insert(root, key)67
68print("Inorder:", inorder(root))69print("Root:", root.key, "| tree height:", root.height)Code AVL Tree bằng JavaScript
JavaScript
1class Node {2 constructor(key) {3 this.key = key;4 this.left = null;5 this.right = null;6 this.height = 1;7 }8}9
10const height = (n) => (n ? n.height : 0);11const update = (n) => {12 n.height = 1 + Math.max(height(n.left), height(n.right));13};14const balance = (n) => height(n.left) - height(n.right);15
16function rotateRight(y) {17 const x = y.left;18 y.left = x.right;19 x.right = y;20 update(y);21 update(x);22 return x;23}24
25function rotateLeft(x) {26 const y = x.right;27 x.right = y.left;28 y.left = x;29 update(x);30 update(y);31 return y;32}33
34function insert(node, key) {35 if (!node) return new Node(key);36 if (key < node.key) node.left = insert(node.left, key);37 else node.right = insert(node.right, key);38 update(node);39 const b = balance(node);40 // Four rebalancing cases: LL, RR, LR, RL41 if (b > 1 && key < node.left.key) return rotateRight(node);42 if (b < -1 && key > node.right.key) return rotateLeft(node);43 if (b > 1) {44 node.left = rotateLeft(node.left);45 return rotateRight(node);46 }47 if (b < -1) {48 node.right = rotateRight(node.right);49 return rotateLeft(node);50 }51 return node;52}53
54function inorder(node, out = []) {55 if (!node) return out;56 inorder(node.left, out);57 out.push(node.key);58 inorder(node.right, out);59 return out;60}61
62let root = null;63for (const key of [10, 20, 30, 40, 50, 25]) root = insert(root, key);64console.log("Root after rebalancing:", root.key);65console.log("Inorder:", inorder(root).join(" "));Code AVL Tree bằng Java
Java
1public class Main {2 static class Node {3 int key, height = 1;4 Node left, right;5 Node(int key) { this.key = key; }6 }7
8 static int height(Node n) { return n == null ? 0 : n.height; }9 static int balance(Node n) { return n == null ? 0 : height(n.left) - height(n.right); }10 static void update(Node n) { n.height = 1 + Math.max(height(n.left), height(n.right)); }11
12 static Node rotateRight(Node y) {13 Node x = y.left;14 y.left = x.right;15 x.right = y;16 update(y); update(x);17 return x;18 }19
20 static Node rotateLeft(Node x) {21 Node y = x.right;22 x.right = y.left;23 y.left = x;24 update(x); update(y);25 return y;26 }27
28 static Node insert(Node node, int key) {29 if (node == null) return new Node(key);30 if (key < node.key) node.left = insert(node.left, key);31 else node.right = insert(node.right, key);32 update(node);33 int b = balance(node);34 // Four imbalance cases: LL, RR, LR, RL35 if (b > 1 && key < node.left.key) return rotateRight(node);36 if (b < -1 && key > node.right.key) return rotateLeft(node);37 if (b > 1) { node.left = rotateLeft(node.left); return rotateRight(node); }38 if (b < -1) { node.right = rotateRight(node.right); return rotateLeft(node); }39 return node;40 }41
42 static void inorder(Node n, StringBuilder sb) {43 if (n == null) return;44 inorder(n.left, sb);45 sb.append(n.key).append(" ");46 inorder(n.right, sb);47 }48
49 public static void main(String[] args) {50 Node root = null;51 int[] keys = {10, 20, 30, 40, 50, 25};52 for (int k : keys) root = insert(root, k);53 StringBuilder sb = new StringBuilder();54 inorder(root, sb);55 System.out.println("Inorder: " + sb.toString().trim());56 System.out.println("Root after rebalancing: " + root.key + " (height " + root.height + ")");57 }58}Code AVL Tree bằng C++
C++
1#include <algorithm>2#include <iostream>3
4struct Node {5 int value;6 int height = 1;7 Node* left = nullptr;8 Node* right = nullptr;9 explicit Node(int v) : value(v) {}10};11
12int height(const Node* n) { return n ? n->height : 0; }13int balanceFactor(const Node* n) { return height(n->left) - height(n->right); }14void updateHeight(Node* n) {15 n->height = 1 + std::max(height(n->left), height(n->right));16}17
18Node* rotateRight(Node* y) {19 Node* x = y->left;20 y->left = x->right;21 x->right = y;22 updateHeight(y);23 updateHeight(x);24 return x;25}26
27Node* rotateLeft(Node* x) {28 Node* y = x->right;29 x->right = y->left;30 y->left = x;31 updateHeight(x);32 updateHeight(y);33 return y;34}35
36Node* insert(Node* node, int value) {37 if (node == nullptr) return new Node(value);38 if (value < node->value) node->left = insert(node->left, value);39 else node->right = insert(node->right, value);40 updateHeight(node);41 int balance = balanceFactor(node);42 // Four rebalancing cases: LL, RR, LR, RL43 if (balance > 1 && value < node->left->value) return rotateRight(node);44 if (balance < -1 && value > node->right->value) return rotateLeft(node);45 if (balance > 1) {46 node->left = rotateLeft(node->left);47 return rotateRight(node);48 }49 if (balance < -1) {50 node->right = rotateRight(node->right);51 return rotateLeft(node);52 }53 return node;54}55
56void inorder(const Node* n) {57 if (n == nullptr) return;58 inorder(n->left);59 std::cout << n->value << "(h" << n->height << ") ";60 inorder(n->right);61}62
63int main() {64 Node* root = nullptr;65 for (int value : {10, 20, 30, 40, 50, 25}) root = insert(root, value);66 std::cout << "Root after rebalancing: " << root->value << "\n";67 std::cout << "In-order: ";68 inorder(root);69 std::cout << "\n";70 return 0;71}Code AVL Tree bằng C
C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5 int value, height;6 struct Node* left;7 struct Node* right;8} Node;9
10int height(const Node* n) { return n ? n->height : 0; }11int balanceFactor(const Node* n) { return height(n->left) - height(n->right); }12int maxInt(int a, int b) { return a > b ? a : b; }13
14Node* newNode(int value) {15 Node* n = calloc(1, sizeof(Node));16 n->value = value;17 n->height = 1;18 return n;19}20
21void updateHeight(Node* n) {22 n->height = 1 + maxInt(height(n->left), height(n->right));23}24
25Node* rotateRight(Node* y) {26 Node* x = y->left;27 y->left = x->right;28 x->right = y;29 updateHeight(y);30 updateHeight(x);31 return x;32}33
34Node* rotateLeft(Node* x) {35 Node* y = x->right;36 x->right = y->left;37 y->left = x;38 updateHeight(x);39 updateHeight(y);40 return y;41}42
43Node* insert(Node* node, int value) {44 if (node == NULL) return newNode(value);45 if (value < node->value) node->left = insert(node->left, value);46 else node->right = insert(node->right, value);47 updateHeight(node);48 int balance = balanceFactor(node);49 // Four rebalancing cases: LL, RR, LR, RL50 if (balance > 1 && value < node->left->value) return rotateRight(node);51 if (balance < -1 && value > node->right->value) return rotateLeft(node);52 if (balance > 1) {53 node->left = rotateLeft(node->left);54 return rotateRight(node);55 }56 if (balance < -1) {57 node->right = rotateRight(node->right);58 return rotateLeft(node);59 }60 return node;61}62
63void inorder(const Node* n) {64 if (n == NULL) return;65 inorder(n->left);66 printf("%d(h%d) ", n->value, n->height);67 inorder(n->right);68}69
70int main(void) {71 int values[] = {10, 20, 30, 40, 50, 25};72 Node* root = NULL;73 for (int i = 0; i < 6; i++) root = insert(root, values[i]);74 printf("Root after rebalancing: %d\n", root->value);75 printf("In-order: ");76 inorder(root);77 printf("\n");78 return 0;79}Câu hỏi thường gặp về cây AVL
Hệ số cân bằng trong cây AVL là gì?
Hệ số cân bằng của một nút là chiều cao cây con trái trừ đi chiều cao cây con phải. Cây AVL giữ hệ số cân bằng của mọi nút ở mức -1, 0 hoặc +1; nếu một lần chèn đẩy giá trị này ra ngoài khoảng đó, một phép xoay sẽ khôi phục cân bằng.
Cây AVL và cây đỏ đen khác nhau như thế nào?
Cả hai đều là BST tự cân bằng với các thao tác
O(log n). Cây AVL được cân bằng chặt chẽ hơn nên tra cứu nhanh hơn một chút, nhưng có thể phải xoay nhiều hơn khi chèn/xóa. Cây đỏ đen cân bằng lỏng hơn và ưu tiên ít phép xoay hơn, vì vậy nhiều thư viện chuẩn dùng nó cho map và set.Vì sao nên dùng cây AVL thay cho cây tìm kiếm nhị phân thông thường?
Một BST thông thường có thể suy biến thành các thao tác
O(n) nếu giá trị được chèn theo thứ tự đã sắp xếp, tạo thành một chuỗi lệch hẳn về một bên. Cây AVL tự xoay để giữ cân bằng, bảo đảm chiều cao và các thao tác luôn là O(log n) bất kể thứ tự chèn.Cây AVL có tốt hơn cây đỏ đen cho chỉ mục cơ sở dữ liệu không?
Còn tùy vào khối lượng công việc. Cây AVL cân bằng cứng nhắc hơn, nên có lợi thế khi thao tác đọc chiếm phần lớn và bạn muốn đường tìm kiếm ngắn nhất có thể. Tuy nhiên, phần lớn cơ sở dữ liệu và thư viện của các ngôn ngữ chọn cây đỏ đen (hoặc B-tree) vì chúng cân bằng lại với ít phép xoay hơn khi ghi nhiều, điều quan trọng hơn khi chèn và xóa diễn ra thường xuyên.
Một lần chèn vào cây AVL cần bao nhiêu phép xoay?
Nhiều nhất là một lần xoay, có thể là xoay đơn hoặc xoay kép (hai bước), để cân bằng lại cây sau khi chèn một giá trị. Lý do là một lần chèn chỉ tăng chiều cao của một cây con thêm tối đa 1, nên chỉ cần sửa một lần tại nút tổ tiên mất cân bằng thấp nhất. Xóa thì khác: có thể cần tới
O(log n) phép xoay vì việc cân bằng lại lan dần lên phía gốc.Có cần cập nhật chiều cao các nút sau mỗi phép xoay không?
Có. Một bug phổ biến là xoay con trỏ đúng nhưng quên tính lại chiều cao của hai nút liên quan. Sau mỗi phép xoay, bạn phải cập nhật chiều cao của nút bị hạ xuống trước, rồi đến nút được đưa lên, vì chiều cao của nút được đưa lên phụ thuộc vào các nút con mới của nó. Bỏ qua bước này sẽ để lại hệ số cân bằng sai, làm hỏng các quyết định cân bằng lại về sau.
Tài nguyên liên quan
Thêm mô phỏng trực quan
