删一个节点为什么要动两棵子树:二叉搜索树增删查的边界

二叉搜索树用一条区间约定把数据排成可二分的形状:左子树全小、右子树全大,查找沿一条路径比较,插入落在失败查找的终点,删除则要分叶子、单孩子、双孩子三种情况处理。它重要,是因为有序映射、范围查询与前驱后继都建立在这条约定上,而 TreeMap、std::map 的底层红黑树也只是它的平衡版本。最常见的误区是查找无脑答 O(log n)、校验只比较父子、删除双孩子节点时随便拿一个孩子顶替。读完你能写对三种删除情形,讲清中序后继为什么能接班,并判断什么时候该换平衡树或跳表。

是什么

二叉搜索树(BST)是每个节点都满足一条大小约定的二叉树:左子树里所有键都小于它,右子树里所有键都大于它。注意是“整棵子树”,不是“左右两个孩子”,这条差别几乎决定了后面所有 bug。

一句话直觉:它像一本按关键字排好序、可以从中任取一页翻开的字典,每次比较都能把待查范围砍掉一半。

典型场景:内存里的有序映射(Java 的 TreeMap、C++ 的 std::map,底层是红黑树,对外语义仍是 BST)、按区间取数据、找前驱与后继、排行榜的分数段查询,以及数据库 B+ 树索引的思想源头。它只保证“有序”,不保证“平衡”,而复杂度几乎全由后者决定。

核心原理

查找从根开始:键小往左、键大往右、相等命中;走到空说明不存在。比较次数等于根到目标的路径长度,也就是树高 h。平衡时 h 约为 log₂n,一百万节点大约比较 20 次;退化成一条链时 h = n,等于线性扫描。所以“BST 查找是 O(log n)”这句话省掉了一个关键前提。

插入的位置一定是一次失败查找的终点:沿同样的路径比较,遇到空位就把新节点挂上去,新节点必然是叶子。这意味着插入不改变已有节点的相对位置,树的形态完全由插入顺序决定。依次插入 1、2、3、4、5 会得到一条右斜链;按 5、3、8、1、4 插入才像一棵树。

同一条路径还能顺手回答“最接近的键是谁”:小于等于 key 的最大值(floor)和大于等于 key 的最小值(ceiling)。边走边记候选——key 比当前节点小时,当前节点可能是 ceiling,继续往左找更紧的;key 比当前节点大时,当前节点可能是 floor,继续往右。这个技巧也是范围查询能剪枝的原因。

删除分三种情况。叶子节点:把父节点对应的指针置空。只有一个孩子:让孩子顶替自己的位置,因为那棵子树里的所有键仍落在原节点的合法区间内。有两个孩子:不能随便挑一个孩子上来——左孩子可能比右子树的所有键都小,右孩子可能比左子树的所有键都大,直接顶替会破坏顺序。正确做法是找中序后继(右子树中最小者)或中序前驱(左子树中最大者),把它的键值搬到待删位置,再回头删掉那个后继节点。后继一定没有左孩子,于是问题退化成前两种情况。

def delete(root, key):
    if root is None:
        return None
    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    elif root.left is None:          # 0 个或只有右孩子
        return root.right
    elif root.right is None:         # 只有左孩子
        return root.left
    else:                            # 两个孩子:找中序后继
        succ = root.right
        while succ.left:
            succ = succ.left
        root.key, root.val = succ.key, succ.val
        root.right = delete(root.right, succ.key)
    return root

可以这样类比:从一排按身高站好的人里抽走一个,不是把后面所有人往左挪(那是数组),而是把“紧挨着的下一位”请到空位上;BST 里的“下一位”就是中序后继。搬的只是标签,位置关系不变。

为什么这样做是对的?BST 的合法性本质是一组区间约束。根的值把数轴分成两段,左子树只能落在 (-∞, root),右子树只能落在 (root, +∞),每往下一层区间继续收窄。后继恰好是这个区间里“最小的那个更大者”,让它接班,左右两侧的约束同时满足。反过来,校验一棵树是不是 BST 也必须带着上下界往下走,只比较父子会漏掉“孙子跑到叔叔那边”的情况。

删除的代价:找节点 O(h),找后继 O(h),所以删除也是 O(h)。但删除会改变形状——Hibbard 删除法在随机插入与大量删除交替进行时,树高的期望会从 log n 退化到大约 √n(经典分析见 Sedgewick 的教材与 Princeton 的课程讲义)。这正是标准库不用裸 BST,而用红黑树、AVL 或 B 树把 h 钉在 O(log n) 的原因。

常见考点与误区

  • 校验 BST 只比较父子:反例是根 10、右孩子 15、15 的左孩子 6。6 小于 15,却不在 (10, +∞) 区间里。正确写法是递归传上下界(用 None 表示无界,避免 INT_MIN 撞上真实最小值),或检查中序是否严格递增。面试追问“不用额外空间”时,答 Morris 中序或上下界递归。
  • 删除双孩子节点时直接返回左孩子或右孩子:另一棵子树会被整棵丢掉,节点数变少却不报错,是最隐蔽的一类 bug。必须用后继/前驱顶替,再递归删除后继。
  • 以为查找恒为 O(log n):有序数据顺序插入会退化成链表,复杂度变 O(n)。面试常追问“什么时候退化、怎么避免”,答案是随机化插入顺序、使用平衡树,或换跳表。
  • 后继找成“右孩子”:后继是右子树的最左节点,不是右孩子本身;前驱则是左子树的最右节点,方向对称。写错这一步,删除后中序就不再有序。
  • 重复键语义不清:插入时相等往右放,删除时却按唯一键处理,可能只删掉一个副本;用计数节点时又忘了计数减到零才摘链。工程上要先约定:拒绝、计数,还是允许重复并规定放哪一侧。
  • 把 BST 当成平衡树:BST 只是“有序”这条性质,平衡是额外约束。红黑树是 BST 的一种实现,反过来不成立;std::map 的 O(log n) 来自平衡,不来自“它是 BST”。

实践建议

  • 先写不变量测试:随机执行 insert/delete 后,中序必须严格递增、节点数要对得上;再用一个有序列表做影子模型对拍。删除的三种分支,靠肉眼很难覆盖全,随机对拍最省时间。
  • 生产环境别手写裸 BST:需要有序映射就用 TreeMap/std::map(红黑树),需要高并发读与范围扫描用跳表(Redis 的有序集合、LevelDB 的 memtable),需要落盘用 B+ 树。裸 BST 适合教学、面试,以及节点少且形状可控的场景。
  • 把重复键和空值语义写进接口:删除接口最好返回被删的值,调用方才能区分“本来就不存在”和“删成功”;允许重复时明确相等键放左还是放右,并在查找、删除里保持一致。
  • 范围查询与前驱后继顺路径剪枝:找 lower_bound 时记录“最后一个小于目标的节点”,一路走到空即可,不要中序全量扫。区间查询在节点区间与目标区间不相交时直接返回。
  • 递归要评估树高:h 可能等于 n,递归删除有栈溢出风险。生产代码用迭代版,或先确认树是平衡结构;给深度设上限并监控。
  • 删除频繁就监控树高:不要假设“删除不会让树变差”。Hibbard 删除会缓慢破坏平衡,定期重建或直接换平衡结构,比事后调参可靠。

一句话总结:BST 的增删查都只是在维护一条区间约定——查找靠比较,插入靠失败终点,删除靠后继接班;决定性能的从来不是节点数,而是树高。

相关阅读

← 返回文章志