为什么二分查找时间复杂度为logN而BST查找复杂度为N？

Robert Sedgewick在《Algorithms（第4版）》中给出的算法时间复杂度对照表如下：

首先需要明确一个容易被忽略的前提：表中标注的BST查找复杂度O(N)，指的是最坏情况复杂度，而非平均情况。普通BST的平均查找复杂度确实是O(logN)，但它无法保证所有场景下都能达到这个效率，这也是它和二分查找的核心区别。

核心差异拆解 #

你之所以会有「BST查找过程也是不断对半拆分检索范围，为什么复杂度不是logN」的疑惑，核心是把「理想场景下的表现」和「结构本身强制兜底的表现」等同了：

• 二分查找的对半拆分是静态有序数组结构强制保证的。二分查找操作的是连续存储的有序数组，每次可以O(1)直接访问当前搜索区间的中点，只要数组整体有序，不管元素具体怎么分布，每次比较后都能直接排除一半的元素，搜索空间严格逐次折半，因此哪怕是最坏情况，时间复杂度也稳定在O(logN)。
• 普通BST的对半拆分没有任何机制做强制约束。BST是动态链式结构，仅要求满足「左子树节点值 < 根节点值 < 右子树节点值」的基本性质，完全不限制左右子树的大小差。如果插入BST的元素本身按升序或降序排列，最终生成的BST会直接退化成单链表——比如依次插入1、2、3、4、5，根节点为1，右孩子是2，2的右孩子是3，以此类推。这时候查找值为5的节点，需要从根开始遍历全部5个节点，每次搜索范围仅缩小1个节点，根本不存在折半效果，最坏情况下时间复杂度自然是O(N)。

你认知里「每次对半拆分搜索范围」的树结构，其实是加了平衡约束的BST变种，比如AVL树、红黑树。这类平衡二叉搜索树会通过旋转等操作，强制保证左右子树的高度差在可控范围内，才能做到最坏情况查找复杂度稳定在O(logN)，已经不属于教材里定义的无平衡约束的基础BST范畴。

内容的提问来源于stack exchange，提问作者user19318020