ceiling的实现
ceiling()则与floor()相反,它做的是向下取整,即找到大于等于key的最小结点。但是两者的实现思路是一致的,只要将上面的左变为右,小于变为大于就行了:
/**
* Returns the smallest key in the symbol table greater than or equal to {@code key}.
*
* @param key the key
* @return the smallest key in the symbol table greater than or equal to {@code key}
* @throws NoSuchElementException if there is no such key
* @throws IllegalArgumentException if {@code key} is {@code null}
*/
public Key ceiling(Key key) {
if(key == null) {
throw new IllegalArgumentException("argument to ceiling() is null");
}
if(isEmpty()) {
throw new NoSuchElementException("called ceiling() with empty symbol table");
}
Node x = ceiling(root, key);
if(x == null) {
return null;
} else {
return x.key;
}
}
private Node ceiling(Node x, Key key) {
if(x == null) {
return null;
} else {
int cmp = key.compareTo(x.key);
if(cmp == 0) {
return x;
} else if(cmp < 0) {
Node t = ceiling(x.left, key);
if (t != null) {
return t;
} else {
return x;
}
} else {
return ceiling(x.right, key);
}
}
}
|