I am having a bit of trouble wrapping my mind around what a ranked binary search tree is and why having a rank is important. I am hoping that someone can clarify a few things for me.

What I have looked into:
From what I have read, a ranked binary search tree is a tree where each node has a variable "rank" attached to it.

In the question here, someone states that in order to determine the rank of a node in a binary search tree you can do the following:

Start the rank at zero. As the binary search proceeds down from the root, sum up the sizes of all the left subtrees that the search skips by. Also include the nodes along the path less than the searched item. These are just the parents of right children on the search path.

The rank seems like it is just a number that reflects how many nodes it takes (plus one for the root) to get to a particular node in a tree. Is that right? It didn't seem right to me only because that seems like that would just make the rank of a node the same as the depth of a node.

Also, what is the difference between "weight" and "rank"? If a node in a particular binary search tree has a weight attached to it, is that just a random value assigned to it by the user/developer?

Lastly, what is the point of having a rank? My first thought is that it can be used to indicate priorities. However, in that case, why wouldn't the developer just use weights?

Other things:
I also took a look at the site here. It explains how to calculate rank, but I'm still not convinced I understand the concept yet.

Thanks for any help.


According to this book (Chapter 3.2), a node in a BST has rank $k$ if precisely $k$ other keys in the BST are smaller. So, if you order all the BST nodes according to their keys, then each node with rank $k$ will take $k$-th place.

| cite | improve this answer | |

I think it depends on if you are doing rank union by size or by height. The rank of a node using rank union by size may indicate how many nodes are in the subtree of that node. The rank of a node using rank union by height would indicate how many edges are in the path from that node to the furthest leaf in that node's subtree.

| cite | improve this answer | |

Adding to the answer by HEKTO above, to calculate the rank in a BST with unique elements,

the rank of a left child = rank of the parent - 1 - number of elements in its right subtree


the rank of a right child = rank of the parent + 1 + number of elements in its left subtree.

It can be used to find any general $i^{th}$ order statistic in the BST in O(h) time, i.e. O(log n) time if the tree is balanced. So it is useful to find the median of the elements or ith largest/smallest element among the elements.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.