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

TL;DR: Self-balancing BST tự sắp xếp lại cấu trúc sau mỗi insert/delete để giữ height O(log n), bất kể thứ tự insert. AVL tree giữ chênh lệch chiều cao hai bên (balance factor) |height(left) - height(right)| ≤ 1 tại mọi node, height tối đa khoảng 1.44 * log n: cây thấp nhưng phải sửa nhiều hơn. Red-Black tree dùng 5 invariant về màu, height tối đa 2 * log n: cây cao hơn một chút, đổi lại mỗi lần ghi cần ít rotation hơn. Rotation (xoay cây) đổi cấu trúc nhưng giữ nguyên thứ tự in-order. Java TreeMap dùng Red-Black; lý do thường được nêu là một map đa dụng cần chi phí ghi thấp, nhưng JDK không công bố lý do chính thức.

Bài 05 cho thấy insert timestamp tăng dần vào BST ngây thơ biến cây thành một chuỗi node nối thẳng, mọi thao tác từ O(log n) rơi xuống O(n). Cách chữa là self-balancing tree. Hai họ chính: AVL tree (Adelson-Velsky & Landis, 1962) với điều kiện rất chặt, và Red-Black tree (Bayer, 1972, gọi là "symmetric binary B-tree"; tên red-black đến từ Guibas & Sedgewick, 1978) với điều kiện lỏng hơn.

Bài này dạy trực giác, invariant, rotation và đánh đổi của cả hai, đủ để đọc source TreeMap mà không phải tự code từ đầu.

1. Hình dung: 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, ca nào lệch nhau quá 1 nhân viên là điều chỉnh ngay. Khách lúc nào cũng được phục vụ nhanh (cây cân đối tốt), nhưng ca trưởng cứ phải chạy đi chạy lại để điều phối (nhiều rotation mỗi khi 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ờ thường thì 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 nên ca trưởng đỡ căng (ít rotation khi insert/delete).

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

Mọi thao tác trên BST (search, insert, delete) có độ phức tạp O(height của cây), nên giữ height nhỏ là điều quan trọng nhất.

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: cỡ 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. Cây skewed không vi phạm BST property (in-order traversal vẫn đúng), nhưng vi phạm giới hạn height, nên mất đảm bảo O(log n).

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

Rotation là thao tác nền tảng của mọi self-balancing BST. Nó đổi cấu trúc cây nhưng giữ nguyên BST property (in-order traversal không đổ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, không đổi. 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ờ thành right child của x.

Ví dụ nhỏ nhất: insert 1, 2, 3 vào BST ngây thơ ra chuỗi 1 → 2 → 3. Left rotate quanh 1: node 2 lên làm gốc, 1 thành con trái, 3 vẫn là con phải. Height giảm từ 3 xuống 2, in-order vẫn 1, 2, 3.

Right rotate là bản đối xứng 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

Hàm trả về gốc mới của cây con để nơi gọi gán lại (root.left <- rotateLeft(root.left)). Nếu kiểu "hàm trả kết quả ra cho nơi gọi" còn lạ, xem Hàm.

3.3 Double rotation

Có 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 (x lệch trái, z lệch phải):   Bước 1: left rotate z:   Bước 2: right rotate x:
      x                                  x                          y
     / \                                / \                       /   \
    z   d                              y   d                    z     x
   / \                                / \                      / \   / \
  a   y                              z   c                    a   b c   d
     / \                            / \
    b   c                          a   b

Rotation LR = left rotate z (con trái của x) rồi right rotate x. Tương tự, Right-Left (RL) case = right rotate con phải rồi left rotate node. In-order cả ba hình đều là a, z, b, y, c, x, d.

4. AVL tree, strict height balance

AVL tree giữ balance factor (độ lệch chiều cao) 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 chỉ được có balance factor -1, 0 hoặc 1. Node nào có |balance| = 2 sau insert/delete thì phải rebalance (cân bằng lại) 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

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. Con số này đến từ cây Fibonacci (trường hợp tệ nhất của AVL): cây AVL tệ nhất có height h chứa ít nhất F(h+2) - 1 node, tăng theo dãy Fibonacci, nên n tăng theo hàm mũ của h.

Hệ quả: AVL search không bao giờ cần quá 1.44 * log n bước, còn Red-Black có thể cần tới 2 * log n bước.

4.3 Trade-off

Invariant chặt của AVL phải trả giá: sau insert, AVL cần tối đa một rotation (đơn hoặc kép), nhưng sau delete có thể phải rotate ở nhiều tầng, lan lên tới O(log n) lần. Với workload ghi nhiều, đặc biệt nhiều delete, AVL tốn hơn mức cần thiết.

Thử ngẫmđánh đổi của AVL: invariant chặt khiến mỗi lần ghi có thể kéo theo chuỗi rotation. Với hệ thống insert và delete liên tục mà hiếm khi search, đổi lấy cây thấp hơn còn đáng không?

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 đảm bảo cây không lệch quá mức.

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ả để code đơn giản hơn: leaf "thật" trỏ tới NIL thay vì null.
4. Node đỏ không có parent đỏ: không có hai node đỏ liền nhau trên bất kỳ đường đi nào.
5. Mọi đường đi từ một node bất kỳ xuống tới NIL đều qua cùng số node đen, gọi là "black height".

5.2 Hệ quả từ 5 invariant

Invariant 4 và 5 cùng nhau tạo ra một giới hạn rất quan trọng: đường đi dài nhất không vượt 2 lần đường đi ngắn nhất.

Đườ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)

Giới hạn height 2 * log n của RB "lỏng" hơn AVL (1.44 * log n), nhưng đổi lại rotation ít hơn đáng kể. Đây là đánh đổi cốt lõi.

5.3 Insert fixup, overview

Insert vào RB tree: thêm node mới và tô đỏ. Tô đỏ để không vi phạm ngay invariant 5 (số node đen trên mỗi đường đi không đổi). Tuy nhiên có thể vi phạm invariant 4 (parent cũng đỏ).

Fixup (bước sửa lại sau insert) có 3 case chính, dựa vào màu của "uncle" (anh/chị/em của parent):

• Case 1: Uncle đỏ: Đổi parent và uncle thành đen, grandparent thành đỏ. Vấn đề "leo" lên grandparent và được xử lý tiếp lên trên.
• Case 2: Uncle đen, node và parent lệch nhau (hình tam giác): Rotate để đưa về case 3.
• Case 3: Uncle đen, node và parent thẳng hàng: Rotate grandparent + recolor. Kết thúc fixup.

Delete fixup phức tạp hơn với 4 case, bài này chỉ nhắc tới. Cả insert và delete đều O(log n), và số rotation của Red-Black là hằng số (tối đa 2 khi insert, 3 khi delete); phần việc còn lại là đổi màu.

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

Rule of thumb:

• Đọc nhiều, insert/delete hiếm: AVL có lợi nhờ cây thấp hơn.
• Đọc ghi lẫn lộn, nhất là có nhiều delete: RB có lợi nhờ mỗi lần ghi ít rotation hơn.
• Chưa đo trên workload thật thì chưa kết luận được.

Thử ngẫm"hơi nhanh hơn" và "hơi chậm hơn" ở bảng trên là toàn bộ chênh lệch search giữa AVL và Red-Black. Chênh lệch mơ hồ đó có đáng để bỏ TreeMap có sẵn mà tự viết một cây AVL không?

7. Red-Black tree trong thực tế, cấu trúc node

Red-Black tree có mặt trong nhiều cài đặt 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   -- JDK TreeMap: RED = false
ĐEN  = true    -- JDK TreeMap: BLACK = true (Entry mới mặc định BLACK, fixAfterInsertion gán RED 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, tam giác → rotate về case 3
                    x <- parent(x)
                    rotateLeft(x)
                -- Case 3: uncle đen, thẳng hàng → 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 cài đặt đúng 3 case fixup đã mô tả ở section 5.3. Nếu đọc source TreeMap mà chưa hiểu vì sao phải lặp ngược lên và đổi màu, section 5.3 giải thích invariant đứng sau.

8. Các bẫy thường gặp

Bẫy 1: Tự cài AVL/RB từ đầu trong production

AVL và RB có nhiều trường hợp biên tinh tế (parent pointer, thứ tự đổi màu, delete có 4 case fixup). Một lỗi nhỏ làm cây hỏng nhưng không crash ngay, chỉ lặng lẽ trả kết quả search sai, và debug cây hỏng là một trong những trải nghiệm tệ nhất của nghề. Trừ khi có ràng buộc đặc biệt (embedded, custom allocator, benchmark cụ thể), hãy dùng TreeMap/TreeSet của standard library.

Bẫy 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 thành con), node mới (nay thành root của subtree), và subtree b (đổi cha sau rotation, xem hình ở 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

Đó là lý do rotateLeft thực tế dài hơn hẳn bản ngây thơ.

Bẫy 3: "AVL luôn nhanh hơn" là giả định sai

AVL thấp hơn RB, nhưng "AVL search luôn nhanh hơn" chỉ đúng với workload đọc nhiều. Với workload lẫn lộn, delete trong AVL có thể kéo theo rotation ở nhiều tầng, còn chênh lệch height giữa hai loại chỉ cỡ vài bước so sánh, dễ bị chi phí khác (cache miss, so sánh key đắt) che mất. Không đo thì không kết luận.

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

Linux kernel scheduler: CFS (đến Linux 6.5) dùng RB tree để xếp các task đang chờ CPU theo vruntime; bộ lập lịch EEVDF thay CFS từ Linux 6.6 vẫn dùng RB tree. Workload nghiêng về ghi (task vào, task ra) và luôn lấy task ngoài cùng bên trái.

Java TreeMap và TreeSet: RB tree. TreeMap là lựa chọn mặc định khi cần map có thứ tự.

Database B-tree trên disk: Không phải AVL hay RB mà là B-tree, bản mở rộng của BST cho ổ đĩa, mỗi node chứa hàng trăm key để giảm I/O. Bài 07 sẽ đi sâu. B-tree giải quyết bài toán khác (fanout trên disk), không phải cùng đánh đổi như cây trong bộ nhớ.

Redis ZSET (Sorted Set): Dùng skip list thay vì RB tree. Skip list là cấu trúc cân bằng theo xác suất; tác giả Redis nêu lý do chọn là code đơn giản, dễ debug và range query tự nhiên, với hiệu năng tương đương cây cân bằng.

Thử ngẫmRedis chọn skip list thay Red-Black tree dù hiệu năng ngang nhau, chỉ vì code đơn giản hơn. Lý do "dễ cài đúng hơn" này có nên thắng cả một cấu trúc có độ phức tạp lý thuyết tốt hơn không?

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

Các thao tác theo thứ tự của TreeMap (firstKey, lastKey, headMap, tailMap, subMap) chạy được vì in-order traversal của RB tree cho ra dãy đã sắp xếp. Range query tốn O(log n + k): O(log n) để tìm điểm bắt đầu, O(k) để liệt kê k phần tử. C++ std::map/std::set của GNU libstdc++ cũng là RB tree, nên câu hỏi phỏng vấn "map bên dưới là gì" thường có đáp án này.

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

Bài 05: BST nêu vấn đề skewed BST mà bài này chữa; bài 07: B-tree và B+tree mở rộng cho ổ đĩa, với fanout lớn nên ít I/O hơn.

12. Đào sâu

Bài liên quan trong khoá học:

• BST: cấu trúc cây tìm kiếm gốc.
• B-Tree & B+Tree: mở rộng cây cân bằng ra thiết bị lưu trữ đĩa.
• Skip List: cấu trúc tìm kiếm xác suất đối đầu Red-Black Tree.

13. Tóm tắt

Checklist khi cần cây cân bằng:

• Đừng tự cài AVL hay Red-Black ở production; dùng TreeMap, TreeSet hoặc thư viện tương đương.
• Đọc nhiều, ghi ít thì AVL (cây thấp hơn) có lợi; ghi nhiều, nhất là delete, thì Red-Black (rotation mỗi lần ghi là hằng số).
• Tự code thì nhớ cập nhật con trỏ parent sau rotation, và test bằng dữ liệu đã sắp xếp.
• Muốn kết luận "cái nào nhanh hơn" thì đo trên workload thật, đừng tin câu "AVL luôn nhanh hơn".
• Cây trên disk là chuyện khác: sang bài B-tree.

14. Tự kiểm tra

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