什么是平衡BST（AVL和红黑树），为什么它们很重要？

Question

Accepted Answer

普通BST如果键按排序顺序到达，可能会退化成链表（O(n)操作）。**自平衡BST** — 如**AVL**和**红黑树** — 在插入/删除后自动**旋转**节点，将高度保持在~`log n`，保证**O(log n)**操作。

## 平衡问题

```text
Unbalanced (insert 1,2,3,4):   Balanced after rotations:
  1                                  2
   \                                / \
    2                              1   3
     \                                  \
      3                                  4
   height ~ n (BAD)            height ~ log n (GOOD)
```

## AVL vs 红黑树

| | AVL树 | 红黑树 |
|---|---|---|
| 平衡严格度 | 严格（高度平衡） | 较松散 |
| 查找 | 更快（更矮） | 略慢 |
| 插入/删除 | 更多旋转 | 更少旋转 |
| 最适合 | 读取密集的工作负载 | 写入密集的工作负载 |

## 保证的复杂度

| 操作 | 时间 |
|---|---|
| search | O(log n) |
| insert | O(log n) |
| delete | O(log n) |

两者通过**旋转** — 局部O(1)的重构来维持平衡，在保持BST排序的同时降低高度。

## 为什么这很重要

平衡树支撑标准库中的有序映射和集合（例如Java `TreeMap`、C++ `std::map`使用红黑树），提供排序迭代以及针对对抗性输入的对数操作保证。

当你需要BST的排序特性*和*对抗对抗性输入的硬性性能保证时，它们是答案。

平衡严格度	严格（高度平衡）	较松散
查找	更快（更矮）	略慢
插入/删除	更多旋转	更少旋转
最适合	读取密集的工作负载	写入密集的工作负载