• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

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

极客笔记 Geekerstar 11个月前 (05-17) 360次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

删除只有左孩子的节点


比如图中要删除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