如果二叉搜索树中的每个节点都存储其权重(子树中的节点数),那么在查找节点时,计算给定节点的排名(在排序列表中的索引)的有效方法是什么?
如果二叉搜索树中的每个节点都存储其权重(子树中的节点数),那么在查找节点时,计算给定节点的排名(在排序列表中的索引)的有效方法是什么?
从零开始排名。随着二进制搜索从根节点向下进行,将跳过的所有左子树(包括找到的节点的左子树)的大小相加。
也就是说,当搜索向左(从父节点到左子节点)时,它不会发现比所搜索的项更小的新值,因此等级保持不变。当它向右走时,父节点以及所有左子树中的节点都比所搜索的项小,因此添加一加左子树的大小。当它找到所搜索的项时,包含该项的节点的左子树中的任何项都比它小,因此将其添加到等级中。
将所有这些放在一起:
int rank_of(NODE *tree, int val) {
int rank = 0;
while (tree) {
if (val < tree->val) // move to left subtree
tree = tree->left;
else if (val > tree->val) {
rank += 1 + size(tree->left);
tree = tree->right;
}
else
return rank + size(tree->left);
}
return NOT_FOUND; // not found
}
这将返回基于零的等级。如果您需要基于1的等级,则将 rank
初始化为1而不是0。
由于每个节点都有一个存储其权重的字段,因此首先需要实现一个名为size()的方法,该方法返回节点子树中节点数:
private int size(Node x)
{
if (x == null) return 0;
else return x.N;
}
public int rank(Node key)
{ return rank(key,root) }
private int rank(Node key,Node root)
{
if root == null
return 0;
int cmp = key.compareTo(root);
// key are smaller than root, then the rank in the whole tree
// is equal to the rank in the left subtree of the root.
if (cmp < 0) {
return rank(key, root.left)
}
//key are bigger than root,the the rank in the whole tree is equal
// to the size of subtree of the root plus 1 (the root) plus the rank
//in the right sub tree of the root.
else if(cmp > 0){
return size(root.left) + 1 + rank(key,root.right);
}
// key equals to the root, the rank is the size of left subtree of the root
else return size( root.left);
}
else
语句不正确。只有根节点的左子树包含小于搜索值的项。 - Gene这取决于二叉搜索树的实现方式,但我相信你可以通过递归来解决它。
public int rank(Key key){
return rank(root, key);
}
private int rank(Node n, Key key){
int count = 0;
if (n == null)return 0;
if (key.compareTo(n.key) > 0) count++;
return count + rank(n.left, key) + rank(n.right, key);
}