计算二叉搜索树中节点的排名

Question

如果二叉搜索树中的每个节点都存储其权重（子树中的节点数），那么在查找节点时，计算给定节点的排名（在排序列表中的索引）的有效方法是什么？

- dissem

Answer 1

从零开始排名。随着二进制搜索从根节点向下进行，将跳过的所有左子树（包括找到的节点的左子树）的大小相加。

也就是说，当搜索向左（从父节点到左子节点）时，它不会发现比所搜索的项更小的新值，因此等级保持不变。当它向右走时，父节点以及所有左子树中的节点都比所搜索的项小，因此添加一加左子树的大小。当它找到所搜索的项时，包含该项的节点的左子树中的任何项都比它小，因此将其添加到等级中。

将所有这些放在一起：

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。

- Gene

---

这太棒了！ - Hormigas

你的解决方案简单而干净。我曾尝试通过在每个节点上维护所有子节点计数来解决这个问题。那样太复杂了，容易出错。相反，像你一样只维护左子树的大小要容易得多。谢谢！ - Anwar Shaikh

Answer 2

由于每个节点都有一个存储其权重的字段，因此首先需要实现一个名为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);  
    }

- Jade Tang

---

最后一个else语句不正确。只有根节点的左子树包含小于搜索值的项。 - Gene

Answer 3

这取决于二叉搜索树的实现方式，但我相信你可以通过递归来解决它。

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);
}

- Joe Drool