What is "rank" in a binary search tree and how can it be useful?

Question

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.

Questions:
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.

Answer 1

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.

Answer 2

The Rank of node in tree tells us how many nodes in the tree have key values less than that node in the Tree. So a node of Rank 5 will have 4 other nodes in the tree with Key value less than that specific Node. This can be used in algorithms to find '$K$'th smallest item in a tree and will run in $\log(n)$ ($O(1)$ if you already maintain the sizes) running time.

The size of a node : is the sum of all nodes in Left subTree + sum of all nodes in right SubTree + 1 (for the given node) -- There will be slight complications if you the node is on the rightSubtree of its parent. In this case, choose rank as Rank of parent + size of leftSubTree.

So if I want to find the rank of a node, I will need to find the "size" of leftSubTree (as all of them will be smaller than current node) + 1.

int rank(int key, Node node) {
        if (node == null) return 0; 
        if      (key < node.key) return rank(key, node.left); 
        else if (key > node.key) return 1 + size(node.left) + rank(key, node.right); 
        else              return size(node.left);
    } 

It is not same as depth. Depth of a Node is the number of "levels" between the root of the tree and that node. This will be equal to height of root - height of Node.

For further reading, check Algorithms 4th Edition By Robert Sedgewick and Kevin Wayne.

Answer 3

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.

Answer 4

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

and,

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.