Calculating the rank of a node in a binary search tree

Question

If each node in a binary search tree retains its weight (the number of nodes in its subtree), what would be an effective method for calculating the rank of a given node (index in a sorted list), how do I look for it in a tree?

Answer 1

Run the rank to zero. When the binary search continues from the root, add the sizes of all the left subtrees that the search will scan, including the left subtree of the found node.

Ie, when the search goes to the left (from the parent to the left child), it does not detect new values ​​less than the found element, so the ranking remains unchanged. When it goes right, the parent plus all the nodes in the left subtree are smaller than the item found, so add one plus the size of the left subtree. When he finds the item he is looking for. all elements in the left subtree of the node containing the element are smaller than it, so add this to the rank.

Putting it all together:

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
}

Returns rank zero. If you need 1-based, then initialize rankto 1 instead of 0.

Answer 2

Since each node has a field in which its weight is stored, you must first implement the size of the method () call, which returns the number of nodes in the node substring:

private int size(Node x)
{
if (x == null) return 0;
else return x.N;
} 

node

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