二叉搜索树
二叉搜索树在每个节点维护同一规则：左子树所有值更小，右子树所有值更大。比较一次便能排除一侧，插入、搜索和删除都沿高度 h 的路径运行，时间为 O(h)。树保持平衡，或满足合适的随机输入假设时，平均为 O(log n)；普通 BST 不保证每次比较都排除一半。
猜数字时，“更大”或“更小”决定下一步。平衡的二分过程约二十次判断能覆盖一百万个候选。BST 把这种分支选择存成节点和指针，效果取决于树形。
二叉搜索树如何工作
三种操作都从根比较：小于当前值走左，大于走右，相等则命中。区别在路径结束后的动作。
insert(value) 走到空位置，再把新节点接为叶子，不调整上方结构。遇到相等值就停止，本实现不保存重复值。空树插入直接设置根。
search(value) 命中返回找到，走到 null 返回未找到。排序不变量保证被跳过的子树不可能包含目标。
delete(value) 找到目标后按子节点数处理：
- 没有子节点：让父节点指向它的引用变为 null。
- 一个子节点：让父节点跳过目标，直接接它的子节点；子树整体保留，仍满足相对父节点的顺序。
- 两个子节点：本课使用中序后继。先到右子树，再一路向左，取其中最小值。它大于目标左子树所有值，也小于右子树剩余值。把后继值复制到目标，再从右子树删除后继。后继没有左孩子，所以删除归结为叶子或单子节点情况。中序前驱也可对称实现，本课代码采用后继。
逐步演示
播放器从空树开始。依次插入 50, 30, 70, 20, 40, 60, 80。
insert(50)：空根，无需比较，50 成为根。insert(30)：30 < 50，向左接入。insert(70)对称地接到右侧。insert(20)：依次与 50、30 比较，向左两次。随后 40、60、80 各比较两次，分别接到 30 右侧、70 左侧、70 右侧。形成高度 2 的平衡树。search(40)：在 50 处走左，在 30 处走右，在 40 处相等。三次比较，在深度 2 找到。delete(20)：经 50、30 找到叶子 20，把 30 的左引用清空。delete(30)：此时 30 只有子节点 40。把 50 的左引用改为 40，再移出 30，40 上移。delete(50)：第一步命中根，根有两个子节点。向右到 70，再向左到 60。60 没有左孩子，是后继。复制 60 到根，再移除右子树中原来的叶子 60。
最终根为 60，左为 40，右为 70，70 的右侧为 80，每个节点仍满足排序规则。
画布的游标点亮比较路径，未访问子树保持淡色。插入前显示空位，删除分别展示剪除、旁路连接或后继搜索。后继与目标通过虚线关联，再执行复制和移除。
时间与空间复杂度
| 操作 | 平均，需相应形状或输入假设 | 最坏退化 |
|---|---|---|
| 搜索 | O(log n) | O(n) |
| 插入 | O(log n) | O(n) |
| 删除 | O(log n) | O(n) |
| 存储 | O(n) | O(n) |
普通 BST 不主动平衡。依次插入 1, 2, 3, 4, 5，每个新节点都接在前一个右侧，形成链。按边计高度为 n − 1，最坏操作 O(n)。AVL、红黑树和 treap 通过各自规则控制高度；例如 Java TreeMap 使用红黑树。
最大深度滑块 3–5 是画布布局限制。插入超出显示深度时，播放器说明原因；达到该深度可容纳的完美树节点上限后，插入按钮禁用。这不是 BST 的结构限制，实际树可以继续退化增长。
边界情况
- 空树：搜索立即未找到；插入创建根；删除不改变状态。
- 删除根：双子节点用后继；单子节点让孩子成为根。
- 重复插入：遇到相等值即停止。也可另设计数字段等策略，但同一棵树内必须一致。
- 删除缺失值：走到 null，树不变。
- 删除唯一节点：叶子情况，根变空。
常见错误
- 直接移除双子节点目标而不保留连接。 会丢失子树。本课先复制后继值，再移除后继；也可采用维护相同不变量的节点移植算法。
- 找错后继。 后继是右子树最左节点，不是任意附近叶子，也不是左子树节点。若使用前驱，要采用对称的完整算法。
- 有序输入却期待平衡。 普通插入会形成链。需要最坏界时使用自平衡树，随机顺序也不是最坏情况保证。
- 混淆 BST 与堆。 BST 的左右顺序支持有序遍历和范围查询；堆约束父子优先级，能 O(1) 查看极值，但数组并不有序。