前言:
二叉搜索树的查找效率代表了其插入,删除的操作的性能,这次通过模拟实现二叉搜索树,增加对其底层实现的认识。
值得提到的一点:
二叉搜索树的插入,和查找功能很易实现,本篇作为学习笔记,重点了解其删除功能的实现。(代码在最后)
删除功能:
如何找到待删除的结点?可以通过创建一个cur指针,和一个parent指针(用来指向cur的父亲结点),cur通过二叉搜索树的性质(左结点的值 < 根节点的值 < 右结点的值)遍历二叉搜索树,找到待删除元素后分以下三大种情况:
1.cur.left == null;
满足以上条件继续分为,cur == root、cur != root即cur是否为parent的左节点或右结点;
2.cur.right == null;
满足以上条件继续分为,cur == root、cur != root即cur是否为parent的左节点或右结点;
3.cur.left != null && cur.right != null;(难点)
此时需要用替代法进行删除,替代法删除有以下两种方法:(任选一种即可,本篇代码实现选用第一种)
- 在cur的右边找到最小值,并且若能找到这个最小值,这个最小值点一定不存在左子树;
- 在cur的左边找到最大值,并且若能找到这个最大值,这个最大值点一定不存在右子树;
最后通过target(需要被替换的结点)和targetParent(target的父亲结点)两个指针来进行删除操作。
感觉有点懵?来看下方图解:
代码实现:
public class BinarySearchTree {
static class TreeNode{
TreeNode left;
TreeNode right;
int val;
public TreeNode(int val){
this.val = val;
}
}
TreeNode root = null;
//查找结点
public TreeNode sreach(int key){
TreeNode cur = root;
while(cur != null){
if(cur.val > key){
cur = cur.left;
}else if(cur.val < key){
cur = cur.right;
}else{
return cur;
}
}
return null;
}
//插入结点
public boolean insert(int key){
if(root == null){
root = new TreeNode(key);
return true;
}
TreeNode cur = root;
TreeNode parent = root;
while(cur != null){
parent = cur;
if(cur.val > key){
cur = cur.left;
}else if(cur.val < key){
cur = cur.right;
}else{
return false;
}
}
if(parent.val > key){
parent.left = new TreeNode(key);
}else{
parent.right = new TreeNode(key);
}
return true;
}
//删除结点
public void remove(int key){
TreeNode cur = root;
TreeNode parent = root;
while(cur != null){
if(cur.val > key){
parent = cur;
cur = cur.left;
}else if(cur.val < key){
parent = cur;
cur = cur.right;
}
else{//找到了,并删除
removeNode(cur,parent);
return;
}
}
}
private void removeNode(TreeNode cur, TreeNode parent){
//分三大种情况: 1.cur.left == null
if(cur.left == null){
if(cur == root){
root = cur.right;
}else if(parent.left == cur){
parent.left = cur.right;
}else if(parent.right == cur){
parent.right = cur.right;
}
//第二大种情况:2.cur.right == null
}else if(cur.right == null){
if(cur == root){
root = cur.left;
}else if(parent.left == cur){
parent.left = cur.left;
}else if(parent.right == cur){
parent.right = cur.left;
}
}
else{
/**
* 第三大种情况:cur两边都不为空
* 可以使用替换法进行删除,有以下两种替换方式(任意一种即可)
* 1.在cur的右边找最小值,并且若能找到这个最小值,这个最小值点一定不存在左子树
* 2.在cur的左边找最大值,并且若能找到这个最小值,这个最大值点一定不存在右子树
* 以下代码通过方法1实现
* 通过target和targetParent来确定要替换的结点
*/
TreeNode targetParent = cur;
TreeNode target = cur.right;
while(target.left != null){
targetParent = target;
target = target.left;
}
cur.val = target.val;
//分两种情况
if(targetParent.left == target){
targetParent.left = target.right;
}else{
targetParent.right = target.right;
}
}
}
//中序遍历打印二叉树
public void Print(TreeNode root){
if(root == null){
return;
}
Print(root.left);
System.out.print(root.val);
Print(root.right);
}
}