二叉搜索树
二叉搜索树（BST）利用键的大小关系剪去不可能的子树，用于有序查找与范围查询。本文假设键互异；重复键必须另行约定计数或存放方式。
1. 面试核心
先记住这几条，再读正文- 每个节点左子树的所有键更小，右子树的所有键更大。
- 查找、插入和删除通常为 O(h)，普通 BST 最坏可退化为 O(n)。
- 中序遍历得到升序序列，平衡搜索树通过额外规则控制树高。
2. 查找时排除一棵子树
从根查找 target：相等就命中；target 更小时走左孩子，否则走右孩子。走到空节点表示不存在。每一步只沿一条路径，成本由树高决定。
验证 BST 时，不能只比较一个节点与直接孩子。例如根 10 的左孩子是 5，5 的右孩子是 12，局部父子关系正确，但 12 违反了根的左子树上界。递归验证必须把祖先确定的上下界向下传递。
3. 插入与删除
插入沿查找路径找到空位置。若依次插入 1,2,3,4，会形成向右的链，说明普通 BST 不保证 O(log n)。
删除分三种情况：叶子直接移除；只有一个孩子时用孩子接替；有两个孩子时，可用右子树最小键作为后继替代当前键，再删除原后继节点。后继没有左孩子，后一次删除因此更简单。若外部持有节点引用，还应明确替换的是键还是节点身份。
4. 使用边界
有序遍历、前驱后继和范围查找适合搜索树。只要等值查询时，可以比较哈希表的平均成本与顺序需求。
AVL 树、红黑树通过旋转及平衡规则维持 O(log n) 高度，但会增加维护成本。数据库的磁盘索引通常需要减少页访问，进一步使用B+ 树，不能直接把内存 BST 的节点结构搬到磁盘上。
5 · 面试题卡片
先想答案，再翻面题目来自公开面经。点任意一张进入翻卡，可左右切换，看完回到这里。
逐张翻看 1 张 →5.1 为什么验证二叉搜索树不能只比较每个节点和它的直接孩子？
出现公司：暂无已核验的公开来源（本站自测）
考察重点：整棵子树的键范围、祖先约束的传递与重复键策略。
参考回答
BST 要求整棵左子树都小于当前键、整棵右子树都大于当前键，局部检查遗漏祖先约束。验证时传入允许的上下界，左孩子收紧上界、右孩子收紧下界；也可以中序遍历检查严格递增。重复键策略必须先约定，边界值应避免靠加一或减一制造溢出。