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

TL;DR: Self-balancing BST tự động tái cấu trúc sau mỗi insert/delete để giữ height O(log n) — bất kể thứ tự insert. AVL tree duy trì balance factor |height(left) - height(right)| ≤ 1 tại mọi node, height tối đa 1.44 * log n — chặt, nhiều rotation hơn. Red-Black tree dùng 5 invariant màu sắc, height tối đa 2 * log n — lỏng hơn, ít rotation hơn mỗi write. 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). Java TreeMap chọn Red-Black vì general-purpose, mixed workload — write cost thấp hơn AVL quan trọng hơn height nhỏ hơn một chút.

Bài 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:
  Height cân đối:  log(1_000_000) ≈ 20
  Height skewed:   1_000_000

Chi phí search:
  Cân đối: ~20 bước so sánh
  Skewed:  ~1_000_000 bước so sánh
  Chênh lệch: 50,000 lần

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:

Trước:                Sau:
    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 Pseudocode rotateLeft

-- Left-rotate quanh node x.
-- Điều kiện trước: x.right != null
-- Trả về root mới của subtree (y).
rotateLeft(x):
    y       <- x.right       -- y trở thành root mới
    x.right <- y.left        -- subtree b chuyển từ y.left sang x.right
    y.left  <- x             -- x trở thành left child của y
    return y                 -- caller phải cập nhật tham chiếu parent sang 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

-- Insert vào AVL tree
avl_insert(root, value):
    root <- bst_insert(root, value)    -- insert bình thường như BST

    -- Đi ngược từ node vừa insert lên đến root
    -- Cập nhật height mỗi node
    -- Tại node vi phạm |balance| = 2, xác định case và rotate:

    balance <- height(root.left) - height(root.right)

    -- Case LL: left child nặng, left-left gây ra
    if balance > 1 AND value < root.left.value:
        return rotateRight(root)

    -- Case RR: right child nặng, right-right gây ra
    if balance < -1 AND value > root.right.value:
        return rotateLeft(root)

    -- Case LR: left child nặng, left-right gây ra
    if balance > 1 AND value > root.left.value:
        root.left <- rotateLeft(root.left)
        return rotateRight(root)

    -- Case RL: right child nặng, right-left gây ra
    if balance < -1 AND value < root.right.value:
        root.right <- rotateRight(root.right)
        return rotateLeft(root)

    return root

Time: O(log n) Space: O(log n) -- đệ quy

graph TD
    INS["Insert như BST bình thường"]
    UPD["Cập nhật height đi ngược lên root"]
    CHK{"Tìm node vi phạm |balance| = 2"}
    CASE["Xác định case: LL / RR / LR / RL"]
    ROT["Áp dụng 1 hoặc 2 rotation"]
    DONE["Cây thoả AVL invariant"]

    INS --> UPD --> CHK
    CHK -- "tìm thấy" --> CASE --> ROT --> DONE
    CHK -- "không có" --> DONE

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 balanced BST 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. 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à đỏ hoặc đen.
2. Root là đen.
3. Mọi lá NIL (sentinel) là đen. NIL là node giả dùng để đơn giản hoá code — leaf "thật" trỏ đến NIL thay vì null.
4. Node đỏ không có 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.

Đường đi ngắn nhất (toàn đen): Đen - Đen - Đen - ... - NIL
  Độ dài = black_height

Đường đi dài nhất (xen kẽ):    Đen - Đỏ - Đen - Đỏ - ... - Đen - NIL
  Độ dài = 2 * black_height (tối đa)

=> 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 (parent đỏ).

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

• Case 1 — Uncle đỏ: Recolor parent và uncle thành đen, grandparent thành đỏ. Vấn đề "leo" lên grandparent, giải quyết đệ quy lên trên.
• Case 2 — Uncle đen, cấu hình zig: Rotate để đưa về case 3.
• Case 3 — Uncle đen, cấu hình zag: 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. Red-Black tree trong thực tế — cấu trúc node

Red-Black tree được dùng trong nhiều implementation thực tế. Cấu trúc node điển hình:

-- RB tree node: lưu key, value, màu sắc, và con trái/phải/parent
RBNode:
    key
    value
    color      <- ĐỎ hoặc ĐEN; node mới insert mặc định ĐỎ
    left       <- RBNode hoặc NIL sentinel
    right      <- RBNode hoặc NIL sentinel
    parent     <- RBNode hoặc null (nếu là root)

-- Hằng số màu
ĐỎ   = false   -- convention thú vị: default boolean = false = ĐỎ
ĐEN  = true    -- node mới mặc định ĐỎ mà không cần gán tường minh

Đoạn fixAfterInsertion (rút gọn, giải thích từng bước):

-- Fix RB invariants sau khi insert node x (đỏ).
fixAfterInsertion(x):
    x.color <- ĐỎ

    while x != null AND x != root AND x.parent.color = ĐỎ:
        if parent(x) = leftChild(grandparent(x)):
            uncle <- rightChild(grandparent(x))

            if color(uncle) = ĐỎ:
                -- Case 1: uncle đỏ → recolor và leo lên
                setColor(parent(x), ĐEN)
                setColor(uncle, ĐEN)
                setColor(grandparent(x), ĐỎ)
                x <- grandparent(x)
            else:
                if x = rightChild(parent(x)):
                    -- Case 2: uncle đen, cấu hình zig → rotate về case 3
                    x <- parent(x)
                    rotateLeft(x)
                -- Case 3: uncle đen, cấu hình zag → rotate grandparent
                setColor(parent(x), ĐEN)
                setColor(grandparent(x), ĐỎ)
                rotateRight(grandparent(x))
        else:
            -- Đối xứng của trên (parent là right child của grandparent)
            ...

    root.color <- ĐEN    -- invariant 2: root luôn đen

Time: O(log n) Space: O(log n) -- đệ quy

Code này trực tiếp implement 3 case fixup đã mô tả ở section 5.3. Nếu đọc source thực tế của TreeMap mà 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 cho production:
MyAvlTree: ...   -- 300 dòng rotation code với subtle bug

-- CORRECT approach:
dùng TreeMap / TreeSet từ standard library
-- đã được test hàng triệu lần, O(log n) guaranteed

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

Pitfall 2 — Quên update parent pointer sau rotation

Nếu node có trường parent, 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).

-- KHÔNG ĐẦY ĐỦ: rotation quên update parent
rotateLeft_broken(x):
    y       <- x.right
    x.right <- y.left
    y.left  <- x
    return y
    -- BUG: y.parent, x.parent, và y.left.parent (b cũ) đều cần update!

-- ĐẦY ĐỦ: rotation với parent tracking
rotateLeft(x):
    y       <- x.right
    x.right <- y.left
    if y.left != null: y.left.parent <- x     -- b nay thuộc x
    y.parent <- x.parent                      -- y chiếm vị trí của x
    if x.parent = null: root <- y             -- x là 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 rotateLeft thực tế 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 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.

Java TreeMap và TreeSet: RB tree. General-purpose, mixed workload. TreeMap là lựa chọn mặc định khi cần sorted map — 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. Bài 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. 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 (bài 05). firstKey, lastKey, headMap, tailMap, subMap tất cả đều là traversal trên RB tree đã sorted sẵn. Range query có độ phức tạp O(log n + k) — O(log n) để tìm điểm bắt đầu, cộng O(k) để liệt kê k phần tử trong range.

C++ std::map (GNU libstdc++) cũng là RB tree, gần như cùng invariant. 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).

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.

11. Liên hệ các bài khác

• Bài 05 — BST: BST property, insert/delete, lý do cần balanced tree — bài này là giải pháp cho vấn đề skewed BST ở bài 05.
• Bài 07 — B-tree và B+tree: generalization cho disk storage, tại sao database không dùng RB mà dùng B+tree — fanout lớn hơn, ít I/O hơn.

12. Deep Dive

13. Tóm tắt

• Self-balancing tree giữ height O(log n) sau mỗi insert/delete — giải quyết skewed BST từ bài 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 đen, không có hai đỏ liên tiếp, 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.

14. Tự kiểm tra

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