二叉搜索树
二叉搜索树（BST）按键的大小组织子树。本文负责查找、验证、删除和有序查询，假设键互异。
本文使用树高和中序遍历分析操作。尚不熟悉这些概念时，先读二叉树。
1. 面试核心
先记住这几条，再读正文- 排序约束。 键互异时，BST 左子树的所有键都小于根，右子树的所有键都大于根。这个约束作用于整棵子树，验证时需传递祖先限定的范围。卡 · 查找与键范围
- 操作成本。 BST 查找、插入和删除均为 O(h)，h 为树高。
- 双孩子节点删除。 删除双孩子节点时，可用中序后继替代。后继满足当前位置的大小关系，且自身至多有一个右孩子，后续删除更简单。卡 · 双孩子节点与后继
- 高度控制。 平衡搜索树控制高度为 O(log n)，普通 BST 最坏高度为 n。
2. 查找与键范围
从根比较 target。相等就命中，更小则走左孩子，更大则走右孩子。空节点表示查找失败。每步沿一条边前进，成本为 O(h)。
验证需要传递祖先规定的上下界。例如根为 10，左孩子为 5，5 的右孩子为 12。12 满足直接父节点的条件，却越过了根规定的上界。左递归收紧上界，右递归收紧下界。初始边界可用可空值表示，避免整数极值加减溢出。
3. 插入与删除
插入沿查找路径找到空位置。顺序插入 1,2,3,4 会形成向右的链。普通 BST 的最坏查找为 O(n)。
删除叶子时，清除父节点对应链接。只有一个孩子时，让父节点改连该孩子。删除根时还需更新根引用。
3.1 双孩子节点与后继
双孩子节点可由右子树最小键接替。这个后继大于左子树的全部键。它也小于右子树的其他键，所以仍满足 BST 顺序。
后继位于右子树最左端，至多有一个右孩子。复制后继的键值后，删除原后继节点即可。若节点还保存关联数据，应一起复制。外部持有节点引用时，还需明确节点身份的变化。
3.2 前驱后继与范围查询
查找第一个不小于 target 的键时，保存候选节点。当前键足够大，就更新候选并向左搜索。当前键偏小时向右搜索。最终候选就是 lower bound，耗时 O(h)。
闭区间查询可按中序遍历，并跳过区间外的子树。输出 k 项的时间为 O(h+k)。维护子树大小后，可沿大小信息查找第 k 小值。
4. 使用边界
AVL 树和红黑树用旋转及平衡规则控制树高。范围查询需要键顺序。只做等值查询时，可比较哈希表的成本。
数据库索引还需考虑每次访问的页大小。相关结构见B+ 树。
5 · 面试题卡片
本页题目与参考回答
5.1 为何验证 BST 要传递祖先的键范围？
考察重点：子树范围、重复键与数值边界。
相关内容：查找与键范围。
参考回答
BST 约束作用于整棵子树，直接父子比较会遗漏祖先。
递归时传入上下界，并按当前键收紧边界。互异键要求严格大小关系。也可用中序遍历检查严格递增。
5.2 删除双孩子节点时，为何可用中序后继替代？
考察重点：后继的顺序条件与链接修复。
相关内容：双孩子节点与后继。
参考回答
后继大于全部左侧键，且小于右侧其他键。
替代后仍满足 BST 约束。后继至多有一个右孩子，删除时连接该孩子即可。查找和修复都沿树路径完成，时间为 O(h)。
5.3 BST 如何查找第一个不小于目标的键？
考察重点：候选记录与有序排除。
相关内容：前驱后继与范围查询。
参考回答
当前键足够大时，保存为候选并向左寻找更小合格键。
当前键偏小时向右走。走到空节点后返回最后候选，未记录候选则无解。沿单条路径搜索，时间为 O(h)。