文章目录
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 树、红黑树