数据结构与算法 / 系统课时
二叉搜索树查找
二叉搜索树查找
二叉搜索树把大小关系编码进树结构,使查找不必访问全部节点。本课将围绕搜索树不变式,实现键值查找、最小值和最大值操作,并分析树形是否平衡对性能的直接影响。
在一条路径内找键
- 理解二叉搜索树的有序不变式及其边界条件。
- 实现迭代查找、最小值和最大值操作。
- 根据树高判断操作的时间与空间复杂度。
有序不变式与可选分支
二叉搜索树查找
├── 有序不变式
│ ├── 左子树键值小于当前节点
│ └── 右子树键值大于当前节点
├── 查找
│ ├── 相等:返回当前节点
│ ├── 更小:进入左子树
│ └── 更大:进入右子树
└── 极值
├── 最小值:沿左链到底
└── 最大值:沿右链到底
查找时何时能舍弃一整侧
在线集合、内存索引和符号表经常需要执行“是否存在某个键”“当前最小键是什么”“当前最大键是什么”等操作。普通二叉树没有大小约束,最坏情况下必须遍历全部节点;二叉搜索树通过有序不变式,在每次比较后排除一侧子树。
查找性能取决于树高而不是节点总数本身。平衡良好的树高约为 ,查找接近二分搜索;若数据按升序插入且没有平衡机制,树会退化为单链,性能下降到线性级别。
将目标与当前键比较
本课采用“键值唯一”的二叉搜索树定义。对任意节点 node,其左子树所有键都小于 node.key,右子树所有键都大于 node.key。这个规则必须对每一棵子树递归成立,而不只是比较父节点与直接孩子。
查找目标 target 时有三种结果:等于当前键则成功;小于当前键则只可能出现在左子树;大于当前键则只可能出现在右子树。每次比较都会把问题缩小到一个子树,因此访问节点数最多等于树高。
| 操作 | 移动方向 | 时间复杂度 | 迭代额外空间 |
|---|---|---|---|
| 查找 | 根据比较结果向左或向右 | ||
| 最小值 | 持续沿左孩子移动 | ||
| 最大值 | 持续沿右孩子移动 |
空树没有最小值和最大值,接口必须明确返回空结果或抛出异常。重复键也要预先约定处理规则,例如拒绝插入、计数或固定放到某一侧;若规则不统一,搜索树不变式会变得含糊。
查找终点、最小值与最大值
迭代查找只需要一个 current 指针。循环中先比较目标值与当前节点键值,再决定进入左子树还是右子树;当 current 变为 null 时,说明搜索路径已经结束且目标不存在。
最小值操作不需要比较目标,只需从根节点开始沿 left 指针移动,直到左孩子为空;最大值对称地沿 right 指针移动。三种操作都不会修改树结构,因此适合定义为只读查询。
检查搜索树是否有效时,不能只验证每个节点与直接孩子的关系。例如,某个值可能小于根节点,却错误地出现在根节点的右子树深处。严格验证需要为每个子树维护允许的上下界。
实现可观测的搜索路径
将以下代码保存为 BinarySearchTreeLookupDemo.java。程序通过插入固定数据构造搜索树,然后执行两次查找以及最小值、最大值查询。
public class BinarySearchTreeLookupDemo {
static class Node {
final int key;
Node left;
Node right;
Node(int key) {
this.key = key;
}
}
static class BinarySearchTree {
private Node root;
void insert(int key) {
if (root == null) {
root = new Node(key);
return;
}
Node current = root;
while (true) {
if (key == current.key) {
return;
}
if (key < current.key) {
if (current.left == null) {
current.left = new Node(key);
return;
}
current = current.left;
} else {
if (current.right == null) {
current.right = new Node(key);
return;
}
current = current.right;
}
}
}
Node search(int target) {
Node current = root;
// 每次比较后只保留可能包含目标的一侧子树。
while (current != null) {
if (target == current.key) {
return current;
}
current = target < current.key ? current.left : current.right;
}
return null;
}
int min() {
ensureNotEmpty();
Node current = root;
while (current.left != null) {
current = current.left;
}
return current.key;
}
int max() {
ensureNotEmpty();
Node current = root;
while (current.right != null) {
current = current.right;
}
return current.key;
}
private void ensureNotEmpty() {
if (root == null) {
throw new IllegalStateException("树为空,不存在最小值或最大值");
}
}
}
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
int[] keys = {8, 3, 10, 2, 6, 14, 13, 20};
for (int key : keys) {
tree.insert(key);
}
System.out.println("查找 13: " + (tree.search(13) != null ? "找到" : "未找到"));
System.out.println("查找 7: " + (tree.search(7) != null ? "找到" : "未找到"));
System.out.println("最小值: " + tree.min());
System.out.println("最大值: " + tree.max());
}
}运行命令:
javac BinarySearchTreeLookupDemo.java
java BinarySearchTreeLookupDemo验证命中与未命中的结果
查找 13: 找到
查找 7: 未找到
最小值: 2
最大值: 20查找 13 的访问路径是 8 → 10 → 14 → 13,查找 7 的路径是 8 → 3 → 6,随后进入空的右子树并结束。最小值沿左链到达 2,最大值沿右链到达 20。
树形改变查找成本
按升序把同一组键逐个插入一棵普通二叉搜索树,会形成向右的链。查找最大值将经过所有节点。再以中位键开始组织近似平衡的树,同一个最大值仍能找到,但经过的节点更少。测试时记录访问路径长度,可以直接比较树形,而不必依靠耗时推断。
- 将比较逻辑集中在一个位置,避免查找、插入和删除各自采用不同的重复键规则。
- 调试时打印访问路径,比只打印“找到或未找到”更容易发现左右方向写反的问题。
- 接口需要表达“可能不存在”时,可以返回
Node、OptionalInt或布尔值;不要用一个可能与合法键冲突的特殊整数表示失败。 - 大量有序数据会使普通二叉搜索树退化。工程中需要稳定的对数性能时,应使用 AVL 树、红黑树或标准库中的平衡搜索树实现。
重复键与空子树的边界
只比较目标与根节点,然后转为普通遍历,会失去搜索树剪枝的意义。正确做法是在每个访问节点上重新比较,并始终只进入一侧子树。
寻找最小值时若判断 current != null 后继续移动并在循环结束时访问 current.key,最终可能得到 null 并触发异常。应判断 current.left != null,让循环结束时 current 保持在最左节点。
把重复键有时放左侧、有时放右侧,会使查找和删除无法遵循统一规则。本示例选择跳过重复插入;实际系统也可以保存计数,但必须在所有操作中保持一致。
验证祖先范围和 floor
- 为
search增加路径记录,返回访问过的键值列表。输入目标13时,验收结果为[8, 10, 14, 13]。 - 增加
floor(int target),返回不大于目标值的最大键。输入target = 12时应返回10,输入target = 1时应明确表示不存在。 - 编写搜索树合法性检查,使用上下界验证整棵树。验收条件是能够识别“某个深层节点违反祖先约束”的错误结构,而不只检查父子关系。
搜索路径的验收条件
- 二叉搜索树通过左小右大的递归不变式,把查找限制在一条根到叶的路径上。
- 查找、最小值和最大值的时间复杂度都是 ,平衡程度决定实际性能。
- 空树、重复键和退化树是实现接口时必须明确处理的边界情况。
从查询转向插入与删除
接下来将继续学习二叉搜索树的更新操作,重点关注插入或删除节点后如何维持有序不变式,并分析不同树形对性能的影响。