二叉搜索樹中節點的計算等級

Question

如果二叉搜索樹中的每個節點存儲其權重（其子樹中的節點數），那麼計算給定節點的等級（其索引在排序列表中），因爲我在樹中搜索它？

Answer 1

從零開始排名。隨着二進制搜索從根開始向下進行，添加搜索跳過的所有左側子樹的大小，包括找到的節點的左側子樹。

即，當搜索向左（從父母到左孩子）時，它發現沒有比搜索到的項目少的新值，因此排名保持不變。當它正確時，父節點加左子樹中的所有節點都小於搜索的項目，所以加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.

Answer 2

由於每個節點都有一個字段存儲的重量時，首先應該實現一個方法調用大小（），它返回一個節點的substree節點的數量：

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

Answer 3

取決於BST實現，但我相信您可以遞歸解決它。

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