Binary search tree (BST) là gì và độ phức tạp các thao tác của nó là gì?

Question

Accepted Answer

**Binary search tree** (cây tìm kiếm nhị phân) là một binary tree với một bất biến (invariant) về thứ tự: với mọi node, **tất cả key trong cây con bên trái nhỏ hơn**, và **tất cả key trong cây con bên phải lớn hơn**. Điều này cho phép bạn tìm kiếm bằng cách chia đôi bài toán ở mỗi bước.

## Bất biến (invariant)

```text
        8
       / \
      3    10
     / \     \
    1   6     14     left < node < right tại mọi node
```

## Tìm kiếm và chèn

```python
def search(node, key):
    while node:
        if key == node.val: return node
        node = node.left if key < node.val else node.right  # đi một hướng
    return None

def insert(node, key):
    if node is None: return Node(key)
    if key < node.val: node.left  = insert(node.left, key)
    else:              node.right = insert(node.right, key)
    return node
```

## Độ phức tạp

| Thao tác | Cân bằng | Tệ nhất (suy biến) |
|---|---|---|
| search | O(log n) | O(n) |
| insert | O(log n) | O(n) |
| delete | O(log n) | O(n) |

**Trường hợp tệ nhất** xảy ra khi key được chèn theo thứ tự đã sắp xếp — cây suy biến thành một linked list có chiều cao `n`.

## Đánh đổi

- **Điểm mạnh:** duyệt theo thứ tự trong O(n); hỗ trợ truy vấn khoảng (range query) và phần tử kế tiếp/liền trước (successor/predecessor).
- **Điểm yếu:** tự nó không đảm bảo cân bằng — cần một biến thể AVL hoặc red-black để giữ O(log n).

## Tại sao điều này quan trọng

BST cho bạn dữ liệu động, có thứ tự với các thao tác logarit — tổ tiên về mặt khái niệm của database index và ordered map.

Vấn đề suy biến thúc đẩy **cây tự cân bằng (self-balancing tree)**, một chủ đề tiếp nối quan trọng trong phỏng vấn.