什么是二叉搜索树（BST），它的操作复杂度是多少？

Question

Accepted Answer

**二叉搜索树**是一个具有排序不变量的二叉树：对于每个节点，**其左子树中的所有键都较小**，**其右子树中的所有键都较大**。这使您可以通过在每一步减半问题空间来进行搜索。

## The invariant

```text
        8
       / \
      3    10
     / \     \
    1   6     14     left < node < right at every node
```

## Search and insert

```python
def search(node, key):
    while node:
        if key == node.val: return node
        node = node.left if key < node.val else node.right  # go one way
    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
```

## Complexity

| Operation | Balanced | Worst (degenerate) |
|---|---|---|
| search | O(log n) | O(n) |
| insert | O(log n) | O(n) |
| delete | O(log n) | O(n) |

**最坏情况**发生在按有序顺序插入键时——树退化为高度为 `n` 的链表。

## Trade-offs

- **优势**：O(n) 时间的有序遍历；支持范围查询和前驱/后继操作。
- **劣势**：自身不保证平衡——需要 AVL 或红黑树变体来维持 O(log n) 性能。

## 为什么这很重要

BST 为您提供具有对数级操作的有序动态数据——这是数据库索引和有序映射的概念祖先。

退化问题推动了**自平衡树**的发展，这是面试中的关键后续话题。