元数据卡
- 前置知识：二叉树基础（上一页）
- 预计时间：8 分钟
BST 的查找过程
python
def search_bst(root, target):
"""在 BST 中查找 target。每次比较减少一半的搜索空间。"""
current = root
while current:
if current.val == target:
return current
elif target < current.val:
current = current.left
else:
current = current.right
return None这和二分查找异曲同工——每次排除一半的节点。这就是 BST 能实现 O(log n) 查找的原因。
为什么 BST 可能退化成 O(n)
python
# 按顺序插入 1, 2, 3, 4, 5
# 树长这样（只有右子树，等于链表）：
# 1
# \
# 2
# \
# 3
# \
# 4
# \
# 5这就是退化的 BST——查找 5 需要 O(n)。解决方案：平衡树（红黑树、AVL），强制树的高度不超过 O(log n)。Java 的 TreeMap 和 TreeSet 底层就是红黑树。
BST vs 哈希表
| 操作 | BST | 哈希表 |
|---|---|---|
| 查找 | O(log n) | O(1) |
| 范围查询 | O(k + log n) ✅ | O(n) ❌ |
| 有序遍历 | O(n) ✅ | 不支持 ❌ |
| 插入/删除 | O(log n) | O(1) |
哈希表适合精确查找。BST 适合需要顺序的场景——比如"找出所有价格在 100-200 之间的商品"。
旅人笔记
BST 的查找效率依赖树的平衡程度。最差 O(n)，平均 O(log n)。优点是支持范围查询和有序遍历——哈希表做不到。实际工程中用红黑树保证平衡。
→ 下一步：堆与优先队列
如果我把数据放进一个容器，然后每次只想拿"最大"或"最小"的那个——不关心其他元素——那该多好？