二叉搜索树

超、凢脫俗 2024-04-19 09:50 14阅读 0赞

## 二叉搜索树 ##

> **二叉搜索树(又名二叉查找树、二叉排序树)：它或者是一棵空树，或者是具有下列性质的二叉树：**  
> **  若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；**  
> **  若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；**  
> **  它的左、右子树也分别为二叉搜索树。**

#####   举个栗子，下图便是一个二叉搜索树： #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70]

#####   二叉搜索树最重要的性质：`二叉搜索树的中序遍历是升序的`。 #####

#####   对于二叉搜索树的基本操作来讲，与二叉树的大致相同，无非增删改查。 #####

#####   本篇文章不直接处理一颗二叉搜索树，而是自己实现一个简化版的Map集合，该简化版Map集合的底层由一颗二叉搜索树组成(Java中Map的实现是利用哈希表+红黑树)，通过对Map集合的操作，完成对二叉搜索树的学习和理解。 #####

#####   首先定义出Map的大体轮廓，Map是由key-value组成的键值对的集合，那么首先定义二叉搜索树结点类Node(静态内部类) #####

private static class Node{
            int key;
            int value;
    
            public Node(int key, int value) {
                this.key = key;
                this.value = value;
            }
    
            Node left;
            Node right;
        }

#####   并在自定义Map类(BinaryTreeForMap)中，创建二叉搜索树的根节点root。 #####

private Node root = null;

#####   根据二叉搜索树查找当前key所对应的value，此处采用while循环，也可使用递归调用。BinaryTreeForMap的get()方法如下： #####

######    由于二叉搜索树的中序遍历是升序的，则很容易想到，若key小于当前节点的值，则需要在当前节点的左子树中找，若key大于当前节点的值，则需要在当前节点的右子树中找，否则若相等，则返回当前节点的value值。 ######

public int get(int key){
            Node cur = this.root;
            while (cur!=null){
                if(key<cur.key){
                    cur = cur.left;
                }else if(key>cur.key){
                    cur = cur.right;
                }else {
                    return cur.value;
                }
            }
            return -1;
        }

#####   Map中元素的增加和修改都对应了二叉搜索树的插入，由于Map的特性(key不能重复)，因此如果没找到当前key所对应的节点就进行插入操作，若找到当前key所对应的结点就进行修改(更新)操作。<该段代码的注释已经讲得很清楚了> #####

public int put(int key,int value){
            // 若root为null，只需要新建一个root结点即可，不需要做下面的操作了
            if (this.root == null){
                this.root = new Node(key,value);
                return -1;
            }
            // 为插入操作设置父节点
            Node parent = null;
            Node cur = this.root;
            // 如果在循环里就return了，证明是找到结点并进行修改
            while (cur!=null){
                if(key<cur.key){
                    parent = cur;
                    cur = cur.left;
                }else if(key>cur.key){
                    parent = cur;
                    cur = cur.right;
                }else {
                    int oldValue = cur.value;
                    cur.value = value;
                    return oldValue;
                }
            }
            // 如果循环退出仍没有return，证明是没找到结点，应该进行插入(记录了parent)
            Node node = new Node(key,value);
            // 新结点可能是parent的左孩子，也可能是右孩子
            // 此时需要访问parent的value域，这时就要考虑，parent会不会为null
            // parent为null只有一种可能——root为null，程序不会进入上面的循环，
            // 由此，需要在上面添加一步判断root的操作
            if(key<parent.key){
                parent.left = node;
            }else {
                parent.right = node;
            }
            return -1;
        }

#####   最难理解也是最重要的就是Map的删除操作了，同样对应二叉搜索树的删除操作。二叉搜索树的删除操作有8种可能性(设cur为被删除的结点) #####

######    1、cur.left==null(默认包含了cur.left==null&&cur.right==null的情况) ######

######     1.1 cur是其父节点的左节点 ######

######     1.2 cur是其父节点的右节点 ######

######     1.3 cur是根节点 ######

######    2、cur.right==null ######

######     2.1 cur是其父节点的左节点 ######

######     2.2 cur是其父节点的右节点 ######

######     2.3 cur是根节点 ######

######    3、cur.left!=null&&cur.right!=null(`替换法——找左子树最大/找右子树最小——以下操作使用找左子树最大`) ######

######     3.1 maxNode是其父节点的左节点(可能左子树最大的元素是要被删除结点的左子节点) ######

######     3.2 maxNode是其父节点的右节点(普通情况) ######

#####   先贴一下代码，返回被删除结点的value，若结点不存在，返回-1。 #####

public int remove(int key){
            if(root == null){
                return -1;
            }
            Node cur = this.root;
            Node parent = null;
            int ret = -1;
            while(cur!=null){
                if(key<cur.key){
                    parent = cur;
                    cur = cur.left;
                }else if(key>cur.key){
                    parent = cur;
                    cur = cur.right;
                }else {
                    ret = cur.value;
                    // 找到结点进行删除工作
                    if(cur.left == null){
                        if(cur==this.root){
                            ret = cur.value;
                            this.root = cur.right;
                            break;
                        }
                        if(cur == parent.left){
                            parent.left = cur.right;
                            break;
                        }else{
                            parent.right = cur.right;
                            break;
                        }
                    }else if(cur.right == null){
                        if(cur==this.root){
                            ret = cur.value;
                            this.root = cur.left;
                            break;
                        }
                        if(cur == parent.left){
                            parent.left = cur.left;
                            break;
                        }else {
                            parent.right = cur.left;
                            break;
                        }
                    }else {
                        Node maxNode = cur.left;
                        Node maxParent = cur;
                        while (maxNode.right!=null){
                            maxParent = maxNode;
                            maxNode = maxNode.right;
                        }
                        cur.key = maxNode.key;
                        cur.value = maxNode.value;
                        if(maxNode==maxParent.left){
                            maxParent.left = maxNode.left;
                        }else {
                            maxParent.right = maxNode.left;
                        }
                    }
                }
            }
            return ret;
        }

#####   看逻辑+代码可能有些难以理解，下面用图片来理清思路。 #####

######    1、cur.left==null ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 1]

######    2、cur.right==null ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 2]

######    3、cur.left!=null&&cur.right!=null ######

######     3.1 maxNode是其父节点的左节点(可能左子树最大的元素是要被删除结点的左子节点) ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 3]

######     3.2 maxNode是其父节点的右节点(普通情况) ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 4]

#####   基本上二叉搜索树的相关操作逻辑就是这么多，最难的就是二叉搜索树删除的8种情况的讨论，然而通过二叉搜索树还可以实现Map的其他方法及操作，可以查看源码：[二叉搜索树实现简化版Map][Map]。 #####

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/082c053e059f410ba1dfbbdf0860bfce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/1100bca848b2451ab1e84ea9ce53aa31.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/989fe360e2b346749cf99292e82ef612.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/5547a43829084560ac24840092f3fab3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/ae52c430438041adb6c93c89a975cb44.png
[Map]: https://github.com/xiaomessi/JavaTest/blob/master/JavaDSTest/src/com/xiaoaxiao/binary_search_test/BinarySearchTree.java