二叉搜索树(又称二叉排序树),它可以是一棵空树,也可以是一棵具有以下性质的二叉树:
- 若它的左子树不为空,则左子树上所有的节点的值都小于根节点的值
- 若它的右子树不为空,则右子树上所有的节点的值都大于根节点的值
- 它的左子树和右子树也都为二叉搜索树
通过性质,我们也容易得出一个结论:
可以通过中序遍历来判断这棵二叉树是否为搜索二叉树,如果结果有序,则是搜索二叉树
示例图:
在进行下面搜索二叉树的几个操作实现之前,我们先写一个基本的搜索二叉树类,在这个类中来实现我们的操作
实现代码:
public class BinarySearchTree { // 将节点直接定义在二叉树类的内部 static class TreeNode{ public int val; public TreeNode left; public TreeNode right; public TreeNode(int val){ this.val=val; } } // 查找 // 插入 // 删除 }
思想:
- 若节点不为空:
- 如果根节点 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; }
思想:
- 若跟节点为空,则在根节点插入
- 若不为空,则找到数值应该插入的叶子节点,来进行判断插入
实现代码:
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; } }
思想:
- 先通过查找找到要删除的节点,再设置一个节点记为其父节点
- 找到删除的节点之后
- 若待删除的结点的左节点为空
- 如果待删除结点为根节点,让根节点为右子树即可
- 如果待删除结点不是根节点,且为父节点的左子树,只要让父节点的左子树为待删除结点的右子树即可
- 如果待删除结点不是根节点,且为父节点的右子树,只要让父节点的右子树为待删除结点的右子树即可
- 若待删除的结点的右结点为空
- 如果待删除结点为根节点,让根节点为左子树即可
- 如果待删除结点不是根节点,且为父节点的左子树,只要让父节点的左子树为待删除结点的左子树即可
- 如果待删除结点不是根节点,且为父节点的右子树,只要让父节点的右子树为待删除结点的左子树即可
- 若待删除的结点的左右节点都不为空,那么使用替换法,找到左子树的最大值或者右子树的最小值,来将待删除结点给替换,这样,我们只要再将将其替换的结点删除即可
实现代码:
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; } } }
通过分析,我们发现删除和插入操作之前都必须先查找,故查找效率代表了二叉搜索树的这几个操作的性能
以下来分析下两种特殊的搜索二叉树的查找的时间复杂度
完全二叉树(时间复杂度为:O(logN)
)
单支二叉树(时间复杂度为:O(N)
)
如果是一棵单支树的话,时间复杂度其实就达到了 O(N),为了优化的更快则出现了:AVL 树、红黑树