algorithm - Rank of a node in a order-statistics tree -

in order-statistics tree, rank of node?

is given by

rank = x.left.size + 1 

or 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 confused, because think should x.left.size + 1, since should position of x in inorder tree walk of tree.

each node in order statistic tree stores number of nodes in left subtree (and, optionally, in right subtree). if read off value, won't know rank of node because don't know in order statistic tree node lies. example, if node in right subtree of root node, need factor in of nodes left of root rank.

if have node , want know rank, can compute using modified bst lookup. in pseudocode:

function rank(node root, node n):     /* if n root of tree, rank number of nodes in      * 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 helps!