拾石录
二叉查找树
- 什么是二叉查找树
- 两个重要性质
- 添加数据
- 删除结点
- 查找结点
- 时间复杂度
- 平衡二叉查找树
什么是二叉查找树
二叉查找树（Binary Search Tree，BST，又叫二叉搜索树或二叉排序树）是一种树形数据结构。它可以说是二分查找算法的树形体现——通过左右分支将查找范围不断缩小。
15
/ \
9 23
/ \ / \
3 12 17 28
/
8
两个重要性质
- 每个结点的值均大于其左子树上任意一个结点的值
15
/
9
/ \
3 12
/
8
结点 15 大于左子树上的所有值（9, 3, 12, 8）
结点 9 大于左子树上的所有值（3, 8）
- 每个结点的值均小于其右子树上任意一个结点的值
15
\
23
/ \
17 28
结点 15 小于右子树上的所有值（23, 17, 28）
结点 23 小于右子树上的所有值（28）
由这两个性质可以得出：
- 最小值：从根结点出发，一路往左走到底
- 最大值：从根结点出发，一路往右走到底
找最小值: 15 → 9 → 3 → 8？不，3 没有...
实际: 15 → 9 → 3 → (3的左子树到底) = 3
找最大值: 15 → 23 → 28 = 28
添加数据
添加数字 1 的过程——从根结点开始比较，小则往左，大则往右：
15
/ \
9 23
/ \ / \
3 12 17 28
/
8
添加 1:
1 < 15 → 往左
1 < 9 → 往左
1 < 3 → 往左
3 的左边已经没有结点了 → 把 1 作为新结点添加到 3 的左下方
15
/ \
9 23
/ \ / \
3 12 17 28
/
8
/
1 ← 新结点
删除结点
删除操作分三种情况：
情况 1：没有子结点 → 直接删除
删除 28:
23 23
/ \ → /
17 28 17
情况 2：只有一个子结点 → 删除后，子结点顶上来
删除 8（假设 8 只有一个子结点 1）:
3 3
/ → /
8 1
/
1
情况 3：有两个子结点 → 找左子树中的最大值（或右子树最小值）替换
删除 9（有两个子结点）:
15 15
/ \ / \
9 23 → 8 23
/ \ / \ / \ / \
3 12 17 28 3 12 17 28
/
8
左子树(3,8)中最大的是 8，把 8 移到 9 的位置
查找结点
查找数字 12 的过程——和二分查找一样，每次排除一半：
15
/ \
→ 9 23 ← 12 < 15，往左
/ \ / \
→ 3 12 17 28 ← 12 > 9，往右
↑
找到 12！
只比较了 2 次就找到了——这就是二叉查找树的高效之处。
时间复杂度
| 操作 | 平均情况 | 最糟情况 |
|---|---|---|
| 查找 | O(log n) | O(n) |
| 插入 | O(log n) | O(n) |
| 删除 | O(log n) | O(n) |
比较次数取决于树的高度。如果树比较均衡，高度为 log₂n，时间复杂度为 O(log n)。
最糟情况：如果数据本身就是有序的，树会退化成一条链，高度变成 n，时间复杂度退化为 O(n)。
退化成链表（最糟情况）:
1
\
2
\
3
\
4
\
5
查找变成顺序遍历，O(n)
平衡二叉查找树
为了解决退化问题，人们发明了平衡二叉查找树：
- AVL 树：任何结点的左右子树高度差不超过 1，插入/删除后自动旋转调整
- 红黑树：通过颜色标记和旋转保持近似平衡，Java 的 TreeMap 底层就是红黑树
此外，把子结点数从 2 扩展到 m（预先设定好的常数），形状均衡的树就是 B 树，广泛用于数据库索引。
小结
- 二叉查找树：左子树值都小，右子树值都大
- 查找、插入、删除平均 O(log n)，最糟 O(n)（退化为链表时）
- 是二分查找思想的树形体现
- 平衡二叉查找树（AVL、红黑树）解决了退化问题
- B 树是扩展版本，广泛用于数据库