数据结构笔记总结(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;
    }
}

源码下载

[dm href=’https://www.jikewenku.com/product/1487.html’]下载地址[/dm]

导航目录

[dm href=’https://www.jikewenku.com/geeknote/2241.html’]查看导航[/dm]

本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 数据结构笔记总结(5.12)删除二分搜索树的任意元素

Leave a Reply

欢迎加入「极客文库」,成为原创作者从这里开始!

立即加入 了解更多