【算法剖析】二叉排序树的删除

前言

网上的很多博客稂莠不齐，讲的也是参差不齐。看了排名靠前的几篇博客，大概都存在没有把各种情况分析完全的问题，虽然有代码，但还是看的不明不白。

于是我就参考了黑皮书《算法导论（第三版）》做个笔记。同时，对比了与国内教材的不同。

二叉排序树的删除

二叉排序树，又称为二叉搜索树，设为 T ，删除结点 z 可分为三种大情况：

• z 为叶子结点，直接删除。类似下图：

  

• z 只有左孩子或者右孩子，直接删掉，让其孩子代替。类似下图：

  

• z 同时拥有左孩子和右孩子，那么就要找到 z 的直接后继 y （相对于中序遍历），y 肯定在 z 的右子树中，并且没有左孩子（中序遍历的特点）。根据 y 又分两种情况：

  • y 直接是 z 的右孩子，并且 y 无左孩子 ，直接将后继结点 y 顶替 z。类似下图：

    

  • 否则的话，y 位于 z 的右子树，但是不是右孩子。先用 y 的右孩子 x 代替 y，然后再用 y 顶替 z（可能就这稍微复杂一点）。类似下图：

    

后序

有趣的是，我在参考 黑皮书《算法导论（第三版）》 的同时，也看了 黑皮书《数据结构与算法分析（Java语言描述）（第三版）》，这两本教材对二叉排序树的第三种删除方式是一样的，只考虑删除结点 z 的直接后继结点。

国内的话，科班出身一般都是从 清华大学严蔚敏老师的《数据结构（C语言版）》 学习到这部分。严老师对于二叉排序树的第三种删除方式与上述有些差异，主要是考虑了 删除结点 z 的直接前驱结点，国内很多博客也都是围绕这种思路。其实两种方法的考虑点基本是相同的，结果都是可以的。

思路：

• z 同时拥有左孩子和右孩子，那么就要找到 z 的直接前驱 y （相对于中序遍历），y 肯定在 z 的左子树中（中序遍历的特点）。根据 y 又分两种情况：

  • y 没有右孩子，直接将 y 顶替 z，y 的左孩子顶替 y。

  • y 有右孩子 x，直接将 x 顶替 z。

这种方法是严老师在书中介绍的第二种方法，还有第一种方法就不再提了，不太常见，感兴趣可以去书中看看。

后续实现代码版。