二叉搜索树又称二叉排序树,它是一棵空树 或者 具有以下性质的二叉树:
例如:
注意:插入的位置一定是搜索二叉树的根节点
设待删除的结点为 cur ,待删除结点的双亲结点为 parent
- 如果 cur == root,则root == cur.right
- 如果 cur != root,cur 是parent的左子树,则parent.left == cur.right
- 如果 cur != root,cur 是parent的右子树,则parent.right == cur.right
- 如果 cur == root,则root == cur.left
- 如果 cur != root,cur 是parent的左子树,则parent.left == cur.left
- 如果 cur != root,cur 是parent的右子树,则parent.right == cur.left
需要使用替换法进行删除,用 cur 左子树中的最大值,或者 cur 右子树中的最小值替换掉删除结点,然后删除替换元素。
在找到replace并且替换cur之后,就可以进行如下操作(采用右树找最小值的方法):
- 如果 replace==cur.right ,则 cur.right = replace.right
- 如果 replace==cur.right ,则 replace_parent.left = replace.right
- 注意:
(1)在左子树找最大值时,这个值一定在左子树的最右边,而最右边的这个结点一定没有右子树;
(2)在右子树中找最小值时,这个值一定在右子树最左边。而最左边的这个1结点一定没有左子树;
BinarySearchTree:
public class BinarySearchTree {
public static class Node{
int val;
Node left;
Node right;
public Node(int val){
this.val=val;
}
}
Node root;
//查找
public boolean search(int key){
if(root==null){
return false;
}
Node cur = root;
while(cur!=null){
if(cur.val==key){
return true;
}else if(key<cur.val){
cur=cur.left;
}else{
cur=cur.right;
}
}
return false;
}
//插入
public void insert(int val){
Node node = new Node(val);
if(root==null){
root=node;
}else{
Node parent = null;
Node cur = root;
while(cur!=null){
if(val<cur.val){
parent=cur;
cur=cur.left;
}else{
parent=cur;
cur=cur.right;
}
}
if(val<parent.val){
parent.left=node;
}else{
parent.right=node;
}
}
}
//删除
private void delete_child(Node parent,Node 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;
}else{
if(cur==parent.left){
parent.left=cur.left;
}else{
parent.right=cur.left;
}
}
}else{
Node replace = cur.right;
Node replace_parent=parent;
while(replace.left!=null){
replace_parent=replace;
replace=replace.left;
}
cur.val=replace.val;
if(replace==cur.right){
replace_parent.right=replace.right;
}else{
replace_parent.left=replace.right;
}
}
}
public boolean delete(int key){
if(root==null){
return false;
}
//找到要删除的结点
Node cur = root;
Node parent = null;
while(cur!=null){
if(cur.val==key){
delete_child(parent,cur);
return true;
}else if(key<cur.val){
parent=cur;
cur=cur.left;
}else{
parent=cur;
cur=cur.right;
}
}
return false;
}
}
Test:
public class Test {
public static void main(String[] args) {
BinarySearchTree BST = new BinarySearchTree();
int []arr = {5,3,4,1,7,8,2,6,0,9};
for(int val:arr){
BST.insert(val);
}
boolean ret1 = BST.search(0);
boolean ret2 = BST.delete(5);
}
}