/**
* 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;
}
}
/**
* 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;
}
}
欢迎光临 电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/) | Powered by Discuz! 7.0.0 |