Binary Search Tree — Insert, search, delete, và lý do skewed BST trở thành linked list

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 code đầ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 (giới thiệu thôi; lesson 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 -- generic, requires Comparable for ordering
class Node<T extends Comparable<T>> {
    T value;
    Node<T> left, right;

    Node(T v) { value = v; }
}

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

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

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

3. Insert (recursive)

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 into BST rooted at 'root'.
// Returns new root (needed when tree was empty).
// Duplicate: skip (caller can change to count or overwrite).
public Node<T> insert(Node<T> root, T value) {
    if (root == null) return new Node<>(value);  // found insertion point

    int cmp = value.compareTo(root.value);
    if (cmp < 0) {
        root.left = insert(root.left, value);    // go left
    } else if (cmp > 0) {
        root.right = insert(root.right, value);  // go right
    }
    // cmp == 0: duplicate -- skip; convention varies by use case
    return root;
}

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 -> go left, left=null -> Node(3)
        5
       /
      3

Insert 8: 8 > 5 -> go right, right=null -> Node(8)
        5
       / \
      3   8

Insert 1: 1 < 5 -> left; 1 < 3 -> left=null -> Node(1)
        5
       / \
      3   8
     /
    1

Insert 4: 4 < 5 -> left; 4 > 3 -> right=null -> Node(4)
        5
       / \
      3   8
     / \
    1   4

Insert 7: 7 > 5 -> right; 7 < 8 -> left=null -> Node(7)
        5
       / \
      3   8
     / \ /
    1  4 7

Insert 9: 9 > 5 -> right; 9 > 8 -> right=null -> Node(9)
        5
       / \
      3   8
     / \ / \
    1  4 7  9

// Iterative insert -- no recursion, safe on deep tree
public Node<T> insertIterative(Node<T> root, T value) {
    Node<T> newNode = new Node<>(value);
    if (root == null) return newNode;

    Node<T> current = root;
    while (true) {
        int cmp = value.compareTo(current.value);
        if (cmp < 0) {
            if (current.left == null) { current.left = newNode; break; }
            current = current.left;
        } else if (cmp > 0) {
            if (current.right == null) { current.right = newNode; break; }
            current = current.right;
        } else {
            break; // duplicate: skip
        }
    }
    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 for value in BST.
// Returns node if found, null if not found.
// Average O(log n) for balanced tree, O(n) for skewed.
public Node<T> search(Node<T> root, T value) {
    while (root != null) {
        int cmp = value.compareTo(root.value);
        if (cmp == 0) return root;             // found
        root = (cmp < 0) ? root.left : root.right;
    }
    return null;  // not found
}

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 (lesson 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
       / \      delete 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
       / \      delete 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
       / \      delete 5   / \
      3   8    -------->  3   8
     / \ /                / \  \
    1  4 7               1   4  9
          \
           (9 belongs to 8)

In-order successor của 5 là 7 (smallest in 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 from BST.
// Returns new root (needed if root itself is deleted).
public Node<T> delete(Node<T> root, T value) {
    if (root == null) return null;

    int cmp = value.compareTo(root.value);
    if (cmp < 0) {
        root.left = delete(root.left, value);     // search left
    } else if (cmp > 0) {
        root.right = delete(root.right, value);   // search right
    } else {
        // Found the node to delete -- handle 3 cases:

        // Case 1: leaf node (no children) -- root.left == null && root.right == null
        // Case 2a: only right child
        if (root.left == null) return root.right;

        // Case 2b: only left child
        if (root.right == null) return root.left;

        // Case 3: two children
        // Replace with in-order successor (smallest node in right subtree)
        Node<T> succ = minNode(root.right);
        root.value = succ.value;                  // copy successor's value
        root.right = delete(root.right, succ.value); // delete successor
    }
    return root;
}

// Find minimum node in subtree (leftmost node).
private Node<T> minNode(Node<T> n) {
    while (n.left != null) n = n.left;
    return n;
}

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 -> right
1
 \
  2

Insert 3: 3 > 1 -> right; 3 > 2 -> right
1
 \
  2
   \
    3

Insert 4, 5: tiep tuc right...
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).

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 comparisons
  Sorted insert:  height = 1_000_000 -> search 1_000_000 comparisons
  Speedup: 25,000x

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ó ORDER BY id → sorted → tree skew → O(n).

// DANGEROUS: insert timestamps in ascending order
List<Long> timestamps = fetchFromDB("ORDER BY created_at ASC");
for (Long ts : timestamps) {
    root = insert(root, ts);  // all go to right subtree -> O(n) tree
}

// MITIGATION: shuffle first (if order doesn't matter), or use balanced BST
Collections.shuffle(timestamps);  // break sorted order
for (Long ts : timestamps) {
    root = insert(root, ts);
}
// BETTER: use TreeMap (Red-Black tree) -- always O(log n) regardless of insert order

Nếu data có pattern sorted (timestamp, monotonic ID), cần balanced BST (TreeMap/TreeSet) thay vì BST naive. Lesson 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 compareTo value, nếu value đó thay đổi, BST property bị phá vỡ — object "lạc" trong sai nhánh, search không tìm được.

// DANGEROUS: mutable key
class Event implements Comparable<Event> {
    int priority;  // mutable!

    @Override
    public int compareTo(Event other) {
        return Integer.compare(this.priority, other.priority);
    }
}

Event e = new Event(5);
root = insert(root, e);   // inserted at correct position for priority=5
e.priority = 10;          // BST structure now invalid -- e is in wrong subtree
search(root, e);          // may not find e even though it's in the tree

Tương tự pitfall của mutable key trong HashMap (Module 3 lesson 01). Best practice: dùng immutable key, hoặc ít nhất không thay đổi field dùng trong compareTo 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 → StackOverflowError.

// DANGER: 1M sorted inserts -> recursion depth 1M -> StackOverflowError
for (int i = 0; i < 1_000_000; i++) {
    root = insert(root, i);  // recursive insert, depth = i
}

Cross-link: lesson 02 (Recursion và call stack) giải thích default stack size (thường 512KB–1MB trên JVM) 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. Java standard library — TreeMap và TreeSet

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. Lesson 06 sẽ deep dive vào rotation và recoloring. Ở đây chú ý API.

API TreeMap tương đương BST với ordered operations:

TreeMap<Integer, String> map = new TreeMap<>();

// Standard operations -- O(log n) guaranteed (not amortized)
map.put(5, "five");
map.put(3, "three");
map.put(8, "eight");
String val = map.get(3);      // "three"
map.remove(5);

// Ordered operations -- unique to sorted map, HashMap cannot do these
map.firstKey();               // smallest key: 3
map.lastKey();                // largest key: 8
map.ceilingKey(4);            // smallest key >= 4: 5 (lower bound on tree)
map.floorKey(4);              // largest key <= 4: 3
map.higherKey(5);             // smallest key strictly > 5: 8
map.lowerKey(5);              // largest key strictly < 5: 3

// Range query -- O(log n + k) where k = number of results
map.subMap(3, true, 8, false);  // keys in [3, 8): {3, 5}
map.headMap(5);                 // keys < 5
map.tailMap(5);                 // keys >= 5

// Iteration = in-order traversal = sorted
for (Map.Entry<Integer, String> e : map.entrySet()) {
    System.out.println(e.getKey()); // 3, 5, 8 -- sorted
}

TreeSet cho ordered set:

TreeSet<Integer> set = new TreeSet<>();
set.add(5); set.add(3); set.add(8);
set.first();        // 3
set.last();         // 8
set.ceiling(4);     // 5 -- smallest >= 4
set.floor(4);       // 3 -- largest <= 4
set.headSet(5);     // {3} -- elements < 5
set.tailSet(5);     // {5, 8} -- elements >= 5

So sánh HashSet vs TreeSet:

HashMap 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, TreeMap/TreeSet là lựa chọn đúng dù O(log n) chậm hơn O(1).

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

TreeSet cho leaderboard top-K: Bài toán gaming — duy trì top 100 player theo score. TreeSet tự sorted, last() cho player cao điểm nhất, headSet(threshold) cho range query. 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. Lesson 07 sẽ deep dive B+tree và lý do MySQL 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.

HashSet vs TreeSet — khi data có order requirement: Git commit history có timestamp tăng dần. TreeSet<Commit> sắp xếp theo timestamp, headSet(cutoff) cho mọi commit trước một ngày cụ thể — O(log n). HashSet không làm được range query này.

10. Deep Dive

11. 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.
• TreeMap/TreeSet: Red-Black tree, O(log n) guaranteed. Có thêm ordered API: ceilingKey, floorKey, subMap, headMap — HashMap không có.
• Khi nào chọn TreeMap thay HashMap: range query, sorted iteration, "key gần nhất" — bất kỳ operation nào yêu cầu thứ tự.

12. Tự kiểm tra

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