数据结构与算法 / 系统课时

二叉搜索树查找

二叉搜索树查找

二叉搜索树把大小关系编码进树结构,使查找不必访问全部节点。本课将围绕搜索树不变式,实现键值查找、最小值和最大值操作,并分析树形是否平衡对性能的直接影响。

在一条路径内找键

  • 理解二叉搜索树的有序不变式及其边界条件。
  • 实现迭代查找、最小值和最大值操作。
  • 根据树高判断操作的时间与空间复杂度。

有序不变式与可选分支

text
二叉搜索树查找
├── 有序不变式
│   ├── 左子树键值小于当前节点
│   └── 右子树键值大于当前节点
├── 查找
│   ├── 相等:返回当前节点
│   ├── 更小:进入左子树
│   └── 更大:进入右子树
└── 极值
    ├── 最小值:沿左链到底
    └── 最大值:沿右链到底

二叉搜索树查找与极值路径

查找时何时能舍弃一整侧

在线集合、内存索引和符号表经常需要执行“是否存在某个键”“当前最小键是什么”“当前最大键是什么”等操作。普通二叉树没有大小约束,最坏情况下必须遍历全部节点;二叉搜索树通过有序不变式,在每次比较后排除一侧子树。

查找性能取决于树高而不是节点总数本身。平衡良好的树高约为 log⁡2n\log_2 n,查找接近二分搜索;若数据按升序插入且没有平衡机制,树会退化为单链,性能下降到线性级别。

将目标与当前键比较

本课采用“键值唯一”的二叉搜索树定义。对任意节点 node,其左子树所有键都小于 node.key,右子树所有键都大于 node.key。这个规则必须对每一棵子树递归成立,而不只是比较父节点与直接孩子。

查找目标 target 时有三种结果:等于当前键则成功;小于当前键则只可能出现在左子树;大于当前键则只可能出现在右子树。每次比较都会把问题缩小到一个子树,因此访问节点数最多等于树高。

操作 移动方向 时间复杂度 迭代额外空间
查找 根据比较结果向左或向右 O(h)O(h) O(1)O(1)
最小值 持续沿左孩子移动 O(h)O(h) O(1)O(1)
最大值 持续沿右孩子移动 O(h)O(h) O(1)O(1)

空树没有最小值和最大值,接口必须明确返回空结果或抛出异常。重复键也要预先约定处理规则,例如拒绝插入、计数或固定放到某一侧;若规则不统一,搜索树不变式会变得含糊。

查找终点、最小值与最大值

迭代查找只需要一个 current 指针。循环中先比较目标值与当前节点键值,再决定进入左子树还是右子树;当 current 变为 null 时,说明搜索路径已经结束且目标不存在。

最小值操作不需要比较目标,只需从根节点开始沿 left 指针移动,直到左孩子为空;最大值对称地沿 right 指针移动。三种操作都不会修改树结构,因此适合定义为只读查询。

检查搜索树是否有效时,不能只验证每个节点与直接孩子的关系。例如,某个值可能小于根节点,却错误地出现在根节点的右子树深处。严格验证需要为每个子树维护允许的上下界。

实现可观测的搜索路径

将以下代码保存为 BinarySearchTreeLookupDemo.java。程序通过插入固定数据构造搜索树,然后执行两次查找以及最小值、最大值查询。

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());
    }
}

运行命令:

bash
javac BinarySearchTreeLookupDemo.java
java BinarySearchTreeLookupDemo

验证命中与未命中的结果

text
查找 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

  1. 为 search 增加路径记录,返回访问过的键值列表。输入目标 13 时,验收结果为 [8, 10, 14, 13]。
  2. 增加 floor(int target),返回不大于目标值的最大键。输入 target = 12 时应返回 10,输入 target = 1 时应明确表示不存在。
  3. 编写搜索树合法性检查,使用上下界验证整棵树。验收条件是能够识别“某个深层节点违反祖先约束”的错误结构,而不只检查父子关系。

搜索路径的验收条件

  • 二叉搜索树通过左小右大的递归不变式,把查找限制在一条根到叶的路径上。
  • 查找、最小值和最大值的时间复杂度都是 O(h)O(h),平衡程度决定实际性能。
  • 空树、重复键和退化树是实现接口时必须明确处理的边界情况。

从查询转向插入与删除

接下来将继续学习二叉搜索树的更新操作,重点关注插入或删除节点后如何维持有序不变式,并分析不同树形对性能的影响。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

二叉搜索树查找

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通