79 views

Consider the following What is the rank(index) of the node $50?$

in DS | 79 views
0
Is it 6?
0
how can you explain, I never heard about the rank of the index?
0

I found it here pls check  & varify.

0
thanks
0

shouldnt the rank of 50 be 5 since there are 5 keys that are smaller than 50?

0
answer is $6$
0
Rank of a node is its position in a sorted list of the nodes....
0
so , in sorted list the node will be present after all of its left children , so count no of left children and add 1 that will be the position of the node(of which u want to find rank)  in sorted list..

so here rank of 50 is 6
0

if I want to find the rank of $60?$

0
rank of 60 is 8
0

@lakshman use this algo u will get the rank of the node u want

int rank_of(NODE *tree, int val) {
int rank = 1;
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);
}
}
0

Manas Mishra rank of 60 should be 7 right?

0
@somoshree no it will be 8
0
@smoshree if u will go with zero based rank thn answer will be 7 bt if u will go with 1 based rank thne answer willl be 8 , we generally go with 1 based rank
0

Sort the list and you can easily find the rank.

 10 20 30 40 45 50 55 60 65 70 75

1           2              3         4          5            6          7           8          9             10           11

0
Why we take indexing from $1$, why not from $0?$
0
we can start with 0. But for the Rank of any node then we have to add one.
0
@lakshman we can do both it depends upon u which to take , check the program i have commented if u want indexing from 0 initialize rank =0 , bt generally we use 1 based rank
0
@dilip its not the case that we have to add one for rank ,

suppose u have started indexing from 0, then ( assuming the tree is right skew) rank of root is 0
0
In right skewed tree rank is $0?$
0
@lakshman

in right skewed tree rank of root is zero if u use 0 based rank