Self-balancing tree — AVL vs Red-Black, intuition và lý do TreeMap chọn RB

Lesson 05 đã cho thấy một kịch bản không mong đợi: insert timestamp tăng dần vào BST naive biến cây thành một chuỗi node nối thẳng — height bằng n, mọi operation từ O(log n) rớt xuống O(n). Benchmark với random data không phát hiện được vấn đề này; production data mới lộ ra.

Giải pháp là self-balancing tree — cây tự động tái cấu trúc sau mỗi insert/delete để giữ height ở mức O(log n), bất kể thứ tự insert. Hai family chính tồn tại song song từ thập niên 1960–70: AVL tree (Adelson-Velsky & Landis, 1962) với balance condition rất chặt, và Red-Black tree (Bayer, 1972) với balance condition lỏng hơn nhưng ít rotation hơn. Java TreeMap chọn Red-Black. Vì sao?

Bài này dạy intuition cả hai — invariant, rotation cơ bản, trade-off — đủ để đọc source TreeMap mà không cần full-code AVL/RB từ đầu (đó là việc cho 3 buổi khác, không phải 25 phút).

1. Analogy — Hai quán café tự cân bằng nhân lực

Hình dung hai quán café cạnh nhau, mỗi quán phải điều nhân viên giữa các ca để không ca nào quá tải hay quá rảnh.

Quán AVL rất nghiêm: ca trưởng kiểm tra mỗi 5 phút, bất kỳ ca nào lệch nhau quá 1 nhân viên là điều chỉnh ngay. Khách hàng lúc nào cũng được phục vụ nhanh (cây cân đối tốt), nhưng ca trưởng liên tục phải chạy đi chạy lại điều phối (nhiều rotation hơn mỗi khi có insert/delete).

Quán Red-Black linh hoạt hơn: chỉ điều khi chênh lệch vượt ngưỡng — không chặt đến từng người. Giờ bình thường phục vụ tốt, giờ cao điểm hơi lệch một chút nhưng vẫn chấp nhận được. Ít lần điều phối hơn, ca trưởng đỡ căng hơn (ít rotation khi insert/delete).

2. Tại sao balanced tree bắt buộc — chiều cao và Big-O

Mọi operation trên BST (search, insert, delete) có độ phức tạp O(height cây). Do đó giữ height nhỏ là tất cả.

Balanced binary tree với n node có height xấp xỉ log₂(n):

n = 1_000_000 node:
  Balanced height:  log₂(1_000_000) ≈ 20
  Skewed height:    1_000_000

Search cost:
  Balanced: ~20 comparisons
  Skewed:   ~1_000_000 comparisons
  Difference: 50,000x

Mục tiêu của mọi self-balancing BST: đảm bảo height = O(log n) sau mỗi insert và delete — không chỉ lúc khởi tạo. Skewed tree không vi phạm BST property (in-order traversal vẫn đúng), nhưng vi phạm height bound → mất đảm bảo O(log n).

3. Rotation — cơ chế tái cân bằng

Rotation là thao tác cơ bản của mọi self-balancing BST. Nó thay đổi cấu trúc cây nhưng giữ nguyên BST property (in-order traversal không thay đổi).

3.1 Left rotate

Left rotate quanh node x — x đi xuống, y (right child của x) đi lên:

Before:                After:
    x                      y
   / \                    / \
  a   y       -->        x   c
     / \                / \
    b   c              a   b

In-order trước: a, x, b, y, c. In-order sau: a, x, b, y, c — giữ nguyên. BST property vẫn đúng vì b (từng là left child của y, tức lớn hơn x nhưng nhỏ hơn y) giờ trở thành right child của x.

Right rotate là mirror của left rotate — y đi xuống, x (left child của y) đi lên.

3.2 Code rotateLeft

// Left-rotate around node x.
// Precondition: x.right != null
// Returns new subtree root (y).
Node<T> rotateLeft(Node<T> x) {
    Node<T> y = x.right;   // y becomes new root
    x.right = y.left;      // b subtree moves from y.left to x.right
    y.left = x;            // x becomes left child of y
    return y;              // caller must update parent's reference to y
}

3.3 Double rotation

Một số trường hợp mất cân bằng cần hai rotation liên tiếp. Ví dụ Left-Right (LR) case trong AVL:

Trước:          Sau Right rotate(z):    Sau Left rotate(x):
    x                   x                       y
   / \                 / \                     / \
  z   c   -->        y   c      -->           z   x
   \                / \                      / \ / \
    y              z   b                    a  b b  c
   / \            /
  a   b          a

Rotation LR = right rotate z rồi left rotate x. Tương tự, Right-Left (RL) case = left rotate rồi right rotate.

4. AVL tree — strict height balance

AVL tree duy trì balance factor tại mỗi node: balance = height(left) - height(right). Invariant của AVL:

Với mọi node trong cây, |balance| ≤ 1.

Mọi node được phép có balance factor -1, 0, hoặc 1. Bất kỳ node nào có |balance| = 2 sau insert/delete đều phải được rebalance ngay.

4.1 Insert flow

1. Insert như BST bình thường.
2. Walk ngược từ node vừa insert lên đến root, cập nhật height mỗi node.
3. Tại node vi phạm |balance| = 2, xác định case và rotate:

4.2 Height bound

AVL tree đảm bảo height không vượt 1.44 * log₂(n) — chặt nhất trong các BBST phổ biến. Điều này đến từ Fibonacci tree (worst case AVL): cây AVL tệ nhất có height h chứa ít nhất F(h+2) - 1 node, tăng theo Fibonacci — nên n tăng exponential theo h.

Hệ quả: AVL search không bao giờ cần quá 1.44 * log₂(n) bước — trong khi Red-Black có thể cần đến 2 * log₂(n) bước.

4.3 Trade-off

Invariant chặt của AVL có giá: mỗi insert/delete có thể trigger rotation cascade từ leaf lên root. Rotation không rẻ (cần cập nhật height, parent pointer, recolor). Với workload write-heavy (nhiều insert/delete, ít search), AVL tốn nhiều hơn cần thiết.

5. Red-Black tree — looser balance

Red-Black tree không theo dõi height trực tiếp. Thay vào đó, mỗi node được tô màu đỏ hoặc đen, và 5 invariant về màu sắc đảm bảo cây không quá mất cân bằng.

5.1 Năm invariant

1. Mỗi node là red hoặc black.
2. Root là black.
3. Mọi lá NIL (sentinel) là black. NIL là node giả dùng để đơn giản hoá code — leaf "thật" trỏ đến NIL thay vì null.
4. Red node không có red parent — không có hai node đỏ liên tiếp trên bất kỳ path nào.
5. Mọi path từ một node bất kỳ xuống đến NIL đều đi qua cùng số node đen — gọi là "black height".

5.2 Hệ quả từ 5 invariant

Invariant 4 + 5 cùng nhau tạo ra bound rất quan trọng: longest path không vượt 2x shortest path.

Shortest path (all black):     B - B - B - ... - NIL
  Length = black_height

Longest path (alternating):    B - R - B - R - ... - B - NIL
  Length = 2 * black_height (at most)

=> height <= 2 * log₂(n+1)

Height bound 2 * log₂(n) của RB "lỏng" hơn AVL (1.44 * log₂(n)), nhưng đổi lại rotation ít thường xuyên hơn đáng kể — đây là trade-off cốt lõi.

5.3 Insert fixup — overview

Insert vào RB tree: thêm node mới, tô đỏ. Tô đỏ để không vi phạm invariant 5 ngay lập tức (số black node trên path không đổi). Tuy nhiên có thể vi phạm invariant 4 (red parent).

Fixup có 3 case chính, dựa vào màu của "uncle" (anh/chị của parent):

• Case 1 — Uncle red: Recolor parent và uncle thành black, grandparent thành red. Vấn đề "leo" lên grandparent, giải quyết đệ quy lên trên.
• Case 2 — Uncle black, zig configuration: Rotate để đưa về case 3.
• Case 3 — Uncle black, zag configuration: Rotate grandparent + recolor. Kết thúc fixup.

Delete fixup phức tạp hơn với 4 case — mention thôi, không full-code trong bài này. Complexity của cả insert và delete là O(log n) trong mọi trường hợp.

6. AVL vs Red-Black — bảng so sánh

Rule of thumb:

• Workload read-heavy với insert/delete hiếm → AVL thắng nhờ height nhỏ hơn.
• Workload mixed (insert, delete, search đan xen) → RB thắng nhờ rotation ít hơn mỗi write.
• Không đo thực tế → không kết luận được.

7. Java TreeMap source — Red-Black trong thực tế

TreeMap trong Java (java.base/java/util/TreeMap.java) là RB tree hoàn chỉnh. Cấu trúc node:

// Simplified from OpenJDK TreeMap.Entry
static final class Entry<K, V> implements Map.Entry<K, V> {
    K key;
    V value;
    Entry<K, V> left;
    Entry<K, V> right;
    Entry<K, V> parent;
    boolean color = BLACK;   // RED = false, BLACK = true (default boolean = false = RED)
}

// Color constants
private static final boolean RED   = false;
private static final boolean BLACK = true;

Chú ý: RED = false và BLACK = true. Design choice thú vị — default value của boolean trong Java là false, tức node mới tạo mặc định là RED. Đây là convention đúng (node insert mới vào RB tree được tô đỏ trước fixup) và tiết kiệm một dòng code khởi tạo.

Đoạn fixAfterInsertion từ OpenJDK (rút gọn):

// Fix RB invariants after insertion.
// 'x' is the newly-inserted node (red).
private void fixAfterInsertion(Entry<K, V> x) {
    x.color = RED;

    while (x != null && x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Entry<K, V> y = rightOf(parentOf(parentOf(x)));  // uncle
            if (colorOf(y) == RED) {
                // Case 1: uncle is red -- recolor and move up
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == rightOf(parentOf(x))) {
                    // Case 2: uncle black, zig -- rotate to get to case 3
                    x = parentOf(x);
                    rotateLeft(x);
                }
                // Case 3: uncle black, zag -- rotate grandparent
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            // Mirror of above (parent is right child of grandparent)
            // ... symmetric cases
        }
    }
    root.color = BLACK;   // invariant 2: root always black
}

Code này trực tiếp implement 3 case fixup đã mô tả ở section 5.3. colorOf, leftOf, rightOf, parentOf là helper null-safe (trả về BLACK cho null node, tức NIL sentinel). Nếu đọc source TreeMap không hiểu tại sao lại loop ngược lên và recolor, section 5.3 giải thích invariant đằng sau.

8. Pitfall tổng hợp

Pitfall 1 — Implement AVL/RB từ scratch trong production

AVL và RB tree có nhiều edge case tinh tế: rotation phải cập nhật parent pointer, recolor phải đúng thứ tự, delete có thêm 4 case fixup. Một lỗi nhỏ trong rotation → cây bị corrupt nhưng không crash ngay, chỉ fail silently với wrong search results. Debug tree corruption là một trong những trải nghiệm tệ nhất trong career dev.

// WRONG approach for production:
class MyAvlTree<T> { ... }  // 300 lines of rotation code with subtle bugs

// CORRECT approach:
TreeMap<K, V> map = new TreeMap<>();  // battle-tested, O(log n) guaranteed

Trừ khi có constraint đặc biệt (embedded system, custom memory allocator, benchmark cụ thể), dùng TreeMap/TreeSet từ JDK.

Pitfall 2 — Quên update parent pointer sau rotation

Nếu node có parent field, mỗi rotation phải cập nhật parent của: node cũ (nay trở thành con), node mới (nay trở thành root của subtree), và subtree b (đổi chủ sau rotation — xem diagram section 3.1).

// INCOMPLETE rotation -- forgets parent update
Node<T> rotateLeft(Node<T> x) {
    Node<T> y = x.right;
    x.right = y.left;
    y.left = x;
    return y;
    // BUG: y.parent, x.parent, and y.left.parent (old b) all need update!
}

// COMPLETE rotation with parent tracking
Node<T> rotateLeft(Node<T> x) {
    Node<T> y = x.right;
    x.right = y.left;
    if (y.left != null) y.left.parent = x;   // b now belongs to x
    y.parent = x.parent;                      // y takes x's place
    if (x.parent == null) root = y;           // x was root
    else if (x == x.parent.left) x.parent.left = y;
    else x.parent.right = y;
    y.left = x;
    x.parent = y;
    return y;
}

Đây là lý do source TreeMap.rotateLeft dài hơn đáng kể so với naive implementation.

Pitfall 3 — "AVL luôn nhanh hơn" là assumption sai

AVL height thấp hơn RB — đúng. Nhưng kết luận "AVL search luôn nhanh hơn" chỉ đúng cho read-heavy workload với balanced distribution. Với mixed workload (xen kẽ insert/delete/search):

• Mỗi insert/delete trong AVL có thể trigger rotation cascade lên gần root → tổng time per operation cao hơn.
• Cache effect: rotation thay đổi cấu trúc tree → CPU cache miss nhiều hơn.
• Thực đo với jmh benchmark trên realistic workload thường cho kết quả đáng ngạc nhiên.

Không đo = không kết luận. "Tôi nghĩ AVL nhanh hơn" không phải evidence.

9. Case study — Ai dùng gì và tại sao

Linux Kernel Completely Fair Scheduler (CFS): dùng RB tree để track các task đang chờ CPU. Workload: nhiều insert (task spawn) và delete (task end), search ít hơn (tìm task có vruntime nhỏ nhất). RB phù hợp vì write-heavy. Source: kernel/sched/fair.c, struct rb_root_cached.

Java TreeMap và TreeSet: RB tree. General-purpose, mixed workload. TreeMap là lựa chọn mặc định khi cần sorted map trong Java — không cần biết RB internals để dùng đúng, nhưng biết lý do giúp hiểu tại sao O(log n) không bao giờ bị vi phạm.

Database B-tree trên disk: Không phải AVL hay RB mà là B-tree — generalization của BST cho disk storage, mỗi node chứa hàng trăm key để tối ưu I/O. Lesson 07 sẽ deep dive. B-tree giải quyết bài toán khác (disk fanout), không phải cùng in-memory trade-off.

Redis ZSET (Sorted Set): Dùng skip list thay vì RB tree. Skip list là probabilistic balanced structure, code đơn giản hơn, performance comparable với RB trong practice. Module 4 lesson 07 sẽ cover skip list. Lý do Redis chọn skip list: dễ implement đúng, range query dễ hơn trên tree.

10. Ứng dụng thực tế

TreeMap ordered operations hoạt động được vì in-order traversal của RB tree cho sorted sequence — đúng như BST property (lesson 05). firstKey, lastKey, headMap, tailMap, subMap tất cả đều là traversal trên RB tree đã sorted sẵn. O(log n + k) với k là số phần tử trong range.

C++ std::map (GNU libstdc++) cũng là RB tree, gần như cùng invariant với Java TreeMap. std::set tương tự. Đây là lý do interview C++ hay hỏi "map/set là gì bên dưới" — RB tree, luôn luôn (với GNU implementation).

Boost multi_index_container cho phép index cùng một collection theo nhiều key khác nhau. Mỗi ordered index là một RB tree. Dùng khi cần tìm kiếm theo nhiều trường không tốn kém space của nhiều TreeMap riêng lẻ.

Skip list như alternative — Redis ZSET và một số database dùng skip list thay RB vì code đơn giản hơn và range traversal tự nhiên hơn. Performance tương đương trong practice mặc dù worst case kém hơn về mặt lý thuyết. Module 4 lesson 07 sẽ so sánh cụ thể.

11. Deep Dive

12. Tóm tắt

• Self-balancing tree giữ height O(log n) sau mỗi insert/delete — giải quyết skewed BST từ lesson 05.
• Rotation là cơ chế tái cân bằng: thay đổi cấu trúc cây nhưng giữ nguyên BST property (in-order không đổi). Left rotate và right rotate là hai thao tác cơ bản.
• AVL invariant: |height(left) - height(right)| ≤ 1 tại mọi node. Height bound: tối đa 1.44 * log₂(n). Rotation thường xuyên hơn.
• RB invariant: 5 quy tắc màu sắc (root black, no two reds, equal black height trên mọi path). Height bound: tối đa 2 * log₂(n). Rotation ít hơn mỗi write.
• AVL thắng workload read-heavy. RB thắng mixed read/write workload.
• Java TreeMap dùng RB tree — O(log n) guaranteed, mọi ordered API (firstKey, subMap...) hoạt động đúng nhờ in-order traversal.
• Không tự implement AVL/RB trong production: dùng standard library trừ khi có constraint đặc biệt.
• Đo trước khi kết luận — "AVL luôn nhanh hơn RB" là false claim cho mixed workload.

13. Tự kiểm tra

Bài tiếp theo: B-tree và B+tree — disk index, fanout, vì sao database chọn nó