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

Question

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

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

So my questions are:

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

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

I am going to include a sample AVL tree that you can refer to if it helps answer the question.

Thanks!

Answer 1

Your question really comes down to the following: "How is the term" rank "generally defined in relation to the AVL tree?" (and, possibly, as select is usually defined).

At least since I saw the term used, “rank” means the position among the nodes in the tree — that is, how many nodes are left. Usually you are assigned a pointer to a node (or perhaps a key value), and you need to count the number of nodes on the left.

“Select” is basically the opposite: you are given a certain rank and you need to get a pointer to the specified node (or the key for this node).

Two notes: firstly, since none of them modifies the tree at all, it does not matter what form of balancing is used (for example, AVL versus red / black); in this case, a tree that has no balancing at all is equivalent. Secondly, if you need to do this often, you can significantly increase the speed by adding an additional field to each node record, how many nodes are left.

Answer 2

The rank is the number of nodes in the left substring plus one, and is calculated for each node. I believe that rank is not a concept specific to AVL trees - it can be calculated for any binary tree.

The choice is simply the opposite of rank. The rank is set, and you must return the node corresponding to this rank.

The following code will calculate the rank:

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

Answer 3

Here is the code I wrote and worked great for AVL Tree to get the rank of a specific value. the only difference is that you used the node parameter as the parameter, and I used the parameter key. You can change this as your own path. Code example:

  public int rank(int data){ return rank(data,root); } private int rank(int data, AVLNode r){ int rank=1; while(r != null){ if(data<r.data) r = r.left; else if(data > r.data){ rank += 1+ countNodes(r.left); r = r.right; } else{ r.rank=rank+countNodes(r.left); return r.rank; } } return 0; } 

[NB] If you want to start your rank with 0, then initialize the variable rank = 0. you definitely should have implemented the countNodes () method to execute this code.

Answer 4

Here is what I did. In my program, the rank of an element is defined as 1+ (there are no elements that exceed this element). Here you can see that the element should not be present in the tree.

Algorithm for rank search:

1. In the tree structure, the absence of elements in the subtree, including the root, is tracked. Thus, the head of the tree will contain the complete elements in the tree.

2. Map the element to node, if it is smaller than node, then there are (1 + no.of elements in the right child element) that are larger than the key element. Add it to the generic and recursively search for the item in the left child.

3.If the element is larger than the root of the node, then just find the element recursively in the right child element (there is no need to add anything, since we neglect the left tree, in which all elements are smaller than the given key)

4. Build the algorithm when you find that the element has reached zero.

The given program returns no elements exceeding the given key. 1+ return value is a rank.

code snippet:

 int AVLUtils::rank(Node *root,long long val) { int n_ele_greater=0; int rank =0; if(root == NULL) return 0; if(val < root->key) { n_ele_greater = 1+this->n_elements(root->right_child)+this->rank(root->left_child,val); } else if(val > root->key) { n_ele_greater=this->rank(root->right_child,val); } else if(val == root->key) { return(this->n_elements(root->right_child)); } return(n_ele_greater); } 

Hope this helps :)