Understanding Rank, Select, and Range in Binary Search Trees

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.

• Binary Search Trees
• Rank
• Select
• Range
• Sedgewick

alec Follow

Uploaded on Jul 10, 2024 | 1 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.

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.