二叉搜索树的操作及其实现

╰半夏微凉° 2024-04-01 08:42 71阅读 0赞

![ced485cbb11e458d81a746890b32cf3f.gif][]

> 作者：渴望力量的土狗
> 
> 博客主页：[渴望力量的土狗的博客主页][Link 1]
> 
> 专栏：[数据结构与算法][Link 2]
> 
> 工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网
> 
> [点击免费注册和我一起刷题吧][Link 3]

**目录**

二叉搜索树的概念：

二叉搜索树的操作及其实现

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

## 二叉搜索树的概念： ##

二叉搜索树是一种特殊的二叉树，要么是一颗空树，要么满足以下几点：

1、 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

2、若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

3、它的左右子树也分别为二叉搜索树

下面就是一颗典型的二叉搜索树：

![24ce823acf0941f896dfe6c5653468f0.png][]

## 二叉搜索树的操作及其实现 ##

二叉搜索树的查找效率是比较高的，类似与我们所熟知的二分查找。它的查找方式是这样的：如果我们要查找6这个数字，那么我们从根节点开始，遇到根节点的val是5,6>5,所以我们要往右搜寻，遇到7的时候，6<7,这时我们向右左找即可，这就找到了我们要找的数字。

我们可以看的出它的时间复杂度是O(logn)，也就是搜索树的高度，但是，如果这颗搜索树呈现线性的化，也就是一条线的情况：

![55f03e205e57666dd7e766cc4a543857.png][]

这时我们在搜索的时候就类似于线性查找，时间复杂度就达到了O(n)了。

然后就是二叉搜索树的插入操作，我们怎么把数据插入到原来的二叉搜索树当中呢？插入的操作和查找有点类似，需要搜索到需要查找的位置。具体逻辑为：当树空的时候直接new一个结点即可，不空的情况下，当我们要插入一个元素的时候我们需要知道它的前一个元素，这样我们才能实现插入操作，插入的位置都是为空的，所以我们要查找到它适合的位置即可。

二叉搜索树的删除属于最重要的内容，因为它的删除操作可能比较复杂一点，我们在删除某一个结点的时候需要调整，你怎么知道调整后是什么样子的呢？删除前我们还是要进行搜索，找到待删除结点的位置。

这里先说一下删除的步骤：

设待删除结点为 cur, 待删除结点的双亲结点为 parent

一. cur.left == null （要删除结点的左边为空时）

1. cur 是 root，则 root = cur.right

2. cur 不是 root，cur 是 parent.left，则 parent.left = cur.right

3. cur 不是 root，cur 是 parent.right，则 parent.right = cur.right

![e1c5497995da40949bee0a734fc25a72.png][]

二. cur.right == null （要删除结点的右边为空时）

1. cur 是 root，则 root = cur.left

2. cur 不是 root，cur 是 parent.left，则 parent.left = cur.left

3. cur 不是 root，cur 是 parent.right，则 parent.right = cur.left

![f1e4ee6addfc431bae559d6962c0e604.png][]

三. cur.left != null && cur.right != null

1. 需要使用替换法进行删除，即在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被 删除节点中，再来处理该结点的删除问题

下面对二叉搜索树进行实现：

public class BinarySearchTree {
    
        static class TreeNode {
            public int key;
            public TreeNode left;
            public TreeNode right;
    
            TreeNode(int key) {
                this.key = key;
            }
        }
    
        public TreeNode root;
    
        /**
         * 插入一个元素
         * @param key
         */
        public boolean insert(int key) {
            //根结点
            if(root==null){
                root=new TreeNode(key);
                return true;
            }
    
            //找到需要插入的位置
            TreeNode cur=root;//找位置
            TreeNode parent=cur;//插入位置的父节点
            while(cur!=null){
                if(cur.key<key){
                    parent=cur;
                    cur=cur.right;
                } else if (cur.key>key) {
                    parent=cur;
                    cur=cur.left;
                }else{
                    //不可以插入相同的元素
                    return false;
                }
            }
            //此时cur为空了，这个位置就是插入的位置
            //这里需要讨论插入到parent的左边还是右边
            if(key> parent.key){
                //插入右边
                parent.right=new TreeNode(key);
            }else{
                //插入左边
                parent.left=new TreeNode(key);
            }
            return true;
        }
    
        /**
         * 查找key是否存在
         * @param key
         * @return
         */
        public TreeNode search(int key) {
           TreeNode cur=root;
    
           //我们搜索的最差情况为当前结点为空
            while (cur!=null){
    
                //先判断根结点
                if(cur.key==key){
                    return cur;
                    //如果key比结点的key大向右找
                } else if (cur.key<key) {
                    cur=cur.right;
                    //如果key比结点的key小向左找
                } else {
    
                    cur=cur.left;
                }
            }
            //如果cur为空则返回空
            return null;
        }
        //中序遍历
        public void inOrder(TreeNode root){
    
            if(root==null){
                return;
            }
            inOrder(root.left);
            System.out.print(root.key+" ");
            inOrder(root.right);
    
    
        }
    
    
        /**
         * 删除key的值
         * @param key
         * @return
         */
        public void remove(int key) {
    
            TreeNode parent = null;
            TreeNode cur = root;
            while (cur != null) {
                if(cur.key == key) {
                    removeNode(parent,cur);
                    return;
                }else if(cur.key < key) {
                    parent = cur;
                    cur = cur.right;
                }else {
                    parent = cur;
                    cur = cur.left;
                }
            }
        }
    
        private void removeNode(TreeNode parent,TreeNode cur) {
            if(cur.left == null) {
                if(cur == root) {
                    root = cur.right;
                }else if(cur == parent.left) {
                    parent.left = cur.right;
                }else {
                    parent.right = cur.right;
                }
            }else if(cur.right == null) {
                if(cur == root) {
                    root = cur.left;
                } else if (cur == parent.left) {
                    parent.left = cur.left;
                }else {
                    parent.right = cur.left;
                }
            }else {
                TreeNode target = cur.right;
                TreeNode targetParent = cur;
                while (target.left != null) {
                    targetParent = target;
                    target = target.left;
                }
                cur.key = target.key;
                if(target == targetParent.left) {
                    targetParent.left = target.right;
                }else {
                    targetParent.right = target.right;
                }
            }
        }
    
    
    }

[ced485cbb11e458d81a746890b32cf3f.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/fb7cca94aa0b482ba5bd40aefd30c3e9.gif
[Link 1]: https://blog.csdn.net/m0_67995737?type=blog
[Link 2]: https://blog.csdn.net/m0_67995737/category_12000344.html
[Link 3]: https://www.nowcoder.com/link/pc_csdncpt_ylcxx_c
[24ce823acf0941f896dfe6c5653468f0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/b21a3b188ec94fe29af8141a7eaa1976.png
[55f03e205e57666dd7e766cc4a543857.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/30394086e30845028b38aaff9f714bd7.png
[e1c5497995da40949bee0a734fc25a72.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/349827b81e074768a23278b1b015c9b1.png
[f1e4ee6addfc431bae559d6962c0e604.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/bbf2dd9bc31f427c9e8869d685daec4e.png