• 新版网站前后台即将上线,2019年将致力于提高文章质量,加大原创力度,打造一个更加舒适的阅读体验!
  • 极客文库小编@勤劳的小蚂蚁,为您推荐每日资讯,欢迎关注!
  • 新版网站前后台即将上线,2019年将致力于提高文章质量,加大原创力度,打造一个更加舒适的阅读体验!
  • 如果有任何体验不佳的地方,欢迎向客服反馈!

数据结构笔记总结(5.12)删除二分搜索树的任意元素

文章目录[隐藏]

删除只有左孩子的节点


比如图中要删除 58,只需将 58 删除,然后用其左孩子所在的二叉树也就是左子树来取代它的位置,连在它原来父亲节点的右孩子的位置。

删除只有右孩子的节点


同理,将 58 删除,然后用其右孩子所在的二叉树也就是右子树来取代它的位置,连在它原来父亲节点的右孩子的位置。

删除左右都有孩子的节点

比较难的是删除左右都有孩子的节点,比如图中的 58,该怎么删除呢?

首先给 58 取一个名字叫 d,d 既有左孩子又有右孩子,这种情况下删除它后就不能简单的用左子树或右子树代替它的位置,要有机的把 d 的左右子树的节点融合起来。

根据二分搜索树的定义,左子树的节点都小于这个节点,右子树上所有的值都大于 d 节点,所以我们应该找一个节点提到 d 的位置,那我们该找哪个节点呢?

在这里我们找的是 58 的后继,也就是所有的这些元素中,离 58 最近的比 58 还大的节点,也就是 59,那么这个 59 是怎么找到的呢?

其实就是 58 的右子树中对应的最小的节点,因为 58 的右子树中所有节点都比 58 大,那么右子树中最小的节点就是比 58 大且最近的元素。

我们把 59 标记为 s,s 是 d 的后继。此时我们要在 d 的右子树中删除这个最小值,删除最小值后,剩下的这颗子树让它成为我们刚刚找到的 d 的后继,也就是 s 节点的右子树,其实就变成了这个样子。

下面要做的就是让 s 的 left(左子树)等于 d 的左子树,如图所示,现在就可以删除 d 了,s 就变成了新的子树的根。

最终就完成了删除,结果如下图所示

代码演示

// 从二分搜索树中删除元素为 e 的节点
public void remove(E e){
    root = remove(root, e);
}

// 删除掉以 node 为根的二分搜索树中值为 e 的节点, 递归算法
// 返回删除节点后新的二分搜索树的根
private Node remove(Node node, E e){

    if( node == null )
        return null;

    if( e.compareTo(node.e) < 0 ){
        node.left = remove(node.left , e);
        return node;
    }
    else if(e.compareTo(node.e) > 0 ){
        node.right = remove(node.right, e);
        return node;
    }
    else{   // e.compareTo(node.e) == 0

        // 待删除节点左子树为空的情况
        if(node.left == null){
            Node rightNode = node.right;
            node.right = null;
            size --;
            return rightNode;
        }

        // 待删除节点右子树为空的情况
        if(node.right == null){
            Node leftNode = node.left;
            node.left = null;
            size --;
            return leftNode;
        }

        // 待删除节点左右子树均不为空的情况

        // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
        // 用这个节点顶替待删除节点的位置
        Node successor = minimum(node.right);
        successor.right = removeMin(node.right);
        successor.left = node.left;

        node.left = node.right = null;

        return successor;
    }
}

源码下载

下载地址

导航目录

查看导航
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构笔记总结(5.12)删除二分搜索树的任意元素
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

欢迎 注册账号 登录 发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00