手撕二叉搜索树——模拟实现

朴灿烈づ我的快乐病毒、 2023-09-28 19:35 27阅读 0赞

**前言：**

二叉搜索树的查找效率代表了其插入，删除的操作的性能，这次通过模拟实现二叉搜索树，增加对其底层实现的认识。

**值得提到的一点：**

二叉搜索树的插入，和查找功能很易实现，本篇作为**学习笔记**，重点了解其删除功能的实现。（**代码在最后**）

--------------------

**删除功能：**

如何找到待删除的结点？可以通过创建一个cur指针，和一个parent指针(用来指向cur的父亲结点)，cur通过二叉搜索树的性质（左结点的值 < 根节点的值 < 右结点的值）遍历二叉搜索树，找到待删除元素后分以下三大种情况:

**1.cur.left == null;**

满足以上条件继续分为，cur == root、cur != root即cur是否为parent的左节点或右结点；

**2.cur.right == null;**

满足以上条件继续分为，cur == root、cur != root即cur是否为parent的左节点或右结点；

**3.cur.left != null && cur.right != null;(难点)**

此时需要用替代法进行删除，替代法删除有以下两种方法：（任选一种即可，本篇代码实现选用第一种）

*  在cur的右边找到最小值，并且若能找到这个最小值，这个最小值点一定不存在左子树；
 *  在cur的左边找到最大值，并且若能找到这个最大值，这个最大值点一定不存在右子树；

最后通过target(需要被替换的结点)和targetParent(target的父亲结点)两个指针来进行删除操作。

> 感觉有点懵？来看下方图解：

![39c49714130d4a74b00f8d650d42635e.png][]

![6c9429f69d894eb8be32687d0f5d1eea.png][]

![c24b36929cd34738830b78c89953328c.png][]

![2694a5fb883c4638a94fc3075a0849f3.png][]

![69cc7de4640b4298840b7234d0fed37c.png][]

![9a210f3e41074000a28262a2bd9e9ee2.png][]

--------------------

> 代码实现：

public class BinarySearchTree {
        static class TreeNode{
            TreeNode left;
            TreeNode right;
            int val;
            public TreeNode(int val){
                this.val = val;
            }
        }
        TreeNode root = null;
        //查找结点
        public TreeNode sreach(int key){
            TreeNode cur = root;
            while(cur != null){
                if(cur.val > key){
                    cur = cur.left;
                }else if(cur.val < key){
                    cur = cur.right;
                }else{
                    return cur;
                }
            }
            return null;
        }
        //插入结点
        public boolean insert(int key){
            if(root == null){
                root = new TreeNode(key);
                return true;
            }
            TreeNode cur = root;
            TreeNode parent = root;
            while(cur != null){
                parent = cur;
                if(cur.val > key){
                    cur = cur.left;
                }else if(cur.val < key){
                    cur = cur.right;
                }else{
                    return false;
                }
            }
            if(parent.val > key){
                parent.left = new TreeNode(key);
            }else{
                parent.right = new TreeNode(key);
            }
        return true;
        }
        //删除结点
        public void remove(int key){
            TreeNode cur = root;
            TreeNode parent = root;
            while(cur != null){
                if(cur.val > key){
                    parent = cur;
                    cur = cur.left;
                }else if(cur.val < key){
                    parent = cur;
                    cur = cur.right;
                }
                else{//找到了,并删除
                    removeNode(cur,parent);
                    return;
                }
            }
        }
        private void removeNode(TreeNode cur, TreeNode parent){
            //分三大种情况: 1.cur.left == null
            if(cur.left == null){
                if(cur == root){
                    root = cur.right;
                }else if(parent.left == cur){
                    parent.left = cur.right;
                }else if(parent.right == cur){
                    parent.right = cur.right;
                }
                //第二大种情况:2.cur.right == null
            }else if(cur.right == null){
                if(cur == root){
                    root = cur.left;
                }else if(parent.left == cur){
                    parent.left = cur.left;
                }else if(parent.right == cur){
                    parent.right = cur.left;
                }
            }
            else{
                /**
                 * 第三大种情况：cur两边都不为空
                 * 可以使用替换法进行删除，有以下两种替换方式（任意一种即可）
                 * 1.在cur的右边找最小值，并且若能找到这个最小值，这个最小值点一定不存在左子树
                 * 2.在cur的左边找最大值，并且若能找到这个最小值，这个最大值点一定不存在右子树
                 * 以下代码通过方法1实现
                 * 通过target和targetParent来确定要替换的结点
                 */
                TreeNode targetParent = cur;
                TreeNode target = cur.right;
                while(target.left != null){
                    targetParent = target;
                    target = target.left;
                }
                cur.val = target.val;
                //分两种情况
                if(targetParent.left == target){
                    targetParent.left = target.right;
                }else{
                    targetParent.right = target.right;
                }
            }
        }
        //中序遍历打印二叉树
        public void Print(TreeNode root){
            if(root == null){
                return;
            }
            Print(root.left);
            System.out.print(root.val);
            Print(root.right);
        }
    }

[39c49714130d4a74b00f8d650d42635e.png]: https://img-blog.csdnimg.cn/39c49714130d4a74b00f8d650d42635e.png
[6c9429f69d894eb8be32687d0f5d1eea.png]: https://img-blog.csdnimg.cn/6c9429f69d894eb8be32687d0f5d1eea.png
[c24b36929cd34738830b78c89953328c.png]: https://img-blog.csdnimg.cn/c24b36929cd34738830b78c89953328c.png
[2694a5fb883c4638a94fc3075a0849f3.png]: https://img-blog.csdnimg.cn/2694a5fb883c4638a94fc3075a0849f3.png
[69cc7de4640b4298840b7234d0fed37c.png]: https://img-blog.csdnimg.cn/69cc7de4640b4298840b7234d0fed37c.png
[9a210f3e41074000a28262a2bd9e9ee2.png]: https://img-blog.csdnimg.cn/9a210f3e41074000a28262a2bd9e9ee2.png