二叉搜索树 (Binary Search Tree, BST) 是一棵满足下面性质的二叉树：
对每个节点：左子树所有值 < 它，右子树所有值 > 它。
这条不变量带来两个直接结论：
- 中序遍历就是有序序列（从小到大）
- 查找/插入/删除都可以沿着比较结果”二分”地往下走，平衡时是 O(log n)
插入：走到 null 处挂上
Node* insert(Node* t, int v) {
if (!t) return new Node{v};
if (v < t->v) t->l = insert(t->l, v);
else if (v > t->v) t->r = insert(t->r, v);
return t;
}边比较边走，直到走到 null —— 新节点就挂在那里。插入顺序决定形状：顺序插入 1,2,3,4 会得到一条链，退化成链表。
查找：相同的走法，看终点
while (t && t->v != v)
t = (v < t->v) ? t->l : t->r;走到 null 就是没找到，走到值相等的节点就是命中。
删除：三种情况
最有意思的部分。设要删的节点是 t：
1. 叶子节点：直接摘掉。
2. 只有一个子：让子节点顶替自己的位置。
3. 两个子节点：找中序后继 —— 即右子树中的最小值（一路 ->left 走到底）。
- 把后继的值复制到
t上 - 删除原来的后继节点（它本身最多只有右子，转化成情况 1 或 2）
也可以用中序前驱（左子树最大值），对称等价。
复杂度
- 平均：O(log n)（随机插入，期望树高为 O(log n)）
- 最坏：O(n)（顺序插入退化成链表）
要保证最坏 O(log n)，需要自平衡树（红黑树、AVL、Splay）。BST 是它们的起点。
在动画里看什么
- 蓝色高亮：当前正在比较的节点
- 浅蓝路径：本次操作走过的整条路径
- 紫色：两子删除时找到的”中序后继”
- 绿色：search 命中
- 暖红色：即将被删除的节点
- 注意两子删除时，被删节点本身不消失，它的值被后继的值”顶替”了；真正消失的是后继节点