How to find the rank of a node in an AVL tree?

Question

I need to implement two rank queries [rank(k) and select(r)]. But before I can start on this, I need to figure out how the two functions work.

As far as I know, rank(k) returns the rank of a given key k, and select(r) returns the key of a given rank r.

So my questions are:

1.) How do you calculate the rank of a node in an AVL(self balancing BST)?

2.) Is it possible for more than one key to have the same rank? And if so, what woulud select(r) return?

I'm going to include a sample AVL tree which you can refer to if it helps answer the question.

Thanks!

Solution 1

Your question really boils down to: "how is the term 'rank' normally defined with respect to an AVL tree?" (and, possibly, how is 'select' normally defined as well).

At least as I've seen the term used, "rank" means the position among the nodes in the tree -- i.e., how many nodes are to its left. You're typically given a pointer to a node (or perhaps a key value) and you need to count the number of nodes to its left.

"Select" is basically the opposite -- you're given a particular rank, and need to retrieve a pointer to the specified node (or the key for that node).

Two notes: First, since neither of these modifies the tree at all, it makes no real difference what form of balancing is used (e.g., AVL vs. red/black); for that matter a tree with no balancing at all is equivalent as well. Second, if you need to do this frequently, you can improve speed considerably by adding an extra field to each node recording how many nodes are to its left.

Solution 2

Rank is the number of nodes in the Left sub tree plus one, and is calculated for every node. I believe rank is not a concept specific to AVL trees - it can be calculated for any binary tree.

Select is just opposite to rank. A rank is given and you have to return a node matching that rank.

The following code will perform rank calculation:

void InitRank(struct TreeNode *Node)
{
        if(!Node)
        {
                return;
        }
        else
        {       Node->rank = 1 + NumeberofNodeInTree(Node->LChild);
                InitRank(Node->LChild);
                InitRank(Node->RChild);
        }

}


int NumeberofNodeInTree(struct TreeNode *Node)
{
        if(!Node)
        {
                return 0;
        }
        else
        {
                  return(1+NumeberofNodeInTree(Node->LChild)+NumeberofNodeInTree(Node->RChild));
        }
}