二叉搜索树(Java实现)

 博主主页: 码农派大星.

    数据结构专栏:Java数据结构

 数据库专栏:MySQL数据库

JavaEE专栏:JavaEE

关注博主带你了解更多数据结构知识

1.概念

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

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

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

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

2.实现二叉搜索树

定义节点

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

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

        }
    }
    public TreeNode root = null;

查找元素

  //查找
    public TreeNode seach(int key){
        TreeNode cur = root;
        while ( cur != null){  //根节点的值不等于要查找的key值,接下来循环

            if (cur.val < key){//根节点的值小于key值,让其在右子树继续查找
                cur = cur.right;

            }else if(cur.val > key){//根节点的值大于key值,让其在左子树继续查找
                cur = cur.left;

            }else {//找到了key值,返回即可
                return cur;
            }

        }
        return null;//树中没有要找的key值,直接返回null
    }

插入元素 

1.如果为空，那么直接插入
2.如果不为空，如果小于根则插入左边，大于则插入右边

 //插入
    public void insert(int val){
        TreeNode node = new TreeNode(val);
        if(root == null){
            root = node;
            return;
        }
        TreeNode cur = root;
        TreeNode parent = null;
        while (cur != null){
            if(cur.val < val){
                parent = cur;
                cur = cur.right;
            }else if(cur.val > val){
                parent = cur;
                cur = cur.left;
            }else {
                return;
            }
        }
        if(parent.val > val){
            parent.left = node;
        }else{
            parent.right = node;
        }

    }

删除元素

 需要使用替换法进行删除，即在它的右子树中寻找中序下的第一个结点，用它的值填补到被 删除节点中

 //删除
    public void remove(int key) {
        TreeNode parent = null;
        TreeNode cur = root;
        while (cur != null) {
            if(cur.val < key) {
                parent = cur;
                cur = cur.right;
            }else if(cur.val > key) {
                parent = cur ;
                cur = cur.left;
            }else {
                removeNode(parent,cur);
                return;
            }
        }
    }
    private void removeNode(TreeNode parent,TreeNode cur) {
        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;
            }if(cur == parent.left) {
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        }else {
            //cur.left！=null&&cur.right!=null,
            //那么就在cur的左边找到最大值，或者cur的右边找到最小值来替换该元素
            TreeNode target = cur.right;
            TreeNode targetP = cur;
            while (target.left != null) {
                targetP = target;
                target = target.left;
            }
            cur.val = target.val;
            if(target == targetP.left) {
                targetP.left = target.right;
            }else {
                targetP.right = target.right;
            }
        }
    }

性能分析:

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：
​最差情况下，二叉搜索树退化为单支树，其平均比较次N数为：