select与rank的实现
select的实现
上面我们的get()操作是通过指定的key去在二叉查找树中查询其关联的结点，二叉查找树的另外一个优点就是它可以一定程度上保证数据的有序性，所以我们可以较高效的去查询第n小的数据。
首先我们来思考一个问题：怎么知道一个二叉查找树中小于指定结点的子结点的个数？这一点根据二叉查找树的性质-左子树中的结点都要小于根结点很容易实现，我们只需要统计左子树的大小就行了。结合下面这幅图，以查找二叉树第4小的结点我们来看一下select操作的具体流程。
依次遍历二叉树，我们来到了下图中的E结点，E结点的左子树有2个结点，它是二叉树中第3小的结点，所以我们可以判断出要查找的结点肯定在E结点的右子树中。由于我们要查找第4小的结点，而E又是二叉树中第3小的结点，所以我们要查找的这个结点接下来肯定要满足一个特征：E的右子树中只有0个比它更小的结点，即右子树中最小的结点H。
二叉树select流程图
select的实现如下，实际就是根据左子树的结点数目来判断当前结点在二叉树中的大小。
/**
* 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;
}
}
}
rank就是查找指定的键key在二叉树中的排名，实现代码如下，思想和上面一致我就不重复解释了。
/**
* 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);
}
}
}
|
