/**
* Return the kth smallest key in the symbol table.
*
* @param k the order statistic
* @return the kth smallest key in the symbol table
* @throws IllegalArgumentException unless k is between 0 and n-1
*/
public Key select(int k) {
if (k < 0 || k >= size()) {
throw new IllegalArgumentException("called select() with invalid argument: " + k);
} else {
Node x = select(root, k);
return x.key;
}
}
// Return the key of rank k.
public Node select(Node x, int k) {
if(x == null) {
return null;
} else {
int t = size(x.left);
if(t > k) {
return select(x.left, k);
} else if(t < k) {
return select(x.right, k);
} else {
return x;
}
}
}
/**
* Return the number of keys in the symbol table strictly less than key.
*
* @param key the key
* @return the number of keys in the symbol table strictly less than key
* @throws IllegalArgumentException if key is null
*/
public int rank(Key key) {
if (key == null) {
throw new IllegalArgumentException("argument to rank() is null");
} else {
return rank(key, root);
}
}
public int rank(Key key, Node x) {
if(x == null) {
return 0;
} else {
int cmp = key.compareTo(x.key);
if(cmp < 0) {
return rank(key, x.left);
} else if(cmp > 0) {
return 1 + size(x.left) + rank(key, x.right);
} else {
return size(x.left);
}
}
}
欢迎光临 电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/) | Powered by Discuz! 7.0.0 |