floor和ceiling的实现
floor的实现
floor()要实现的就是向下取整，我们来分析一下它的执行流程：
- 如果指定的键key小于根节点的键，那么小于等于key的最大结点肯定就在左子树中了。
- 如果指定的键key大于根结点的键，情况就要复杂一些，这个时候要分两种情况：1>当右子树中存在小于等于key的结点时，小于等于key的最大结点则在右子树中；2>反之根节点自身就是小于等于key的最大结点了。
二叉树floor流程图
具体实现代码如下：
/**
* Returns the largest key in the symbol table less than or equal to key.
*
* @param key the key
* @return the largest key in the symbol table less than or equal to key
* @throws NoSuchElementException if there is no such key
* @throws IllegalArgumentException if key is null
*/
public Key floor(Key key) {
if (key == null) {
throw new IllegalArgumentException("argument to floor() is null");
}
if (isEmpty()) {
throw new NoSuchElementException("called floor() with empty symbol table");
}
Node x = floor(root, key);
if (x == null) {
return null;
} else {
return x.key;
}
}
private Node floor(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) {
return floor(x.left, key);
} else {
Node t = floor(x.right, key);
if(t != null) {
return t;
} else {
return x;
}
}
}
}
|
