@TOC
什么是搜索树？
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
1.若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2.若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
3.它的左右子树也分别为二叉搜索树
查找操作
这里我们定义一个cur指针用来遍历搜索树。
//查找key是否存在
public TreeNode search(int key) {
TreeNode cur = root;
while(cur != null) {
if(cur.key == key) {
return cur;
}else if(cur.key > key){
cur = cur.left;
}else {
cur = cur.right;
}
}
return null;
}插入操作
- 如果树为空树，即根 == null，直接插入
- 如果树不是空树，按照查找逻辑确定插入位置，插入新结点
定义一个cur去遍历搜索树，parent用来记录cur的上一位置，如果该结点大于key则遍历左子树，小于遍历右子树，等于直接退出(搜索树不允许出现相同的数值)。
public boolean insert(int key) {
if(root == null) {
root = new TreeNode(key);
}
TreeNode prev = null;
TreeNode cur = root;
while(cur != null) {
if(cur.key == key) {
return false;
}else if(cur.key > key) {
prev = cur;
cur = cur.left;
}else {
prev = cur;
cur = cur.right;
}
}
if(prev.key > key) {
prev.left = new TreeNode(key);
}else {
prev.right = new TreeNode(key);
}
return true;
}删除操作
设待删除结点为 cur, 待删除结点的双亲结点为 parent
分三种情况:
1.cur.left == null
- cur 是 root，则 root = cur.right
- cur 不是 root，cur 是 parent.left，则 parent.left = cur.right
- cur 不是 root，cur 是 parent.right，则 parent.right = cur.right
2.cur.right == null
- cur 是 root，则 root = cur.left
- cur 不是 root，cur 是 parent.left，则 parent.left = cur.left
- cur 不是 root，cur 是 parent.right，则 parent.right = cur.left
3. cur.left != null && cur.right != null
需要使用替换法进行删除，即在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题
第一和第二种情况相对比较简单，改变一下parent的指向即可，我们具体讨论一下第三种情况。
如果我们想从上面的 搜索树 中删除 15，我们可以做一些技巧来将情况减少到情况 1 或情况 2
1.求其右子树的最小值
2.求其左子树的最大值
我们可以发现我们只需要找到右子树的最左的，或者左子树最右的和cur交换即可，不影响搜索树的顺序。
public boolean remove(int key) {
TreeNode prev = null;
TreeNode cur = root;
while(cur != null) {
if(cur.key == key) {
removeChild(prev,cur);
return true;
}else if(cur.key > key) {
prev = cur;
cur = cur.left;
}else {
prev = cur;
cur = cur.right;
}
}
return false;
}
public void removeChild(TreeNode parent,TreeNode cur) {
if(cur.left == null) {
if(cur == root) {
root = root.right;
} else if(cur == parent.left) {
parent.left = cur.right;
}else {
parent.right = cur.right;
}
}else if(cur.right == null) {
if(cur == root) {
root = root.left;
}else if(cur == parent.left) {
parent.left = cur.left;
}else {
parent.right = cur.left;
}
}else {
TreeNode target = cur.right;
TreeNode targetParent = cur;
while(target.left != null) {
targetParent = target;
target = target.left;
}
cur.key = target.key;
if(target == targetParent.left) {
targetParent.left = target.right;
}else {
targetParent.right = target.right;
}
}
}实现
public class BinarySearchTree {
static class TreeNode {
public int key;
public TreeNode left;
public TreeNode right;
public TreeNode(int key) {
this.key = key;
}
@Override
public String toString() {
return "TreeNode{" +
"key=" + key +
'}';
}
}
public TreeNode root;
/**
* 插入一个元素
*/
public boolean insert(int key) {
if(root == null) {
root = new TreeNode(key);
}
TreeNode prev = null;
TreeNode cur = root;
while(cur != null) {
if(cur.key == key) {
return false;
}else if(cur.key > key) {
prev = cur;
cur = cur.left;
}else {
prev = cur;
cur = cur.right;
}
}
if(prev.key > key) {
prev.left = new TreeNode(key);
}else {
prev.right = new TreeNode(key);
}
return true;
}
public void inOrder(TreeNode root) {
if(root == null) {
return;
}
inOrder(root.left);
System.out.println(root.key + " ");
inOrder(root.right);
}
//查找key是否存在
public TreeNode search(int key) {
TreeNode cur = root;
while(cur != null) {
if(cur.key == key) {
return cur;
}else if(cur.key > key){
cur = cur.left;
}else {
cur = cur.right;
}
}
return null;
}
public boolean remove(int key) {
TreeNode prev = null;
TreeNode cur = root;
while(cur != null) {
if(cur.key == key) {
removeChild(prev,cur);
return true;
}else if(cur.key > key) {
prev = cur;
cur = cur.left;
}else {
prev = cur;
cur = cur.right;
}
}
return false;
}
public void removeChild(TreeNode parent,TreeNode cur) {
if(cur.left == null) {
if(cur == root) {
root = root.right;
} else if(cur == parent.left) {
parent.left = cur.right;
}else {
parent.right = cur.right;
}
}else if(cur.right == null) {
if(cur == root) {
root = root.left;
}else if(cur == parent.left) {
parent.left = cur.left;
}else {
parent.right = cur.left;
}
}else {
TreeNode target = cur.right;
TreeNode targetParent = cur;
while(target.left != null) {
targetParent = target;
target = target.left;
}
cur.key = target.key;
if(target == targetParent.left) {
targetParent.left = target.right;
}else {
targetParent.right = target.right;
}
}
}
}
