Question: We would like to design a data structure to maintain the records of a group of people. Besides insertion and searching, the data structure should
We would like to design a data structure to maintain the records of a group of people. Besides insertion and searching, the data structure should also support the two operations: Find-Closest and Find-Furthest, which find the two people closest and furthest in age, respectively. We would like all operations to take O(log n) time for any group of n people. Suppose that we use a Red-Black BST:
-
Which field should be used as the key, and what additional information, if any, needs to be stored at each node to support the required operations?
-
Show how the operations Find-Closest and Find-Furthest can be implemented to take O(log n) time.
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
