搜索二叉树（Java版）_java满二叉搜索树查找

1.搜索二叉树

   1.1搜索二叉树的概念

   1.2搜索二叉树 操作1 -- 查找

   1.3搜索二叉树 操作2 -- 插入

   1.4搜索二叉树 操作3 -- 删除（重难点）

   1.5性能分析

1.搜索二叉树

  1.1搜索二叉树

  搜索二叉树的本质就是一棵二叉树，但他不一定能满足完全二叉树的条件，搜索二叉树的性质有

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

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

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

 我们在这里给定一个int类型的数组去根据下标顺序去画一棵搜索二叉树

 例：int[] array = {5,3,4,1,7,8,2,6,0,9};

 

 

  1.2搜索二叉树 操作1 -- 查找

   根据搜索二叉树的性质我们可以很快明白在搜索二叉树中进行一次比较可以排除数组一半的元素

 //这里直接上实现代码

 先创建一个搜索二叉树对象

​
public class BinarySearchTree {
    public class TreeNode {
        public int val; //节点的值
        public TreeNode left; //节点的右树
        public TreeNode right;//节点的左树
 
        public TreeNode(int val) {
            this.val = val;
        }
    }
    public TreeNode root;
}
 
​

 //接着实现查找功

//查找
    /**
     * 找到val值返回节点的地址
     * 时间复杂度： 最好情况下（为一棵完全二叉树 或者 是满二叉树） o(log2n)
     * @param val
     * @return
     */
    public TreeNode search(int val) {
        TreeNode cur = root;
        while (cur != null) {
            if(cur.val == val) {
                return cur;
            } else if (cur.val > val) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        return null;
    }

1.3搜索二叉树 操作2 -- 插入

   搜索二叉树的插入操作和查找操作其实都差不多的，就是在插入操作需要额外再定义一个node的临时节点去跟在cur的后面（node移动总比我cur的慢那一步），当我的cur 走到 null 的时候 node就可以清楚我插入的元素到底是放在什么地方了，在插入是一定是插入到叶子位置

//上代码

 /**
     * 插入 二叉收索树在插入的时候一定是插入到叶子的位置
     *     在插入的时候光有一个cur是不够的 我cur为null的时候 我val要放的位置就是我cur记录到的位置
     * @param key 插入的数据
     * @return
     */
    public boolean insert(int key) {
        TreeNode node = new TreeNode(key);
        if(root == null) {
            root = node;//第一次插入的时候
            return true;
        }
        TreeNode cur = root;
        TreeNode parent = null;
        while (cur != null) {
            if(cur.val < key) {
                parent = cur;
                cur = cur.right;
            } else if(cur.val == key) {
                return false;//一样的值不能进行插入
            } else {
                parent = cur;
                cur = cur.left;
            }
        }
        if(parent.val > key) {
            parent.left = node;
        } else {
            parent.right = node;
        }
        return true;
    }

//这里要补充一句，就是我在搜索二叉树已经出现过的元素是不能后面再插入相同的元素的，你要强行插入进来的话也没有位置给你存放元素的

我们来运行上面的代码 看一下我们运行的代码的具体效果

 

 到现在为止感觉搜索二叉树好像也就这样而已，代码逻辑没啥难的

 那我们来看一下 搜索二叉树好玩的地方 删除

 1.4搜索二叉树 操作3 -- 删除（重难点）

     搜索二叉树在删除的实现需要分出3种大的类型在对这3种的类型进行细分（先使用图形表示）

    以下图形中均是设待删除结点为 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

//具体实现代码

 if(cur.left == null) {
            //先写有一边为空的情况 ---- 这种情况比较好分析
            if(cur == root) {
                root = cur.right;
            } else if(cur == parent.left) {
                parent.left = cur.right;
            } else {
                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.lef

//这一部分的具体代码实现

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;
            }
        }

   3). cur.left != null && cur.right != nul (最难搞的情况)

  在第三种情况这边我们换一个好玩的图去呈现第三种情况好玩的地方

 让我们来玩玩这张图的cur的删除

   先让我们进行分析 当我们把val值为10的节点删除以后我们要那什么东西去补上原本的节点的位置会合适一点，在我们观察过后会发现可以使用该节点下面的值去填补空缺

  这里就可以有两种思路了

    1.是拿cur左树的最大值去填补

    2.是拿cur右树的最小值去填补

我们下面就使用第二种方法去实现

  在实现前我们在观察一下，把上面的两种情况一结合是不是就相当于把我cur的左树的最大值（或者右树的最小值）赋值给cur的val值，然后删除存放左树的最大值（或者右树的最小值）的节点，就完成了我的删除操作了，我们就把这一种方法叫做”替罪羊“方法。

  要去实现这种方法的话我们使用到两个指针（t和tp）去完成，t指针是去找到左树的最大值（或者右树的最小值）的节点，tp指针是作为找到的节点的父亲节点，当对t指针的节点进行删除操作是，我父亲节点tp要去接盘的t节点的孩子节点（没有的话就接收null一样的）

  我们直接把删除操作的代码进行整合呈现出来

​
//删除（难点）
    /**
     * 删除节点key
     * @param key 删除的数据
     */
    public void removeNode(int key) {
        TreeNode cur = root;
        TreeNode parent = null;
        while (cur != null) {
            if(cur.val < key) {
                parent = cur;
                cur = cur.right;
            } else if(cur.val > key) {
                parent = cur;
                cur = cur.left;
            } else {
                remove(cur,parent);
                return;
            }
        }
    }
 
    /**
     * 删除cur节点
     * @param cur  要删除的节点
     * @param parent 要删除节点的父亲节点
     */
    private void remove(TreeNode cur , TreeNode parent) {
        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 {
            //cur的左右两边都不为空的情况
            //有两种写法 1.放当前节点的左树的最大值 ---》 左树的最右边 --- 没有右树了
            //         2.放当前节点的右树的最小值 ---》 右树的最左边 --- 没有左树了
            //替罪羊删除法（把我要换过去的数 放在原本要删除的位置） 然后把删除的位置换成前面找到替换过去数的位置
            TreeNode t = cur.right;
            TreeNode tp = cur;
            //找替罪羊
            while (t.left != null) {
                tp = t;
                t = t.left;
            }
            //把替罪羊换到cur的位置 然后把t原来的位置进行删除
            cur.val = t.val;
            //要判断我这个t是在tp的什么位置找到的
            //要对原来位置的父亲节点的左树或者右树进行拼接
            if(t == tp.left) {
                tp.left = t.right;
            } else {
                tp.right = t.right;
            }
        }
    }
 
​

    这里在父亲节点对t节点后面的元素进行拼接的时候一定要注意了，要判断是在什么位置找到t的，就在什么什么位置把后面的元素接上

  //这里要运行的话要从新去创建一下搜索二叉树，博主有点懒 就不去创建了，大佬们可以自己去尝试一下

1.5性能分析

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

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

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

最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：log2N（树的高度）-- 这里是log以2为底的N

最差情况下，二叉搜索树退化为单支树，其平均比较次数为： N/2

//欧克克了，这篇文章就到这里就结束了，本来说是要把map和set和搜索二叉树写在一起的，然后看搜索二叉树写的这么多就算了，把mapset放到下一篇文章去了，如果本篇文章哪里出现了错误欢迎在评论区指出（虽然可能回的速度会很慢，但是还会去看的），期待下一篇数据结构的博客吧