Rank of a node in a order-statistics tree

Question

In a order-statistics tree, what is the rank of a node?

Is it given by

rank = x.left.size + 1

or by this function?

OS-RANK(T, x)
{
    r = left.size + 1
    y = x

    while (y != T.root)
    {
        if (y == y.p.right) {
            r = r + y.p.left.size + 1
        }
    }

    return r
}

I'm really confused, because I think it should be simply x.left.size + 1, since that should be the position of x in the inorder tree walk of the tree.

Answer 1

Each node in an order statistic tree just stores the number of nodes in its left subtree (and, optionally, in its right subtree). If you just read off this value, you won't necessarily know the rank of the node because you don't know where in the order statistic tree that node lies. For example, if your node is in the right subtree of the root node, you will need to factor in all of the nodes to the left of the root into the rank.

If you have a node and want to know its rank, you can compute it by using a modified BST lookup. In pseudocode:

function rank(node root, node n):
    /* If n is the root of the tree, its rank is the number of nodes in its
     * left subtree.
     */
    if root.value == n.value:
        return n.leftSize

    /* Belongs in right subtree: */
    else if root.value < n.value:
        return rank(root.left, n)

    /* Belongs in left subtree: */
    else:
        return root.leftSize + 1 + rank(root.right, n)

Hope this helps!

Answer 2

Everything thing in your code is correct, but you have to add one more command to update value of pointer "y" after each iterations. y = y. p;

The correct algorithm will be

OS-RANK(T, x) {
r = left.size + 1;
y = x ;
while (y != T.root) 
{ 
    if (y == y.p.right) 
    { 
        r = r + y.p.left.size + 1 
    } 
y = y. p;
} 
return r 
}