BST — Insert, search, delete và tại sao skewed BST là O(n)

TL;DR: BST (Binary Search Tree) đảm bảo: left subtree chứa tất cả giá trị nhỏ hơn node hiện tại, right subtree chứa tất cả giá trị lớn hơn — áp dụng đệ quy. Hệ quả: in-order traversal cho sorted sequence; search/insert/delete là O(chiều cao cây). Vấn đề cốt lõi: với sorted input (timestamp tăng, auto-increment ID), cây "ngả hẳn một phía" — height = n, mọi operation thoái hóa về O(n). Random input cho expected height O(log n), nhưng production data hiếm khi random. Giải pháp: dùng self-balancing BST (xem bài 06 — AVL và Red-Black tree).

Tutorial BST dạy "search O(log n)" — nghe thuyết phục. Benchmark nhỏ với 1000 phần tử random xác nhận: search nhanh, mỗi bước loại bỏ một nửa cây. Dev hài lòng, ship lên production. Tuần sau, team load production data theo thứ tự timestamp tăng dần — insert 1, 2, 3, ..., N sorted vào BST. Cây bỗng "ngả phải" hoàn toàn: mỗi node chỉ có right child, không có left child. Search 500.000 phần tử từ O(log 500000) ≈ 19 bước xuống còn O(500000) = 500.000 bước. Hệ thống chậm lại, không exception, không warning — chỉ có latency tăng dần.

Bài này dạy BST từ insert/search/delete với pseudocode đầy đủ — bao gồm delete với in-order successor (case khó nhất) — và giải thích tại sao sorted input phá hỏng BST, dẫn đến sự cần thiết của balanced BST (bài 06 dive vào AVL và Red-Black tree).

1. Analogy — Cây phả hệ chia trái/phải

Hình dung một cây phả hệ đặc biệt: mỗi người trong cây có tối đa hai người con — con bên trái luôn có tên đứng trước (alphabetically nhỏ hơn), con bên phải luôn có tên đứng sau. Tổ tiên ở gốc. Muốn tìm một người, bạn bắt đầu từ gốc: so sánh tên cần tìm với người hiện tại, bước sang trái nếu nhỏ hơn, bước sang phải nếu lớn hơn — và lặp lại cho đến khi tìm thấy.

Nếu cây "cân đối" — mỗi bước loại bỏ một nửa nhánh còn lại — bạn tìm được người trong O(log n) bước. Nhưng nếu cây "ngả hẳn sang phải" (toàn bộ là right child), tìm người cuối cùng trong cây phải đi qua toàn bộ — đúng như duyệt linked list O(n).

2. BST property và cấu trúc node

Định nghĩa BST property: Với mỗi node n trong cây, tất cả node trong left subtree có giá trị nhỏ hơn n.value, và tất cả node trong right subtree có giá trị lớn hơn n.value. Property này áp dụng đệ quy cho mọi node trong cây — không chỉ node gốc và con trực tiếp.

Hệ quả quan trọng: In-order traversal (left → root → right) của một BST hợp lệ luôn cho ra sorted sequence. Đây là cách dễ nhất để kiểm tra BST đúng: in-order phải tăng dần.

-- BST node: lưu giá trị + con trái + con phải
BST node:
    value
    left  <- BST node hoặc null
    right <- BST node hoặc null

Ví dụ BST hợp lệ sau khi insert sequence 5, 3, 8, 1, 4, 7, 9:

graph TD
    N5["5 (root)"]
    N3["3"]
    N8["8"]
    N1["1"]
    N4["4"]
    N7["7"]
    N9["9"]

    N5 --> N3
    N5 --> N8
    N3 --> N1
    N3 --> N4
    N8 --> N7
    N8 --> N9

In-order traversal: 1, 3, 4, 5, 7, 8, 9 — đúng sorted sequence.

3. Insert (đệ quy)

Insert đi theo path từ root xuống leaf, dựa vào BST property để chọn nhánh trái hay phải, cho đến khi gặp null — điểm đó là vị trí insert node mới.

-- Insert value vào BST có root là 'root'.
-- Trả về root mới (cần khi cây rỗng).
-- Duplicate: bỏ qua (có thể đổi thành đếm hoặc ghi đè theo use case).
insert(root, value):
    if root = null: return new BST node với value    -- tìm thấy vị trí insert

    if value < root.value:
        root.left  <- insert(root.left, value)    -- đi trái
    else if value > root.value:
        root.right <- insert(root.right, value)   -- đi phải
    -- value = root.value: duplicate -- bỏ qua; convention tuỳ use case
    return root

Time: O(chiều cao cây) Space: O(chiều cao cây) -- do call stack đệ quy

Trace insert sequence 5, 3, 8, 1, 4, 7, 9 từng bước:

Insert 5: root = null -> Node(5)
        5

Insert 3: 3 < 5 -> đi trái, left=null -> Node(3)
        5
       /
      3

Insert 8: 8 > 5 -> đi phải, right=null -> Node(8)
        5
       / \
      3   8

Insert 1: 1 < 5 -> trái; 1 < 3 -> trái -> Node(1)
Insert 4: 4 < 5 -> trái; 4 > 3 -> phải -> Node(4)
Insert 7: 7 > 5 -> phải; 7 < 8 -> trái -> Node(7)
Insert 9: 9 > 5 -> phải; 9 > 8 -> phải -> Node(9)

        5
       / \
      3   8
     / \ / \
    1  4 7  9

-- Iterative insert -- không đệ quy, an toàn trên deep tree
insertIterative(root, value):
    newNode <- BST node với value
    if root = null: return newNode

    current <- root
    while true:
        if value < current.value:
            if current.left = null:
                current.left <- newNode
                break
            current <- current.left
        else if value > current.value:
            if current.right = null:
                current.right <- newNode
                break
            current <- current.right
        else:
            break   -- duplicate: bỏ qua
    return root

4. Search

Search dùng BST property để đi thẳng xuống nhánh đúng — không cần duyệt toàn cây. Đây là iterative version (không có recursion overhead):

-- Search value trong BST.
-- Trả về node nếu tìm thấy, null nếu không có.
-- Trung bình O(log n) cho cây cân đối, O(n) cho cây skewed.
search(root, value):
    while root != null:
        if value = root.value: return root      -- tìm thấy
        if value < root.value: root <- root.left
        else: root <- root.right
    return null   -- không tìm thấy

Time: O(chiều cao cây) Space: O(1)

Complexity:

• Balanced BST (height ≈ log n): O(log n) mỗi bước loại bỏ một nửa cây.
• Skewed BST (height = n): O(n) — phải đi qua mọi node theo một đường thẳng.

So sánh với binary search trên array (bài 04): cùng O(log n) average, nhưng BST hỗ trợ thêm insert/delete hiệu quả mà array sorted không có.

5. Delete (3 cases)

Delete là operation phức tạp nhất của BST vì phải duy trì BST property sau khi xóa. Có 3 trường hợp tùy vào số con của node cần xóa.

Case 1 — Leaf node (không có con): Xóa trực tiếp, set parent's reference thành null.

        5                   5
       / \      xóa 1      / \
      3   8    -------->  3   8
     / \                   \
    1   4                   4

Case 2 — 1 con: Bypass node cần xóa, nối parent trực tiếp với con duy nhất.

        5                   5
       / \      xóa 3      / \
      3   8    -------->  1   8
     /
    1

Case 3 — 2 con: Không thể xóa trực tiếp vì phải giữ BST property cho cả hai nhánh. Giải pháp: tìm in-order successor (node nhỏ nhất trong right subtree), copy giá trị của nó vào node cần xóa, rồi xóa in-order successor (luôn là case 1 hoặc 2 — successor không có left child).

        5                   7
       / \      xóa 5      / \
      3   8    -------->  3   8
     / \ /                / \  \
    1  4 7               1   4  9
          \
           9

In-order successor của 5 là 7 (nhỏ nhất trong right subtree {8, 7, 9}). Copy 7 vào root, rồi delete node 7 từ right subtree — node 7 chỉ có right child 9 (case 2).

-- Delete value từ BST.
-- Trả về root mới (cần nếu root bị xóa).
delete(root, value):
    if root = null: return null

    if value < root.value:
        root.left  <- delete(root.left, value)    -- tìm về phía trái
    else if value > root.value:
        root.right <- delete(root.right, value)   -- tìm về phía phải
    else:
        -- Tìm thấy node cần xóa -- xử lý 3 case:

        -- Case 1: leaf node (không có con) -- cả left và right đều null
        -- Case 2a: chỉ có right child
        if root.left = null: return root.right

        -- Case 2b: chỉ có left child
        if root.right = null: return root.left

        -- Case 3: hai con
        -- Thay bằng in-order successor (node nhỏ nhất trong right subtree)
        succ          <- minNode(root.right)
        root.value    <- succ.value               -- copy giá trị của successor
        root.right    <- delete(root.right, succ.value)   -- xóa successor
    return root

-- Tìm node nhỏ nhất trong subtree (node ngoài cùng bên trái).
minNode(n):
    while n.left != null: n <- n.left
    return n

Time: O(chiều cao cây) Space: O(chiều cao cây) -- do call stack đệ quy

Tại sao in-order successor đúng? In-order successor là node nhỏ nhất trong right subtree — lớn hơn mọi node trong left subtree nhưng nhỏ hơn mọi node còn lại trong right subtree. Thay thế node cần xóa bằng successor đảm bảo BST property: left subtree (mọi giá trị nhỏ hơn cũ) vẫn nhỏ hơn successor, và right subtree còn lại (mọi giá trị lớn hơn successor) vẫn lớn hơn successor.

6. Skewed BST — linked list ẩn núp

Insert sorted sequence: 1, 2, 3, 4, 5:

Insert 1: root = Node(1)
1

Insert 2: 2 > 1 -> đi phải
1
 \
  2

Insert 3: 3 > 1 -> phải; 3 > 2 -> phải
1
 \
  2
   \
    3

Insert 4, 5: tiếp tục đi phải...
1
 \
  2
   \
    3
     \
      4
       \
        5

Mọi node chỉ có right child — cây "ngả phải" hoàn toàn. Height = n. Search, insert, delete tất cả O(n).

graph TD
    N1["1"]
    N2["2"]
    N3["3"]
    N4["4"]
    N5["5 (leaf)"]
    N1 -->|"right"| N2
    N2 -->|"right"| N3
    N3 -->|"right"| N4
    N4 -->|"right"| N5

Insert sorted descending: 5, 4, 3, 2, 1 → ngả trái, tương tự.

Insert random sequence: expected height O(log n). Thực nghiệm với n = 1000 phần tử random: height xấp xỉ 2 log n ≈ 20. Với sorted input: height = n = 1000.

Hazard trong production: Dữ liệu thực tế thường không random. Timestamp tăng dần, auto-increment ID, sorted file import — tất cả đều là sorted input đối với BST naive. Benchmark với random data sẽ không phát hiện được điều này.

n = 1_000_000:
  Random insert:  height ≈ 40    -> search 40 bước so sánh
  Sorted insert:  height = 1_000_000 -> search 1_000_000 bước so sánh
  Tốc độ chênh lệch: 25,000 lần

7. Pitfall tổng hợp

Pitfall 1 — Skewed BST dưới sorted/sequential input

Benchmark thường dùng random data → tree cân đối → O(log n) → pass. Production dùng data từ DB query có sắp xếp tăng dần → sorted → tree skew → O(n).

-- NGUY HIỂM: insert timestamp theo thứ tự tăng dần
timestamps <- lấy từ DB với ORDER BY created_at ASC
for each ts trong timestamps:
    root <- insert(root, ts)   -- tất cả đi vào right subtree -> O(n) tree

-- GIẢM THIỂU: shuffle trước (nếu thứ tự không quan trọng), hoặc dùng balanced BST
shuffle(timestamps)   -- phá vỡ thứ tự sorted
for each ts trong timestamps:
    root <- insert(root, ts)
-- TỐT HƠN: dùng TreeMap (Red-Black tree) -- luôn O(log n) bất kể thứ tự insert

Nếu data có pattern sorted (timestamp, monotonic ID), cần balanced BST (TreeMap/TreeSet) thay vì BST naive. Bài 06 sẽ giải thích AVL và Red-Black tree giữ cân bằng sau mỗi insert/delete.

Pitfall 2 — Mutable comparable key

Sau khi insert một object vào BST theo một giá trị so sánh, nếu giá trị đó thay đổi, BST property bị phá vỡ — object "lạc" trong sai nhánh, search không tìm được.

-- NGUY HIỂM: key có thể thay đổi sau khi insert
Event:
    priority: int    -- có thể thay đổi!
    compare(other): so sánh theo priority

e <- Event(priority=5)
root <- insert(root, e)      -- insert tại đúng vị trí cho priority=5
e.priority <- 10             -- BST structure giờ không hợp lệ!
search(root, e)              -- có thể không tìm thấy e dù nó đang trong cây

Tương tự pitfall của mutable key trong Map (bài 01). Best practice: dùng immutable key, hoặc ít nhất không thay đổi field dùng trong so sánh sau khi insert.

Pitfall 3 — Recursion depth trên skewed tree gây stack overflow

1 triệu node sorted insert → tree height = 1 triệu → recursive insert, search, delete cần call stack depth 1 triệu → stack overflow (default JVM stack thường 512KB–1MB).

-- NGUY HIỂM: 1M sorted inserts -> recursion depth 1M -> stack overflow
for i <- 0 đến 999_999:
    root <- insert(root, i)   -- recursive insert, depth = i

Cross-link: bài 02 (Recursion và call stack) giải thích default stack size và cách estimate maximum safe recursion depth. Fix: dùng iterative version (section 3 trong bài này), hoặc — tốt hơn — dùng balanced BST để tránh skew từ đầu.

8. Các ordered operation của BST

TreeMap và TreeSet trong Java implement Red-Black tree — một dạng balanced BST tự cân bằng sau mỗi insert/delete. Bài 06 sẽ deep dive vào rotation và recoloring. Ở đây chú ý các operation có thứ tự mà Map thông thường (HashMap) không làm được:

-- BST hỗ trợ các ordered operation mà hash map không thể:
BST ordered operations:
    findMin()          -- node nhỏ nhất: đi mãi sang trái -> O(log n)
    findMax()          -- node lớn nhất: đi mãi sang phải -> O(log n)
    ceilingKey(k)      -- key nhỏ nhất >= k (lower bound trên tree) -> O(log n)
    floorKey(k)        -- key lớn nhất <= k -> O(log n)
    higherKey(k)       -- key nhỏ nhất > k (upper bound trên tree) -> O(log n)
    subRange(a, b)     -- tất cả key trong [a, b] -> O(log n + k)
    inorderTraversal() -- duyệt theo thứ tự tăng dần -> O(n)

So sánh với Map thông thường (hash-based):

Hash map O(1) lookup nhưng không có khái niệm "key gần nhất" hay range scan — phải duyệt toàn bộ. Khi cần ordered operations, BST là lựa chọn đúng dù O(log n) chậm hơn O(1).

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

Leaderboard top-K: Bài toán gaming — duy trì top 100 player theo score. BST (tự cân bằng) tự sorted, findMax() cho player cao điểm nhất, range query cho top-K. Insert player mới O(log n), tìm rank O(log n).

Database index — B+tree: Database index không dùng BST mà dùng B+tree — BST khái quát hoá cho disk storage, mỗi node có thể chứa hàng trăm key thay vì 2. Bài 07 sẽ deep dive B+tree và lý do database chọn B+tree thay vì hash index cho range query. BST là stepping stone để hiểu B+tree.

Filesystem directory (Linux ext4 htree): Linux ext4 dùng "htree" (hash tree — BST variant) cho directory entries khi directory lớn. Directory entry lookup từ O(n) linear scan xuống O(log n). Cùng vấn đề skew nếu filenames sorted — htree giải quyết bằng cách hash filename trước khi insert.

Range query trong Git: Git commit history có timestamp tăng dần. BST (tự cân bằng) sắp xếp theo timestamp, headRange(cutoff) cho mọi commit trước một ngày cụ thể — O(log n). Hash map không làm được range query này.

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

• Bài 04 — Binary search: binary search trên array sorted — cùng tư duy "loại bỏ một nửa", nhưng BST áp dụng tư duy đó lên cấu trúc cây với thêm insert/delete.
• Bài 06 — Self-balancing tree: AVL và Red-Black tree giải quyết vấn đề skewed BST bằng cách tự cân bằng sau mỗi insert/delete — O(log n) guaranteed.
• Bài 07 — B-tree và B+tree: BST khái quát hoá cho disk, mỗi node chứa hàng trăm key — database index standard.

11. Deep Dive

12. Tóm tắt

• BST property: left subtree nhỏ hơn node, right subtree lớn hơn node — áp dụng đệ quy. In-order traversal = sorted sequence.
• Insert/Search: đi theo path từ root, so sánh tại mỗi node, rẽ trái hoặc phải — O(chiều cao cây).
• Delete 3 cases: leaf (xóa trực tiếp), 1 con (bypass), 2 con (thay bằng in-order successor rồi xóa successor — luôn là case 1 hoặc 2).
• Sorted input → skewed BST → O(n): insert 1, 2, ..., n tạo cây chỉ có right child, height = n, mọi operation O(n). Random input → expected height O(log n).
• Production hazard: data thực tế có pattern sorted (timestamp, ID) → skew → cần balanced BST.
• Khi nào chọn BST thay hash map: range query, sorted iteration, "key gần nhất" — bất kỳ operation nào yêu cầu thứ tự.

13. Tự kiểm tra

Bài tiếp theo: Self-balancing trees — AVL vs Red-Black