Question 1
An in-memory event index contains n records with distinct timestamp keys. Inserts and deletions must take O(log n) worst-case time, and a query must return the k records within a timestamp interval in sorted order in O(log n + k) time. Select the single data structure that supports both requirements.
Show answer & explanation
Correct answer: B - A red-black search tree, with an ordered range traversal.