【数据结构】二叉搜索树

目录

一、概念

二、搜索二叉树的查找

三、搜索二叉树的插入

四、二叉搜索树的删除

五、性能分析

---

一、概念

二叉搜索树又称二叉排序树，他可以是一根空树，或者满足以下性质的二叉树：

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

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

他的左右子树也分别为二叉搜索树。

public class BinarySearch {
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }
    }
    // 需要告诉二叉搜索树的根
    public TreeNode root;
}

二、搜索二叉树的查找

    public TreeNode search2(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;
    }

三、搜索二叉树的插入

    public void insert(int val){
        if(root == null){
            root = new TreeNode(val);
        }
        TreeNode parent = root;
        TreeNode cur = root;
        while (cur != null){
            if(cur.val > val){
                parent = cur;
                cur = cur.left;
            }else{
                parent = cur;
                cur = cur.right;
            }
        }
        // 走到这，parent就是待插入节点的根节点，
        TreeNode node = new TreeNode(val);
        if(parent.val > val){
            // 比根节点小，就插在根节点的左边
            parent.left = node;
        }else{
            parent.right = node;
        }
    }

四、二叉搜索树的删除

分三种情况考虑：

第一种：待删除节点的左节点是空的

 第二种：待删除节点的右节点是空的

 第三种：待删除节点的左右节点都不为空

不是直接删除，直接删除需要修改很多指向。采用的方法是“替死鬼”

step1：先找到待删除节点右边最小的节点target

step2：交换target和cur的value

step3：删除target

 

 

    /**
     *
     * @param parent  待删除节点的父亲节点
     * @param cur  待删除节点，
     */
    private void remove(TreeNode parent, TreeNode cur) {
        // 分三种情况 cur.left == null cur.right == null cur的左和右都不为空
        if(cur.left == null){
            if(root == cur){
                root = cur.right;
            }else if(cur == parent.left){
                parent.left = cur.right;
            }else if(cur == parent.right){
                parent.right = cur.right;
            }
        }else if(cur.right == null){
            if(root == cur){
                root = cur.left;
            }else if(cur == parent.left){
                parent.left = cur.left;
            }else if(cur == parent.right){
                parent.right = cur.left;
            }
        }else{
            TreeNode target = cur.right;
            TreeNode tParent = cur;
            // parent向左走，找到cur的右子树的最小值
            while (target.left != null){
                tParent = target;
                target = target.left;
            }
            // 走到这 target的left == null  tagert是最小的值
            // 交换值
            cur.val = target.val;
            // 找到cur的右子树没有左子树
            if(target == tParent.right){
                tParent.right = target.right;
            }else{
                tParent.left = target.right;
            }
        }
    }

 五、性能分析

最优情况下，二叉搜索树为完全二叉树，其平均比较次数为: logN
最差情况下，二叉搜索树退化为单支树，其平均比较次数为: N/2
Java中利用搜索树实现的Map和Set。实际上使用的是红黑树。

红黑树是一根近似平衡的二叉搜索树，即在二叉搜索树的基础上+颜色和红黑树性质验证