5.4删除二叉搜索树的任意元素

一.删除思路分析

在删除二叉搜索树的任意元素时,会有三种情况:

1.1 删除只有左孩子的节点

节点删除之后,将左孩子所在的二叉树取代其位置;连在原来节点父亲元素右节点的位置,比如在图中需要删除58这个节点。

删除58这个节点后,如下图所示:

1.2 删除只有右孩子的节点:

节点删除之后,将右孩子所在的二叉树取代其位置;连在原来节点的位置,比如在下图中需要删除58这个节点。

删除58这个节点后,如下图所示:

这里需要说明说一下,以上两种情况其实包含了叶子节点情况的,我们可以把叶子节点理解成只有左孩子的节点,也可以把它理解为只有右孩子的节点,只不过左孩子、右孩子为null

1.3 删除包含左右孩子的节点

如下图,二叉搜索树包含有左右孩子,假设现需要删除58这个节点。

针对该种情况,分析如下: 我们把58这个节点记为d节点(包含有左子树与右子树),如下图所示:

针对这种节点删除情况需要把左子树与右子树融合起来,融合方法: 从d这节点的左孩子与右孩子中找一个比d节点还要大的节点取代d节点,根据二叉搜索树的性质可知(左边节点<当前节点<右边节点),这个需要被找的节点存在于d节点的右孩子节点中。

寻找规则: 寻找需要被删除节点58(d)的后继的所有元素中,离 58 最近的且比 58 大的节点,在本例中为59这个节点【即右子树中的最小值】,记为s,如下图所示:

删除步骤:

(1)从d的右子树中删除最小值,将删除最小值s后的d的右子树, 变为d后继节点s的右孩子,如下图所示:

(2)将d节点(58节点)的左子树,变为后继节点s(59节点)的左子树,如下图所示:

(3)将后继节点s59节点)连接到d节点(58节点)父亲节点的右边,删除d节点(58节点)后,后继s节点(59节点)成为新的根,如下图所示:

二、编码实现二叉搜索树的任意元素

根据上述的分析,在此基础上进行编码,删除代码如下:

//从二叉搜索树中删除元素为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) {//e<node.e (被删除元素e小于当前节点值e)
            node.left = remove(node.left, e);
            return node;
        }
        if (e.compareTo(node.e) > 0) {//e>node.e (被删除元素e大于当前节点值e)
            node.right = remove(node.right, e);
            return node;
        } else {//e==node.e (被删除元素e等于当前节点值e)

            //待删除节点左子树为空情况
            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;
        }
    }

对于上述代码中的minimum函数,在5.3节中已经实现,此处同样也把代码列出来:

// 寻找二分搜索树的最小元素
    public E minimum() {
        if (size == 0) {
            throw new IllegalArgumentException("BST is empty");
        }

        Node ninNode = minimum(root);
        return ninNode.e;
    }

    // 返回以node为根的二分搜索树的最小值所在的节点
    private Node minimum(Node node) {
        if (node.left == null) {
            return node;
        }

        //返回相应的节点的左子树的最小值
        return minimum(node.left);
    }

源码地址 https://github.com/FelixBin/dataStructure/blob/master/src/BST/BST.java

推荐是最好的支持,关注是最大的鼓励。亲爱的朋友,很荣幸在园子里遇到您。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Rude3Knife的后端开发专栏

[Leetcode][python]二叉树的直径

https://leetcode-cn.com/problems/diameter-of-binary-tree/description/

13210
来自专栏Rude3Knife的后端开发专栏

[Leetcode][链表]相关题目汇总/分析/总结

16430
来自专栏Rude3Knife的后端开发专栏

[Leetcode][python]Flatten Binary Tree to Linked List/二叉树展开为链表

把一棵二叉树变为链表(扁平化),也就是一棵所有节点要么没有子节点,要么只有右节点的二叉树。

9510
来自专栏Rude3Knife的后端开发专栏

[Leetcode][python]从前序与中序遍历序列构造二叉树/从中序与后序遍历序列构造二叉树

根据二叉树的前序遍历和中序遍历( 中序和后序)结果生成二叉树 假设没有重复数字

16220
来自专栏Rude3Knife的后端开发专栏

[Leetcode][python]Populating Next Right Pointers in Each Node I and II/填充同一层的兄弟节点

为二叉树的节点都添加一个next指针,指向跟它在同一高度的右边的节点,如果右边没有节点,就指向None。

10120
来自专栏Rude3Knife的后端开发专栏

【Leetcode】【python】Hamming Distance, Merge Two Binary Trees

两个整数的汉明距离是指其二进制不相等的位的个数。 给定两个整数x和y,计算汉明距离。 注意: 0 ≤ x, y < 2^31.

9020
来自专栏程序生活

二叉树的遍历

15840
来自专栏Rude3Knife的后端开发专栏

[Leetcode][python]Balanced Binary Tree/平衡二叉树

判断一颗二叉树是否是“高度”平衡的。 平衡二叉树的定义是二叉树的任意节点的两颗子树之间的高度差小于等于1。 这实际上是AVL树(维基百科)的定义。

13120
来自专栏Rude3Knife的后端开发专栏

[Leetcode][python]Binary Tree Maximum Path Sum/二叉树中的最大路径和

求一棵二叉树中最大的路径和。该路径可以是二叉树中某一节点到树中任意一个节点的所经过的路径,不允许重复经过一个节点,不必经过根节点。

15220
来自专栏Rude3Knife的后端开发专栏

[Leetcode][python]Convert Sorted Array to Binary Search Tree

二叉查找树(英语:Binary Search Tree),也称二叉搜索树、有序二叉树(英语:ordered binary tree),排序二叉树(英语:sort...

9120

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励