Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
    Tweeted twitter.com/StackCompSci/status/1072234636531646464
2 replaced http://stackoverflow.com/ with https://stackoverflow.com/
source | link

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 herehere, 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.

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.

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.

1
source | link

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

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.