二叉搜索树中的搜索

如果当成普通二叉树,你得挨个节点比对,最坏要看完全部 n 个节点。但这是搜索树,有序,完全用不着这么笨。

就像查字典:你不会从第一页翻到最后一页,而是看一眼当前页比目标大还是小,直接决定往前还是往后翻。BST 查找就是这个直觉。

盯住当前节点(橙色高亮的那个)和它跟 6 的大小关系:小了往右下、大了往左下,走过的路径会被点亮。

先看清这棵 BST：先认清结构:根 8 的左子树(蓝)1、3、6 全比 8 小,右子树(绿)10、14 全比 8 大。这条「左小右大」在每个节点都成立,正是查找能排除一整侧不可能子树的依据。

从根出发 · 当前 8：查找永远从根开始。当前节点是 8,把目标 6 和它比。

6 < 8 → 排除右子树：6 比 8 小。按「左小右大」,6 绝不可能在右边——右子树 10、14 整块作废(紫色标记),一次比较排除一整侧。

下移到左孩子 3：当前节点下移到 8 的左孩子 3。8 已访问(蓝),被排除的 10、14 保持作废标记。再拿 6 和 3 比。

6 > 3 → 排除左孩子 1：6 比 3 大,该往右。3 的左孩子 1 也被排除,又砍掉一块。

下移到右孩子 6：当前节点来到 3 的右孩子 6。已经把整棵树砍得只剩这一条路了。

6 == 6 → 命中!：当前节点的值正好等于 6,命中(绿色)!整棵 7 个节点的树,我们只比较了 3 次(8 → 3 → 6),其余节点看都没看。返回这个节点连同它的子树。

命中很爽,但找不到的情况也要会处理。同一套规则,找一个树里没有的 5。

找 5 · 从根 8 出发：重新从根 8 开始查找,这次目标换成 5,看它最后怎么走到空。

5 < 8 → 走左边：5 比 8 小,和找 6 那次一样往左走,右子树作废,当前节点下移到 3。

5 > 3 → 排除左孩子 1：5 比 3 大,和找 6 时一样该往右走,3 的左孩子节点 1 被排除作废。

下移到 6：当前节点移动到 3 的右孩子 6,继续拿它和目标 5 比。

5 != 6 → 还要继续：当前到了 6,但 6 ≠ 5,还没结束。5 比 6 小,按规则该往 6 的左孩子走。

5 < 6 → 走左边 → 空：可 6 根本没有左孩子,下一步是空节点。走到空就说明:这棵树里没有 5,返回空。这正是查找的终止条件。

对比:链表式遍历会怎样：如果无视「左小右大」、把它当普通二叉树遍历,你得把所有节点都比一遍(O(n))。BST 查找之所以快,全靠每一步用大小关系扔掉一整侧不可能的子树。下面用一行数组把两者的差距摆出来。

笨办法:线性扫描：把 6 个节点摊成一排,线性查找就是指针从左到右一个个比。最坏(目标在末尾或不存在)要比完全部 6 个。

笨办法 · 比第 2 个：第 1 个 1 不对,指针前移到 3。线性查找老老实实一个个挪,不会跳。

笨办法 · 扫到第 4 个：指针挪到第 4 个 8,前面 1、3、6 都白比了。线性查找不会「跳过」任何元素。

笨办法 · 一直扫到末尾：最坏情况指针一路扫到最后的 14,前面全比过——这就是 O(n)。元素越多越慢。

BST 查找:只碰 3 个：而走 BST 找 6,只碰了 8、3、6 三个(高亮),其余灰格连看都没看。树越大,这个差距越夸张——这就是「有序 + 每步排除一整侧」的威力。

复盘命中路径：回看命中那条路径:8 → 3 → 6,从根到目标一条线。比较次数 = 走过的层数 = 树高。树越平衡,树高越低(O(log n))。

它和有序数组上的二分查找思路相通:二分每次稳稳砍掉一半,BST 砍掉的是一整侧子树——只有树平衡时才接近一半。想通这点,「二叉搜索树为什么快、又为什么会变慢」就再不神秘。

雷区实演 · 方向写反：若把方向写反:6 比 8 小本该往左,却跑到右边的 10。这条路上全是比 8 大的数,永远碰不到 6。记牢:小往左、大往右。

边界三连：三种边界都被同一个 while 条件 root && root.val != val 自然兜住,不用单独写 if。

面试追问：迭代 vs 递归、O(h) 的严谨性、如何保持平衡,是这题往深里问的三个方向。