形式陈述

二叉搜索树（BST）是一棵每个结点含有键的二叉树，并满足：对结点 $x$，左子树中键均小于 $x.key$，右子树中键均大于 $x.key$；重复键需由实现另定一致策略。搜索、插入、删除沿根到叶的一条路径进行，时间为 $O(h)$，其中 $h$ 是树高。中序遍历按非降序输出全部键。普通 BST 不保证平衡，最坏可有 $h=n-1$。

直觉

每个比较把剩余候选键分到左或右子树；树形是否均衡决定一次比较能排除多少候选。

例子与边界

按随机顺序插入常得到较低树高，但按递增顺序插入 1,2,...,n 会退化成链。删除有两个孩子的结点时，可用后继或前驱替换再删除。AVL、红黑树等通过旋转维持 $O(\log n)$ 高度；普通 BST 本身没有这一保证。BST 的形状与键插入顺序有关，且不是数组上的二分查找。

推论与应用

BST 支持有序字典、范围查询、前驱后继和顺序统计扩展。平衡版本在最坏情况下给对数复杂度，外存场景则推广为 B 树族。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Chs. 12–13, binary search trees and balancing context。
• Robert Sedgewick and Kevin Wayne, Algorithms, 4th ed., Addison-Wesley, 2011，§3.2, binary search trees。