删除操作
删除操作是二叉查找树中最难实现的方法，在实现它之前，我们先来看一下如何删除二叉查找树中最小的结点。
为了实现deleteMin()，我们首先要找到这个最小的节点，很明显这个结点就是树中最左边的结点A，我们重点关注的是怎么删除这个结点A。在我们下面这幅图中结点E的左子树中的两个结点A和C都是小于结点E的，我们只需要将结点E的左链接由A变为C即可，然后A就会自动被GC回收。最后一步就是更新节点的size了。
二叉树deletetMin流程图
具体的实现代码如下：
/**
* Removes the smallest key and associated value from the symbol table.
*
* @throws NoSuchElementException if the symbol table is empty
*/
public void deleteMin() {
if (isEmpty()) {
throw new NoSuchElementException("Symbol table underflow");
} else {
root = deleteMin(root);
// assert check(); // Check integrity of BST data structure.
}
}
private Node deleteMin(Node x) {
if(x.left == null) {
return x.right;
} else {
x.left = deleteMin(x.left);
x.size = size(x.left) + size(x.right) + 1;
return x;
}
}
删除最大的结点也是一个道理，我就不重复解释了：
/**
* Removes the largest key and associated value from the symbol table.
*
* @throws NoSuchElementException if the symbol table is empty
*/
public void deleteMax() {
if (isEmpty()) {
throw new NoSuchElementException("Symbol table underflow");
} else {
root = deleteMax(root);
// assert check(); // Check integrity of BST data structure.
}
}
private Node deleteMax(Node x) {
if (x.right == null) {
return x.left;
} else {
x.right = deleteMax(x.right);
x.size = size(x.left) + size(x.right) + 1;
return x;
}
}
接下来我们结合下图来一步步完整地看一下整个删除操作的过程，首先还是和上面一样我们要找到需要删除的结点E，然后我们要在E的右子树中找到最小结点，这里是H，接下来我们就用H替代E就行了。为什么可以直接用H替代E呢？因为H结点大于E的左子树的所有结点，小于E的右子树中的其它所有结点，所以这一次替换并不会破坏二叉树的特性。
二叉树delete流程图
实现代码如下，这里解释一下执行到了// find key后的代码，这个时候会出现三种情况：
- 结点的右链接为空，这个时候我们直接返回左链接来替代删除结点。
- 结点的左链接为空，这个时候返回右链接来替代删除结点。
- 左右链接都不为空的话，就是我们上图中的那种情形了。
/**
* Removes the specified key and its associated value from this symbol table
* (if the key is in this symbol table).
*
* @param key the key
* @throws IllegalArgumentException if key is null
*/
public void delete(Key key) {
if (key == null) {
throw new IllegalArgumentException("argument to delete() is null");
} else {
root = delete(root, key);
// assert check(); // Check integrity of BST data structure.
}
}
private Node delete(Key key) {
if(x == null) {
return null;
} else {
int cmp = key.compareTo(x.key);
if(cmp < 0) {
x.left = delete(x.left, key);
} else if(cmp > 0) {
x.right = delete(x.right, key);
} else {
// find key
if(x.right == null) {
return x.left;
} else if(x.left == null) {
return x.right;
} else {
Node t = x;
x = min(t.right);
x.right = deleteMin(t.right);
x.left = t.left;
}
}
// update links and node count after recursive calls
x.size = size(x.left) + size(x.right) + 1;
return x;
}
}
|
