二叉搜索树的实现

浅浅的花香味﹌ 2023-09-27 12:13 77阅读 0赞

![在这里插入图片描述][9ccac89b176d4a14b167faaf1b505294.gif_pic_center]

#### 文章目录 ####

*   *  什么是搜索树？
     *  查找操作
     *  插入操作
     *  删除操作
     *  实现

### 什么是搜索树？ ###

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

> 1.若它的左子树不为空，则左子树上所有节点的值都小于根节点的值  
> 2.若它的右子树不为空，则右子树上所有节点的值都大于根节点的值  
> 3.它的左右子树也分别为二叉搜索树

![在这里插入图片描述][f9e58c1238af4f4784e8f19a414dd7c3.png]

### 查找操作 ###

![在这里插入图片描述][212e7082d6b74df4b10b2fe02a5c0f09.png]  
这里我们定义一个cur指针用来遍历搜索树。

//查找key是否存在
        public TreeNode search(int key) {
        
            TreeNode cur = root;
            while(cur != null) {
        
                if(cur.key == key) {
        
                    return cur;
                }else if(cur.key > key){
        
                    cur = cur.left;
                }else {
        
                    cur = cur.right;
                }
            }
            return null;
        }

### 插入操作 ###

1.  如果树为空树，即根 == null，直接插入  
    ![在这里插入图片描述][abaf5c09708f4b86a8708f45467544f1.png]
2.  如果树不是空树，按照查找逻辑确定插入位置，插入新结点  
    ![在这里插入图片描述][2bc47440a5564d79b9138a7ea1939f61.png]  
    定义一个cur去遍历搜索树，parent用来记录cur的上一位置，如果该结点大于key则遍历左子树，小于遍历右子树，等于直接退出(搜索树不允许出现相同的数值)。

public boolean insert(int key) {
        
            if(root == null) {
        
                root = new TreeNode(key);
            }
            TreeNode prev = null;
            TreeNode cur = root;
            while(cur != null) {
        
                if(cur.key == key) {
        
                    return false;
                }else if(cur.key > key) {
        
                    prev = cur;
                    cur = cur.left;
                }else {
        
                    prev = cur;
                    cur = cur.right;
                }
            }
            if(prev.key > key) {
        
                prev.left = new TreeNode(key);
            }else {
        
                prev.right = new TreeNode(key);
            }
            return true;
        }

### 删除操作 ###

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

分三种情况:  
**1.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

**2.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

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

第一和第二种情况相对比较简单，改变一下parent的指向即可，我们具体讨论一下第三种情况。

![在这里插入图片描述][db01cb433ece4b3eb9aac933d83294b3.png]  
如果我们想从上面的 搜索树 中删除 15，我们可以做一些技巧来将情况减少到情况 1 或情况 2  
**1.求其右子树的最小值**  
**2.求其左子树的最大值**  
![在这里插入图片描述][73b9304e822e45e69968c5160e3d4f96.png]  
我们可以发现我们只需要找到右子树的最左的，或者左子树最右的和cur交换即可，不影响搜索树的顺序。

public boolean remove(int key) {
        
            TreeNode prev = null;
            TreeNode cur = root;
            while(cur != null) {
        
                if(cur.key == key) {
        
                    removeChild(prev,cur);
                    return true;
                }else if(cur.key > key) {
        
                    prev = cur;
                    cur = cur.left;
                }else {
        
                    prev = cur;
                    cur = cur.right;
                }
            }
            return false;
        }
        public  void removeChild(TreeNode parent,TreeNode cur) {
        
            if(cur.left == null) {
        
                if(cur == root) {
        
                    root = root.right;
                } else if(cur == parent.left) {
        
                    parent.left = cur.right;
                }else {
        
                    parent.right = cur.right;
                }
            }else if(cur.right == null) {
        
                if(cur == root) {
        
                    root = root.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;
                }
            }
        }

### 实现 ###

public class BinarySearchTree {
        
        static class TreeNode {
        
            public int key;
            public TreeNode left;
            public TreeNode right;
    
            public TreeNode(int key) {
        
                this.key = key;
            }
    
            @Override
            public String toString() {
        
                return "TreeNode{" +
                        "key=" + key +
                        '}';
            }
        }
    
        public TreeNode root;
    
        /**
         * 插入一个元素
         */
        public boolean insert(int key) {
        
            if(root == null) {
        
                root = new TreeNode(key);
            }
            TreeNode prev = null;
            TreeNode cur = root;
            while(cur != null) {
        
                if(cur.key == key) {
        
                    return false;
                }else if(cur.key > key) {
        
                    prev = cur;
                    cur = cur.left;
                }else {
        
                    prev = cur;
                    cur = cur.right;
                }
            }
            if(prev.key > key) {
        
                prev.left = new TreeNode(key);
            }else {
        
                prev.right = new TreeNode(key);
            }
            return true;
        }
    
        public  void inOrder(TreeNode root) {
        
            if(root == null) {
        
                return;
            }
            inOrder(root.left);
            System.out.println(root.key + " ");
            inOrder(root.right);
        }
        //查找key是否存在
        public TreeNode search(int key) {
        
            TreeNode cur = root;
            while(cur != null) {
        
                if(cur.key == key) {
        
                    return cur;
                }else if(cur.key > key){
        
                    cur = cur.left;
                }else {
        
                    cur = cur.right;
                }
            }
            return null;
        }
    
        public boolean remove(int key) {
        
            TreeNode prev = null;
            TreeNode cur = root;
            while(cur != null) {
        
                if(cur.key == key) {
        
                    removeChild(prev,cur);
                    return true;
                }else if(cur.key > key) {
        
                    prev = cur;
                    cur = cur.left;
                }else {
        
                    prev = cur;
                    cur = cur.right;
                }
            }
            return false;
        }
        public  void removeChild(TreeNode parent,TreeNode cur) {
        
            if(cur.left == null) {
        
                if(cur == root) {
        
                    root = root.right;
                } else if(cur == parent.left) {
        
                    parent.left = cur.right;
                }else {
        
                    parent.right = cur.right;
                }
            }else if(cur.right == null) {
        
                if(cur == root) {
        
                    root = root.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;
                }
            }
        }
    }

[9ccac89b176d4a14b167faaf1b505294.gif_pic_center]: https://img-blog.csdnimg.cn/9ccac89b176d4a14b167faaf1b505294.gif#pic_center
[f9e58c1238af4f4784e8f19a414dd7c3.png]: https://img-blog.csdnimg.cn/f9e58c1238af4f4784e8f19a414dd7c3.png
[212e7082d6b74df4b10b2fe02a5c0f09.png]: https://img-blog.csdnimg.cn/212e7082d6b74df4b10b2fe02a5c0f09.png
[abaf5c09708f4b86a8708f45467544f1.png]: https://img-blog.csdnimg.cn/abaf5c09708f4b86a8708f45467544f1.png
[2bc47440a5564d79b9138a7ea1939f61.png]: https://img-blog.csdnimg.cn/2bc47440a5564d79b9138a7ea1939f61.png
[db01cb433ece4b3eb9aac933d83294b3.png]: https://img-blog.csdnimg.cn/db01cb433ece4b3eb9aac933d83294b3.png
[73b9304e822e45e69968c5160e3d4f96.png]: https://img-blog.csdnimg.cn/73b9304e822e45e69968c5160e3d4f96.png