Understanding Rank, Select, and Range in Binary Search Trees

 
Rank, Select, and Range in
Binary Search Trees
 
Notes from Sedgewick
 
Definition of Rank
 
The 
rank
 of a key 
k
 is the number of keys in the BST that are less
than 
k
.
 
Definition of Select
 
The 
Select
 function finds the key with a specified rank
.
 
Select is the inverse of rank
     i = rank(select(i))
     key = select(rank(key))
 
Implementation of Select
 
Create a function computeNDescendants() that sets a value inside the node that records
the number of descendants the node has.
 
 
computeNDescendants(root);
 
Assert(6, root.NDescendants);
Assert(4, root.Left.NDescendants);
Assert(1, root.Left.Left.NDescendants);
 
We will need to call computeNDesendants before
we call one or more select functions.
 
Implementation of Select (continued)
 
The number of the descendants of left node + 1 is the
number of nodes that are less than the root
 
- E has 4 descendants + 1 makes 5 less than the root
 
If we are selecting for a number less than the left node’s
descendants + 1, then the node we are looking for is in
the left branch.  In the example, if we are selecting for
ranks 4 or less, the target node is in the left branch.
 
In this example, we can ignore the right branch and
recursively call the function on the left branch.
 
 
 
Implementation of Select (continued)
 
If the target node is not in the left branch, we need to
search for it in the right branch.
 
We need to compensate for the fact that the rank of the
target node in the left subtree will be smaller than the
rank of node in the whole tree.  In the subtree the rank
will be smaller by the number of nodes in the left branch
plus the root.
 
Thus we will reduce the requested rank by the
Ndescendants for the Left child plus 2 (1 for leftChild and
1 for root).
 
 
In this example, if we are looking for rank 6
(which is X) we would reduce the rank when
we recursively call the function on the left
subtree by 6.
 
Implementation of Rank
 
If the node key matches the requested key
 
the rank of the node in the subtree rooted at
 
this node is the number of nodes in the left subtree.
 
If the requested key is less than the node key
 
the rank of the node in the subtree rooted at this node
       is its rank in the left subtree.
 
If the requested key is greater than the node key
 
the rank of the node in the subtree rooted at this node
 
is the number of nodes in the left subtree + 1 for the
 
root plus its rank the right subtree
 
Definition of Range
 
The Range function returns an enumeration of data from a range
of keys.
Range(startKey, endKey) returns information for entries >=
startKey and <= endKey.
 
Range(R,X) returns information from R,S, and X.
Slide Note
Embed
Share

Rank, Select, and Range are key operations in Binary Search Trees that help determine the position of a key, find a key based on its rank, and select keys within a specified range. Sedgewick's notes provide detailed insights into the definitions and implementations of these operations, including computing the number of descendants and navigating through the tree to locate the desired keys efficiently.


Uploaded on Jul 10, 2024 | 3 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Rank, Select, and Range in Binary Search Trees Notes from Sedgewick

  2. Definition of Rank The rank of a key k is the number of keys in the BST that are less than k. Key Rank(Key) A 0 C 1 E 2 H 3 R 4 S 5 X 6

  3. Definition of Select The Select function finds the key with a specified rank. Rank Select(Rank) 0 A 1 C 2 E 3 H 4 R 5 S 6 X Key Rank(Key) A 0 C 1 E 2 H 3 R 4 S 5 X 6 Select is the inverse of rank i = rank(select(i)) key = select(rank(key))

  4. Implementation of Select Create a function computeNDescendants() that sets a value inside the node that records the number of descendants the node has. computeNDescendants(root); Assert(6, root.NDescendants); Assert(4, root.Left.NDescendants); Assert(1, root.Left.Left.NDescendants); We will need to call computeNDesendants before we call one or more select functions.

  5. Implementation of Select (continued) The number of the descendants of left node + 1 is the number of nodes that are less than the root - E has 4 descendants + 1 makes 5 less than the root If we are selecting for a number less than the left node s descendants + 1, then the node we are looking for is in the left branch. In the example, if we are selecting for ranks 4 or less, the target node is in the left branch. In this example, we can ignore the right branch and recursively call the function on the left branch.

  6. Implementation of Select (continued) If the target node is not in the left branch, we need to search for it in the right branch. We need to compensate for the fact that the rank of the target node in the left subtree will be smaller than the rank of node in the whole tree. In the subtree the rank will be smaller by the number of nodes in the left branch plus the root. In this example, if we are looking for rank 6 (which is X) we would reduce the rank when we recursively call the function on the left subtree by 6. Thus we will reduce the requested rank by the Ndescendants for the Left child plus 2 (1 for leftChild and 1 for root).

  7. Implementation of Rank If the node key matches the requested key the rank of the node in the subtree rooted at this node is the number of nodes in the left subtree. If the requested key is less than the node key the rank of the node in the subtree rooted at this node is its rank in the left subtree. If the requested key is greater than the node key the rank of the node in the subtree rooted at this node is the number of nodes in the left subtree + 1 for the root plus its rank the right subtree

  8. Definition of Range The Range function returns an enumeration of data from a range of keys. Range(startKey, endKey) returns information for entries >= startKey and <= endKey. Range(R,X) returns information from R,S, and X.

More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#