【数据结构 Java版】了解二叉搜索树

x33g5p2x  于2021-11-17 转载在 Java  
字(2.3k)|赞(0)|评价(0)|浏览(322)

1. 概念

二叉搜索树(又称二叉排序树),它可以是一棵空树,也可以是一棵具有以下性质的二叉树:

  • 若它的左子树不为空,则左子树上所有的节点的值都小于根节点的值
  • 若它的右子树不为空,则右子树上所有的节点的值都大于根节点的值
  • 它的左子树和右子树也都为二叉搜索树

通过性质,我们也容易得出一个结论:

可以通过中序遍历来判断这棵二叉树是否为搜索二叉树,如果结果有序,则是搜索二叉树

示例图:

2. 操作

在进行下面搜索二叉树的几个操作实现之前,我们先写一个基本的搜索二叉树类,在这个类中来实现我们的操作

实现代码:

public class BinarySearchTree {
	// 将节点直接定义在二叉树类的内部
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

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

    // 查找
    
    // 插入
        
    // 删除
}

2.1 查找

思想:

  • 若节点不为空:

  • 如果根节点 key == 查找值 key,返回 true

  • 如果根节点 key > 查找值 key,在其左子树继续查找

  • 如果根节点 key < 查找值 key,在其右子树继续查找

  • 否则返回 false

实现代码:

// 查找
public TreeNode search(TreeNode root,int key){
    while(root!=null){
        if(root.val==key){
            return root;
        }else if(root.val>key){
            root=root.left;
        }else{
            root=root.right;
        }
    }
    return null;
}

2.2 插入

思想:

  • 若跟节点为空,则在根节点插入
  • 若不为空,则找到数值应该插入的叶子节点,来进行判断插入

实现代码:

public void insertTree(int key){
    if (root==null){
        root=new TreeNode(key);
    }
    TreeNode cur=root;
    TreeNode parent=null;
    while(cur!=null){
        if(cur.val<key){
            parent=cur;
            cur=cur.right;
        }else{
            parent=cur;
            cur=cur.left;
        }
    }
    TreeNode node=new TreeNode(key);
    if(parent.val<key){
        parent.right=node;
    }else{
        parent.left=node;
    }
}

2.3 删除

思想:

  • 先通过查找找到要删除的节点,再设置一个节点记为其父节点

  • 找到删除的节点之后

  • 若待删除的结点的左节点为空

  • 如果待删除结点为根节点,让根节点为右子树即可

  • 如果待删除结点不是根节点,且为父节点的左子树,只要让父节点的左子树为待删除结点的右子树即可

  • 如果待删除结点不是根节点,且为父节点的右子树,只要让父节点的右子树为待删除结点的右子树即可

  • 若待删除的结点的右结点为空

  • 如果待删除结点为根节点,让根节点为左子树即可

  • 如果待删除结点不是根节点,且为父节点的左子树,只要让父节点的左子树为待删除结点的左子树即可

  • 如果待删除结点不是根节点,且为父节点的右子树,只要让父节点的右子树为待删除结点的左子树即可

  • 若待删除的结点的左右节点都不为空,那么使用替换法,找到左子树的最大值或者右子树的最小值,来将待删除结点给替换,这样,我们只要再将将其替换的结点删除即可

实现代码:

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){
            removeNode(cur,parent);
        }else{
            parent=cur;
            cur=cur.left;
        }
    }
}
public void removeNode(TreeNode cur,TreeNode parent){
    if(cur.left==null){
        if(cur==root){
            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(cur==root){
            root=cur.left;
        } else if(cur==parent.left){
            parent.left=cur.left;
        } else if(cur==parent.right){
            parent.right=cur.left;
        }
    }else{
        TreeNode tp=cur;
        TreeNode target=cur.right;
        while (target.left!=null) {
            tp = target;
            target = target.left;
        }
        cur.val=target.val;
        if(tp.left==target){
            tp.left=target.right;
        }else{
            tp.right=target.right;
        }
    }
}

3. 性能分析及优化

通过分析,我们发现删除和插入操作之前都必须先查找,故查找效率代表了二叉搜索树的这几个操作的性能

以下来分析下两种特殊的搜索二叉树的查找的时间复杂度

  • 完全二叉树(时间复杂度为:O(logN)

  • 单支二叉树(时间复杂度为:O(N)

如果是一棵单支树的话,时间复杂度其实就达到了 O(N),为了优化的更快则出现了:AVL 树红黑树

相关文章