DSA Từ A-Z: Day 3 – Cấu Trúc Cây (Phần 2: Cây Cân Bằng)Học AI cùng Losers – Nơi những cái cây cũng phải học cách “giữ thăng bằng” như chúng ta!

Sau khi vật lộn với BST, hẳn bạn đã nhận ra: BST mất cân bằng giống như cuộc đời – chỉ cần vài lựa chọn sai lầm là mọi thứ đổ nát. Hôm nay, chúng ta sẽ học cách “thiền” cùng các cây cân bằng – nơi mọi thứ LUÔN ỔN ĐỊNH dù có gió bão!

1. AVL Trees: “Vũ Công Ballet” Của Cấu Trúc Dữ Liệu

1.1 Khái Niệm Cơ Bản

Visualization:

        Balance Factor = height(left) - height(right)
        |BF| ≤ 1 → Cân bằng
        ┌───┐
        │ 5 │ BF=0
        └─┬─┘
     ┌────┴─────┐
  ┌─┴─┐       ┌─┴─┐
  │ 3 │ BF=0 │ 8 │ BF=0
  └───┘       └───┘

AVL Tree – Nơi mọi node đều có Balance Factor (BF) trong [-1, 0, 1]

a. Các Loại Mất Cân Bằng

1. Left-Left (LL):

    5 (BF=2)
   /
  3 (BF=1)
 /
2

2. Right-Right (RR):

2 (BF=-2)
 \
  3 (BF=-1)
   \
    5

3. Left-Right (LR):

5 (BF=2)
 \
  3 (BF=-1)
 /
2

4. Right-Left (RL):

2 (BF=-2)
 \
  5 (BF=1)
   \
    3

1.2 Phép Quay (Rotation) – “Điệu Nhảy” Cân Bằng

a. Right Rotation (LL Case)

Code:

// Right rotation for LL case
Node* rightRotate(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;

    // Perform rotation
    x->right = y;
    y->left = T2;

    // Update heights
    y->height = 1 + max(height(y->left), height(y->right));
    x->height = 1 + max(height(x->left), height(x->right));

    return x; // New root
}

Giải thích:

1. Xác định node mất cân bằng (y)
2. “Nhấc” node trái của y (x) lên làm root mới
3. Điều chỉnh các cây con T2

b. Left Rotation (RR Case)

Code:

// Left rotation for RR case
Node* leftRotate(Node* x) {
    Node* y = x->right;
    Node* T2 = y->left;

    // Perform rotation
    y->left = x;
    x->right = T2;

    // Update heights
    x->height = 1 + max(height(x->left), height(x->right));
    y->height = 1 + max(height(y->left), height(y->right));

    return y; // New root
}

Visualization RR Case:

Before:        After:
  x              y
   \            /
    y   →     x
   /          \
  T2           T2

1.3 Ví Dụ Minh Họa Đầy Đủ

Insert Sequence: 10 → 20 → 30 → 40 → 50 → 25

Step 1: Insert 10, 20, 30 → RR case

10 (BF=-2) → Rotate left
 \
  20
   \
    30
After rotation:
    20
   /  \
 10    30

Step 2: Insert 40 → RR case at 20

    20 (BF=-2)
   /  \
10    30 (BF=-1)
       \
        40
After rotation:
    30
   /  \
 20    40
 /
10

Step 3: Insert 50 → RR case at 30

    30 (BF=-2)
   /  \
20    40 (BF=-1)
       \
        50
After rotation:
    40
   /  \
 30    50
 /
20

Step 4: Insert 25 → LR case at 40

      40 (BF=1)
     /
   30 (BF=1)
  /
20 (BF=-1)
 \
  25
After double rotation (right then left):
      30
     /  \
   25    40
  /       \
20        50

2. Red-Black Trees: “Luật Lệ Ngầm” Của Cây Cân Bằng

2.1 5 Nguyên Tắc Vàng

1. Mỗi node có màu đỏ hoặc đen
2. Root luôn đen
3. Lá (NIL) đen
4. Node đỏ chỉ có con đen
5. Mọi path từ root đến leaf có cùng số node đen

Visualization:

        B
       / \
      R   B
     / \   \
    B  B    R

2.2 Phép Xoay Và Đổi Màu

Case Study: Insert 15 vào cây sau

       10(B)
     /     \
    5(B)   20(R)
          /   \
        15(B) 30(B)

Violation: Uncle node (5B) là đen → Cần rotation và recolor

// Pseudocode for fixup
void fixViolation(Node* &root, Node* &pt) {
    while (pt != root && pt->parent->color == RED) {
        // ... check uncle color and cases ...
        if (uncle->color == BLACK) {
            // Perform rotation
            if (pt == parent->right && parent == grandParent->left) {
                leftRotate(parent);
                pt = parent;
                parent = pt->parent;
            }
            // Recolor and rotate
            grandParent->color = RED;
            parent->color = BLACK;
            rightRotate(grandParent);
        }
    }
    root->color = BLACK;
}

After Fix:

       15(B)
     /     \
   10(R)   20(R)
  /       /   \
5(B)    ...   30(B)

3. B-Trees: “Gã Khổng Lồ” Chuyên Xử Lý Big Data

3.1 Đặc Điểm

• Mỗi node chứa từ t đến 2t-1 keys (t là degree)
• Tất cả leaves cùng mức
• Sử dụng trong database, filesystems

Visualization (t=2):

        [10, 20]
      /    |     \
[5]    [15]     [25,30]

3.2 Insertion Và Split

Insert 16 vào:

        [10, 20]
      /    |     \
[5]    [15]     [25,30]

Step 1: Insert vào node [15] → [15,16]
Step 2: Node vượt 2t-1 → split:

        [10, 16, 20]
      /     |      |      \
[5]   [15]  [17]  [25,30]

3.3 Code Mẫu Cho Node Structure

// B-Tree node structure
class BTreeNode {
public:
    int *keys;      // Array of keys
    int t;          // Minimum degree
    BTreeNode **C;  // Child pointers
    int n;          // Current keys count
    bool leaf;      // Is leaf node

    BTreeNode(int _t, bool _leaf) {
        t = _t;
        leaf = _leaf;
        keys = new int[2*t-1];
        C = new BTreeNode*[2*t];
        n = 0;
    }
};

4. Ứng Dụng Thực Tế

• AVL Tree: Cần tìm kiếm nhanh, ít insert/delete (CAD databases)
• Red-Black Tree: Java’s TreeMap, C++ STL map (độ cân bằng tốt)
• B-Tree: Database indexing (MySQL), filesystems (NTFS, ReiserFS)

Complexity So Sánh:

5. Bài Tập “Máu Lửa”

5.1 Easy: Tính Balance Factor

int getBalance(Node* node) {
    if (node == nullptr) return 0;
    return height(node->left) - height(node->right);
}

Test case: Node có left height=3, right height=1 → BF=2

5.2 Medium: Implement Left-Right Rotation

Node* leftRightRotate(Node* z) {
    z->left = leftRotate(z->left);
    return rightRotate(z);
}

Áp dụng khi: LR case (z unbalanced, left child right-heavy)

5.3 Hard: Red-Black Tree Insertion

Thử implement insertion với 3 trường hợp:

1. Uncle đỏ → Recolor
2. Uncle đen → Rotation
3. Root luôn đen

6. Kết Luận & Triết Lý Cân Bằng

Cây cân bằng dạy ta bài học:

• AVL: Hoàn hảo không tồn tại, nhưng luôn phấn đấu
• Red-Black: Chấp nhận “luật lệ” để tồn tại
• B-Tree: Đôi khi “bành trướng” là cách tốt nhất để quản lý

Hãy như Red-Black Tree: Dù bên ngoài có thể đỏ (đam mê), nhưng gốc rễ luôn đen (vững chắc)!

Hẹn gặp lại ở Phần 3: Heap – Khi cây học cách “ưu tiên” điều quan trọng!

Loser1 question: Bạn đã từng mất cân bằng trong cuộc sống như AVL chưa? Hãy chia sẻ câu chuyện của bạn – chúng ta cùng nhau “rotate”!