Balanced BST — AVL Tree & Red-Black Tree

Mỗi khi bạn dùng TreeMap trong Java, std::map trong C++, hay index B-Tree trong PostgreSQL — bên dưới đều là một dạng cây nhị phân tìm kiếm tự cân bằng. Đây là cấu trúc dữ liệu đảm bảo mọi thao tác search, insert, delete đều chạy trong O(log n) — không phụ thuộc vào thứ tự dữ liệu đầu vào.

🎯 Mục tiêu

Sau bài này, bạn sẽ:

Hiểu vì sao BST thông thường có thể suy biến thành O(n)
Nắm vững 4 loại rotation trong AVL Tree (LL, RR, LR, RL)
Hiểu 5 tính chất của Red-Black Tree và cách duy trì chúng
So sánh được AVL vs Red-Black để chọn đúng cho từng use case
Biết nơi chúng được dùng trong production systems

Bức tranh tư duy — Tại sao cần tự cân bằng?

Hình dung bạn xây một cây gia phả. Nếu mọi thành viên chỉ sinh một con duy nhất, cây gia phả trở thành một đường thẳng dài — tìm một người cụ thể phải duyệt từ đầu đến cuối. Nhưng nếu mỗi thành viên sinh hai con cân đối, cây rộng ra và tìm kiếm chỉ cần vài bước nhảy.

text

BST suy biến (insert 1,2,3,4,5):       BST cân bằng (cùng dữ liệu):

1                                             3
 \                                           / \
  2                                         2   4
   \                                       /     \
    3            ← O(n)                   1       5    ← O(log n)
     \
      4
       \
        5

Bài toán cốt lõi: Với BST thông thường, nếu dữ liệu đã sắp xếp → cây suy biến thành linked list → mọi thao tác O(n). Cây tự cân bằng giải quyết bằng cách tự động xoay (rotate) để giữ chiều cao ≈ log₂(n).

💡 HPN's Insight

Sự khác biệt giữa O(log n) và O(n) là sự khác biệt sống còn. Với 1 triệu phần tử: O(log n) ≈ 20 bước, O(n) = 1.000.000 bước. Đó là lý do mọi database engine đều dùng balanced tree cho index.

AVL Tree — Cây cân bằng nghiêm ngặt

Quy tắc AVL

AVL Tree (Adelson-Velsky & Landis, 1962) là BST với ràng buộc: balance factor của mọi node phải là -1, 0, hoặc +1.

Balance Factor = height(left subtree) - height(right subtree)

Khi insert hoặc delete phá vỡ điều kiện này, AVL Tree thực hiện rotation để khôi phục.

Bốn loại Rotation

1. LL Rotation (Left-Left / Right Rotation)

Khi node bị lệch trái-trái — xoay phải:

2. RR Rotation (Right-Right / Left Rotation)

Đối xứng với LL — khi node bị lệch phải-phải:

text

   z                  y
  / \               /   \
 T1   y    →       z     x
     / \          / \   / \
    T2   x       T1 T2 T3 T4
        / \
       T3  T4

3. LR Rotation (Left-Right / Double Rotation)

Node bị lệch trái-phải — xoay trái con trái rồi xoay phải gốc:

text

     z              z              x
    / \            / \           /   \
   y   T4  →     x   T4  →    y     z
  / \            / \          / \   / \
 T1  x          y   T3      T1 T2 T3 T4
    / \        / \
   T2 T3      T1 T2

4. RL Rotation (Right-Left / Double Rotation)

Đối xứng với LR — xoay phải con phải rồi xoay trái gốc.

Triển khai AVL Tree

PythonC++

python

class AVLNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1

class AVLTree:
    def _height(self, node):
        return node.height if node else 0

    def _balance_factor(self, node):
        return self._height(node.left) - self._height(node.right) if node else 0

    def _update_height(self, node):
        node.height = 1 + max(self._height(node.left), self._height(node.right))

    def _rotate_right(self, z):
        y = z.left
        t3 = y.right
        y.right = z
        z.left = t3
        self._update_height(z)
        self._update_height(y)
        return y

    def _rotate_left(self, z):
        y = z.right
        t2 = y.left
        y.left = z
        z.right = t2
        self._update_height(z)
        self._update_height(y)
        return y

    def _rebalance(self, node):
        self._update_height(node)
        bf = self._balance_factor(node)

        # LL Case
        if bf > 1 and self._balance_factor(node.left) >= 0:
            return self._rotate_right(node)
        # LR Case
        if bf > 1 and self._balance_factor(node.left) < 0:
            node.left = self._rotate_left(node.left)
            return self._rotate_right(node)
        # RR Case
        if bf < -1 and self._balance_factor(node.right) <= 0:
            return self._rotate_left(node)
        # RL Case
        if bf < -1 and self._balance_factor(node.right) > 0:
            node.right = self._rotate_right(node.right)
            return self._rotate_left(node)

        return node

    def insert(self, root, key):
        if not root:
            return AVLNode(key)
        if key < root.key:
            root.left = self.insert(root.left, key)
        elif key > root.key:
            root.right = self.insert(root.right, key)
        else:
            return root  # Không cho trùng key
        return self._rebalance(root)

cpp

struct AVLNode {
    int key;
    AVLNode *left, *right;
    int height;
    AVLNode(int k) : key(k), left(nullptr), right(nullptr), height(1) {}
};

class AVLTree {
    int height(AVLNode* n) { return n ? n->height : 0; }

    int balanceFactor(AVLNode* n) {
        return n ? height(n->left) - height(n->right) : 0;
    }

    void updateHeight(AVLNode* n) {
        n->height = 1 + std::max(height(n->left), height(n->right));
    }

    AVLNode* rotateRight(AVLNode* z) {
        AVLNode* y = z->left;
        z->left = y->right;
        y->right = z;
        updateHeight(z);
        updateHeight(y);
        return y;
    }

    AVLNode* rotateLeft(AVLNode* z) {
        AVLNode* y = z->right;
        z->right = y->left;
        y->left = z;
        updateHeight(z);
        updateHeight(y);
        return y;
    }

public:
    AVLNode* insert(AVLNode* node, int key) {
        if (!node) return new AVLNode(key);
        if (key < node->key) node->left = insert(node->left, key);
        else if (key > node->key) node->right = insert(node->right, key);
        else return node;

        updateHeight(node);
        int bf = balanceFactor(node);

        if (bf > 1 && key < node->left->key) return rotateRight(node);
        if (bf < -1 && key > node->right->key) return rotateLeft(node);
        if (bf > 1 && key > node->left->key) {
            node->left = rotateLeft(node->left);
            return rotateRight(node);
        }
        if (bf < -1 && key < node->right->key) {
            node->right = rotateRight(node->right);
            return rotateLeft(node);
        }
        return node;
    }
};

Red-Black Tree — Cây cân bằng linh hoạt

5 Tính chất bất biến

Red-Black Tree (RBT) là BST mà mỗi node được tô đỏ hoặc đen, thỏa mãn 5 quy tắc:

#	Tính chất	Ý nghĩa
1	Mỗi node là đỏ hoặc đen	Cơ chế đánh dấu
2	Root luôn đen	Anchor point
3	Mọi lá (NIL) là đen	Đơn giản hóa logic
4	Node đỏ không có con đỏ	Không hai đỏ liền nhau
5	Mọi đường từ root đến lá có cùng số node đen	Black-height cân bằng

⚠️ Quy tắc 4 & 5 là chìa khóa

Quy tắc 4 (no red-red) + Quy tắc 5 (equal black-height) cùng nhau đảm bảo: đường dài nhất ≤ 2 × đường ngắn nhất. Vì vậy chiều cao tối đa là 2 × log₂(n+1), vẫn O(log n).

Insert — Chiến lược tô màu

Khi chèn node mới (luôn đỏ), có 3 trường hợp cần xử lý:

text

Case 1: Uncle is RED
→ Tô lại: parent & uncle → đen, grandparent → đỏ
→ Tiếp tục kiểm tra từ grandparent lên trên

Case 2: Uncle is BLACK, node là con trong (zig-zag)
→ Rotate node lên vị trí parent
→ Chuyển thành Case 3

Case 3: Uncle is BLACK, node là con ngoài (zig-zig)
→ Rotate grandparent
→ Đổi màu parent ↔ grandparent

Delete — Phức tạp nhưng có hệ thống

Xóa node trong RBT phức tạp hơn insert vì phải duy trì black-height. Khi xóa node đen, black-height bị giảm → cần fixup với 4 case (và 4 case đối xứng).

📘 Thực tế

Trong interview, bạn hiếm khi phải code RBT deletion từ đầu. Nhưng cần hiểu tại sao RBT hoạt động và khi nào dùng nó.

So sánh: AVL Tree vs Red-Black Tree

Tiêu chí	AVL Tree	Red-Black Tree
Cân bằng	Nghiêm ngặt (BF ∈ {-1,0,+1})	Lỏng hơn (chiều cao ≤ 2×log n)
Chiều cao tối đa	~1.44 × log₂(n)	~2 × log₂(n)
Lookup speed	⚡ Nhanh hơn (cây thấp hơn)	Chậm hơn một chút
Insert speed	Chậm hơn (nhiều rotation hơn)	⚡ Nhanh hơn (ít rotation)
Delete speed	Chậm hơn (có thể O(log n) rotations)	⚡ Nhanh hơn (tối đa 3 rotations)
Memory overhead	Lưu height (int) mỗi node	Lưu color (1 bit) mỗi node
Best for	Read-heavy workloads	Write-heavy workloads
Ví dụ thực tế	Database indexing, dictionary	Java TreeMap, C++ std::map, Linux CFS

💡 Quy tắc chọn nhanh

Đọc nhiều, ghi ít → AVL Tree (lookup nhanh hơn ~20%)
Ghi nhiều, đọc ít → Red-Black Tree (insert/delete nhanh hơn)
Không biết chọn gì → Red-Black Tree (lựa chọn an toàn hơn, được dùng rộng rãi hơn)

Production — Nơi chúng được sử dụng

1. Java `TreeMap` / `TreeSet` — Red-Black Tree

java

// Bên dưới TreeMap là RBT
TreeMap<String, Integer> map = new TreeMap<>();
map.put("apple", 3);    // O(log n) guaranteed
map.put("banana", 5);
String first = map.firstKey();  // O(log n)

2. C++ `std::map` / `std::set` — Red-Black Tree

cpp

// std::map trong libstdc++ dùng RBT
std::map<std::string, int> m;
m["apple"] = 3;        // O(log n) guaranteed
auto it = m.lower_bound("b");  // O(log n)

3. Linux Completely Fair Scheduler (CFS)

Linux kernel dùng RBT để quản lý process scheduling — mỗi process là một node, key là virtual runtime. Process có vruntime nhỏ nhất (leftmost node) được chạy tiếp.

4. Database Index (AVL/B-Tree variants)

PostgreSQL và MySQL dùng B-Tree (mở rộng của balanced BST) cho index. Nguyên lý cân bằng giống AVL — đảm bảo O(log n) cho mọi query.

⚠️ Cạm bẫy

Sai lầm thường gặp khi implement Balanced BST:

Quên update height sau rotation — Rotation thay đổi cấu trúc cây nhưng nếu không cập nhật height, các rotation tiếp theo sẽ dựa trên thông tin sai → cây mất cân bằng dần
Nhầm thứ tự rotation trong LR/RL case — LR phải xoay trái con trái trước, rồi mới xoay phải gốc. Đảo thứ tự sẽ phá hỏng BST property
So sánh >= thay vì > khi quyết định rotation — Balance factor = 0 không cần rotation. Chỉ rotate khi |BF| > 1
Implement RBT deletion từ đầu trong interview — Đây là bẫy. Hãy giải thích nguyên lý thay vì code chi tiết. Ngay cả textbook cũng dành 3-4 trang cho deletion fixup

Phân tích độ phức tạp chi tiết

Thao tác	AVL Tree	Red-Black Tree	BST (worst)
Search	O(log n)	O(log n)	O(n)
Insert	O(log n) + ≤2 rotations	O(log n) + ≤2 rotations	O(n)
Delete	O(log n) + O(log n) rotations	O(log n) + ≤3 rotations	O(n)
Space	O(n)	O(n)	O(n)
Min/Max	O(log n)	O(log n)	O(n)

🧠 Quiz

Câu 1: Tại sao BST thông thường có thể suy biến thành O(n)?

[ ] A) Vì BST không hỗ trợ thao tác delete
[x] B) Vì khi dữ liệu đã sắp xếp, cây trở thành linked list với chiều cao n
[ ] C) Vì BST chỉ lưu được số nguyên
[ ] D) Vì BST luôn có chiều cao n bất kể thứ tự insert

💡 Giải thích: Khi insert dữ liệu đã sắp xếp (1, 2, 3, ..., n) vào BST, mỗi node chỉ có con phải → cây suy biến thành linked list. Chiều cao = n → mọi thao tác O(n). Cây tự cân bằng giải quyết bằng rotation.

Câu 2: Trong AVL Tree, khi balance factor của node z = +2 và balance factor của con trái y = -1, cần thực hiện rotation nào?

[ ] A) LL Rotation (xoay phải z)
[ ] B) RR Rotation (xoay trái z)
[x] C) LR Rotation (xoay trái y, rồi xoay phải z)
[ ] D) RL Rotation (xoay phải y, rồi xoay trái z)

💡 Giải thích: BF(z) = +2 nghĩa là lệch trái. BF(y) = -1 nghĩa là con trái lệch phải → đây là trường hợp Left-Right (LR). Phải xoay trái con trái trước để chuyển thành LL case, rồi xoay phải gốc.

Câu 3: Khi nào nên chọn AVL Tree thay vì Red-Black Tree?

[ ] A) Khi cần insert/delete liên tục với tần suất cao
[ ] B) Khi cần tiết kiệm memory tối đa
[x] C) Khi workload chủ yếu là lookup/search với ít thay đổi
[ ] D) Khi làm việc với Linux kernel scheduler

💡 Giải thích: AVL Tree cân bằng nghiêm ngặt hơn → chiều cao thấp hơn RBT (~1.44 log n vs ~2 log n) → lookup nhanh hơn ~20%. Nhưng insert/delete chậm hơn vì cần nhiều rotation hơn. Với read-heavy workload (database index, dictionary), AVL chiếm ưu thế.

Từ khóa glossary: Balanced BST, AVL Tree, Red-Black Tree, rotation, balance factor, black-height, self-balancing, TreeMap, std::map

Balanced BST — AVL Tree & Red-Black Tree ​

Bức tranh tư duy — Tại sao cần tự cân bằng? ​

AVL Tree — Cây cân bằng nghiêm ngặt ​

Quy tắc AVL ​

Bốn loại Rotation ​

1. LL Rotation (Left-Left / Right Rotation) ​

2. RR Rotation (Right-Right / Left Rotation) ​

3. LR Rotation (Left-Right / Double Rotation) ​

4. RL Rotation (Right-Left / Double Rotation) ​

Triển khai AVL Tree ​

Red-Black Tree — Cây cân bằng linh hoạt ​

5 Tính chất bất biến ​

Insert — Chiến lược tô màu ​

Delete — Phức tạp nhưng có hệ thống ​

So sánh: AVL Tree vs Red-Black Tree ​

Production — Nơi chúng được sử dụng ​

1. Java TreeMap / TreeSet — Red-Black Tree ​

2. C++ std::map / std::set — Red-Black Tree ​

3. Linux Completely Fair Scheduler (CFS) ​

4. Database Index (AVL/B-Tree variants) ​

Phân tích độ phức tạp chi tiết ​

Câu 1: Tại sao BST thông thường có thể suy biến thành O(n)? ​

Câu 2: Trong AVL Tree, khi balance factor của node z = +2 và balance factor của con trái y = -1, cần thực hiện rotation nào? ​

Câu 3: Khi nào nên chọn AVL Tree thay vì Red-Black Tree? ​

Balanced BST — AVL Tree & Red-Black Tree

Bức tranh tư duy — Tại sao cần tự cân bằng?

AVL Tree — Cây cân bằng nghiêm ngặt

Quy tắc AVL

Bốn loại Rotation

1. LL Rotation (Left-Left / Right Rotation)

2. RR Rotation (Right-Right / Left Rotation)

3. LR Rotation (Left-Right / Double Rotation)

4. RL Rotation (Right-Left / Double Rotation)

Triển khai AVL Tree

Red-Black Tree — Cây cân bằng linh hoạt

5 Tính chất bất biến

Insert — Chiến lược tô màu

Delete — Phức tạp nhưng có hệ thống

So sánh: AVL Tree vs Red-Black Tree

Production — Nơi chúng được sử dụng

1. Java `TreeMap` / `TreeSet` — Red-Black Tree

2. C++ `std::map` / `std::set` — Red-Black Tree

3. Linux Completely Fair Scheduler (CFS)

4. Database Index (AVL/B-Tree variants)

Phân tích độ phức tạp chi tiết

Câu 1: Tại sao BST thông thường có thể suy biến thành O(n)?

Câu 2: Trong AVL Tree, khi balance factor của node z = +2 và balance factor của con trái y = -1, cần thực hiện rotation nào?

Câu 3: Khi nào nên chọn AVL Tree thay vì Red-Black Tree?