️前言️

本篇文章——二叉搜索树既是对之前的文章【树与二叉树】的一些补充，也是给后续文章TreeMap和TreeSet接口介绍的铺垫。

博客主页：【如风暖阳】
精品Java专栏【JavaSE】、【备战蓝桥】、【JavaEE初阶】、【MySQL】、【数据结构】
欢迎点赞收藏留言评论私信必回哟

本文由 【如风暖阳】 原创，首发于 CSDN

博主将持续更新学习记录收获，友友们有任何问题可以在评论区留言

博客中涉及源码及博主日常练习代码均已上传码云(gitee)、GitHub

在这里给大家推荐博主常用到的刷题网站【牛客网】,剑指Offer专栏是面试笔试题目高频题单，赶快刷起来吧！

---

二叉搜索树

1.概念

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

• 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
• 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
• 它的左右子树也分别为二叉搜索树
• 二叉搜索树的中序遍历结果是有序的

如下图所示就是一棵二叉搜索树

先通过代码完成二叉搜索树的基本构造：

public class BinarySearchTree {
    
    static class TreeNode {
    
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
    
            this.val = val;
        }
    }
    public TreeNode root;
}

2.查找操作

在搜索树中查找关键值，因为二叉搜索树的特性，所以可以将关键值与根节点值比较，如果比根节点值小，就去左子树中寻找，反之去右子树中寻找。

	public TreeNode search(int key) {
    
        TreeNode cur=root;
        while (cur!=null) {
    
            if(cur.val<key) {
    
                cur=cur.right;
            }else if(cur.val>key) {
    
                cur=cur.left;
            }else {
    
                return cur;
            }
        }
        //走到这里说明没有找到关键字
        return null;
    }

3.插入操作

插入操作依然遵循二叉搜索树的特性，与根节点值进行比较，如果比它小就往左子树中插入，如果比它大就往右子树中插入，可以发现，最后都是插入到了叶子节点上。因为插入操作需要让上一个节点有引用指向插入节点，所以需要使用两个节点。

 	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) {
    
                parent=cur;
                cur=cur.left;
            }else {
    
                //存在相同的元素 则不能插入成功
                return false;
            }
        }
        //代码走到这里，cur==null，根据与上一个节点parent的val的比较，确定插入该结点的左还是右
        if(parent.val<key) {
    
            parent.right=node;
        }else {
    
            parent.left=node;
        }
        return true;
    }

4.删除操作

二叉搜索树的删除操作十分复杂，首先需要找到要删除的节点，但是该结点可能有左右子树，所以不能直接删除，需要分情况来确定具体的删除方式，如下：

设待删除结点为 cur, 待删除结点的父结点为 parent
1.cur.left == null

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

2.cur.right == null

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

3.cur.left != null && cur.right != null
需要使用替换法进行删除，即在它的右子树中寻找最小值（它一定没有左树）【或者在它的左子树中寻找最大值，它一定没有右树】，用它的值填补到被删除节点中，再来处理该结点的删除问题（处理该结点就和情况1相同，没有左子树）

代码实现：

    /** * 删除关键字为key的节点 * @param key */
    public void remove(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 {
    
                //代码走到此处说明找到了要删除的节点
                removeNode(cur,parent);
            }
        }
    }

    /** * 进行删除 * @param cur 要删除的节点 * @param parent 删除节点的父结点 */
    private void removeNode(TreeNode cur,TreeNode parent) {
    
        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 targetParent=cur;//记录用于替换的节点的上一个节点
            TreeNode target=cur.right;//记录用于替换的节点
            //在右子树中寻找最小值，就是一直往左走，走到尽头的节点就是最小值
            while (target.left!=null) {
    
                targetParent=target;
                target=target.left;
            }
            //找到用于替换的节点，完成值的替换，再去处理删除这个替换节点
            cur.val=target.val;
            //此时该节点一定没有左子树，与之前没有左子树的删除方法相同
            if(targetParent.left==target) {
    
                targetParent.left=target.right;
            }else {
    
                targetParent.right=target.right;
            }
        }
    }

5.性能分析

二叉搜索树的插入和删除操作都需要先进性查找，查找效率代表了二叉搜索树中各个操作的性能，根据不同的插入次序，得到的二叉树结构也可能不同。
最优情况：
得到一棵完全二叉树
查找的时间复杂度为O（$lo{g}_{2}N$）

最差情况：
得到一棵单分支的树
查找的时间复杂度为O(N)

TreeMap 和 TreeSet (这两个接口在后边的文章中介绍)即 java 中利用搜索树实现的 Map 和 Set；实际上用的是红黑树，而红黑树是一棵近似平衡的二叉搜索树，即在二叉搜索树的基础之上 + 颜色以及红黑树性质验证，关于红黑树的内容后序再进行讲解。

---

️最后的话️
总结不易，希望uu们不要吝啬你们的哟(＾Ｕ＾)ノ~ＹＯ！！如有问题，欢迎评论区批评指正