对二叉搜索树的理解

青旅半醒 2024-03-31 09:17 64阅读 0赞

### 一.二插搜索树的概念 ###

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

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

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

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

图示如下：

![707ce731112f451d85ef639bc39038d4.png][]

通过观察图片我们不难发现， **对于二叉搜索树而言，其中序排序的结果是一个有序数组**

**在说明基本功能之前，我们先对其实现的基本结构进行简单的说明：**

**1.需要二插搜索树结构2.需要结点结构**

**代码如下：**

public class BinarySearchTree {
    TreeNode root;//根结点
     // 定义节点类
        private static class TreeNode {
            int value;
            TreeNode left;
            TreeNode right;
    
            public TreeNode(int value) {
                this.value = value;
            }
        }
    }

### **二.基本功能的实现** ###

**1.插入结点**

**思路如下：**

我们将插入操作进行分类讨论

首先通过该值创建一个新结点

1.如果当前树没有根结点，**让该结点等于根结点即root=node;**

![4ae0bab8e9e04a6bb8e599bb9af28809.png][]

2.当前树存在根结点,如果树存在根结点，那么就**需要父子指针进行遍历，直到找到插入结点的位置并进行插入操作**

![5b23d88398134f4dad1adc6eb09878a4.png][]

代码如下：

public boolean insert(int value) {
           //建立新结点
            TreeNode treeNode = new TreeNode(value);
            //判断根结点是否为空
            if(root==null){
                root=treeNode;
                return true;
            }
            //处理跟结点不为空的情况
            TreeNode cur=root;
            //对树进行遍历
            TreeNode prev=null;
            while(cur!=null){
    
                    if(cur.value==value){
                        return false;
                    }
                   //将当前结点进行保存
                        prev=cur;
                //对值的大小进行比较
                if(value>cur.value){
                    cur=cur.right;
                }
                else{
                    cur=cur.left;
                }
            }
            if(prev.value>value){
                prev.left=treeNode;
            }
            else{
                prev.right=treeNode;
            }
            return true;
        }

**2.查找结点**

**思路如下：我们同样需要创建一个辅助结点(cur)进行遍历：从根结点进行遍历,如果cur.value==value,就返回TRUE，**

**否则**

**如果cur.value<value,就让cur=cur.right(向右子树方向进行调整)，否则向左子树方向进行调整**

![01cf22267bf4449c9dc8f66e10932bd3.png][]

例子：

![b7496b2ec5f34c0aae72bc4deb17da0d.png][]

**代码如下：**

public boolean search(int value) {
            //判断根结点是否为空
            if(root==null){
                return false;
            }
            //定义遍历节点
            TreeNode cur=root;
            //根据节点值的大小进行遍历
            while (cur!=null){
                if(cur.value==value){
                    return true;
                }
                if(cur.value<value){
                    cur=cur.right;
                }
                else{
                    cur=cur.left;
                }
            }
            return false;
        }

#### **3.删除结点（难点）** ####

**思路：在讲解删除结点之前，我们需要理解的是：我们无论是插入操作还是删除操作，都是在对数值进行搜索的前提下展开的，也就是说，如果我们想要对具体数值进行插入或者删除，我们必须找到相应的位置**

**在找到具体位置的基础上(即找到的结点为cur)，我们对删除操作进行分类讨论**

**1.要删除的结点没有左子节点**

**1.1 要删除的结点是根结点，直接让root=cur.right**

**1.2要删除的结点位于父节点的左侧，让parent.left=cur.right**

**1.3要删除的结点位于父节点的右侧，让parent.right=cur.right**

**2.要删除的结点没有右子结点**

**2.1 要删除的结点是根结点，直接让root=cur.left**

**2.2要删除的结点位于父节点的左侧，让parent.left=cur.left**

**2.3要删除的结点位于父节点的右侧，让parent.right=cur.left**

**3.要删除的结点左右子节点均存在**

**那么这时候插入操作事实上已经转为了一种替换操作（替罪羊），具体思路如下：为了在删除之后该树仍表现为二插搜索树，我们发现只有将****该结点的左子树的最右结点或者将该结点的右子树的最左结点进行替换，然后将最左节点或者最右结点进行删除即可****，根据该思路，我们能够发现的是：我们至少需要两个新的变量：****target（负责遍历左子树或者右子树，直至找到目标结点并进行替换），parentTarget(负责记录target的结点，用以target遍历找到后进行替换删除)**

**代码如下：**

/**
         * 删除指定的元素
         * @param value 要删除的元素
         * @return
         */
        public boolean remove(int value) {
            //对根结点进行判断
            if(root==null){
                return false;
            }
            //定义辅助结点进行寻找
            TreeNode parent=null;
            TreeNode cur=root;
            while(cur!=null){
                if(cur.value==value){
                    removeNode(parent,cur);
                    return true;
                }
                //在cur结点向下遍历前将parent进行移位
                parent=cur;
                if(cur.value<value){
                    cur=cur.right;
                }
                else if(cur.value>value){
                    cur=cur.left;
                }
            }
    
            return false;
        }
    
        /**
         * 分类讨论要删除节点的不同情况
         * @param parent 父节点
         * @param cur 子节点
         */
        private void removeNode(TreeNode parent, TreeNode cur) {
            //处理cur没有左子节点的情况
            if(cur.left==null){
                //如果是根结点
                if(cur==root){
                    root=cur.right;
                }
                //如果是父节点的左子节点
                if(parent.left==cur)
                parent.left=cur.right;
                //如果是父节点的右子节点
                if(parent.right==cur)
                    parent.right=cur.right;
            }
            //处理cur没有右子结点的情况
            else if (cur.right==null) {
                //处理cur为根的情况
                if(cur==root){
                    root=cur.left;
                }
                //处理cur为父节点的左子节点
                if(parent.left==cur){
                    parent.left=cur.left;
                }
                //处理cur为父节点的右子节点
                if(parent.right==cur)
                {
                    parent.right=cur.left;
                }
    
            }
            //对cur既有左子节点又有右子结点的情况进行处理
            else{
                //用左子节点的最大值替换或者右子结点的最小值替换
                //notes：此处处理逻辑为替换，之前两种情况处理逻辑为删除，略有不同
                TreeNode curParent=cur;
                //找左子树的右子结点(或者右子树的最左子节点也可以)
                TreeNode target=cur.left;
                while(target.right!=null){
                    curParent=target;
                    target=target.right;
                }
                //替换
                cur.value=target.value;
                //删除左子节点的最右子结点
                if(curParent.left==target){
                    curParent.left=target.left;
                }
                else {
                    curParent.right=target.left;
                }
    
    
            }
    
        }

### **三.性能分析** ###

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。

**对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度 的函数，即结点越深，则比较次数越多。**

但对于同一个关键码集合，如果各 **关键码插入的次序不同** ，可能得到不同结构的二叉搜索树：

![3170584758354d74afa219ecbf51cc0e.png][]

![a3d3df85359b4f8c9c3010dc8e0196ec.png][]

[707ce731112f451d85ef639bc39038d4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/62c652504d764d2fa2d437cec3c4e01c.png
[4ae0bab8e9e04a6bb8e599bb9af28809.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/f4dcf7e873334c3c858729c6182b3b81.png
[5b23d88398134f4dad1adc6eb09878a4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/0f96dcab62a54a3da1145782bc4e6604.png
[01cf22267bf4449c9dc8f66e10932bd3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/6b393c429965441b974351e2891622c7.png
[b7496b2ec5f34c0aae72bc4deb17da0d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/e82b72882e9143f8beec97ace3505242.png
[3170584758354d74afa219ecbf51cc0e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/cb2038ccb3934d4fad80818f5adec313.png
[a3d3df85359b4f8c9c3010dc8e0196ec.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/eb8d3b0c1891478ea3f4cc3005d2d81e.png