二叉搜索树Binary search tree

按键的大小关系把记录放在左右子树。

一棵平衡的二叉搜索树示例；普通二叉树不必满足键序。

常见操作#

n 为节点数，h 为树高，k 为输出的键数。

操作	时间复杂度	条件与说明
查找 / 插入 / 删除	$O(h)$	不带平衡约束；最坏 h 可达 n。
最小 / 最大 / 前驱 / 后继	$O(h)$	从根搜索或沿父子链移动；额外缓存可优化特定接口。
有序遍历	$O(n)$	中序遍历；递归辅助栈为 $O(h)$ 。
范围枚举	$O(h+k)$	先定位范围边界，再有序访问匹配节点。
从有序数组平衡构建	$O(n)$	递归选择中点；这只保证初始形态，后续更新仍可能使树退化。

随机插入顺序的平均表现依赖概率模型，不作为任意输入的保证。

基础原理参考资料

Princeton · BST普通二叉搜索树的操作、最坏线性时间与有序接口。