Abstract Data Types

BST: Binary Search Tree HTC: Hash Table with Chaining (use n/m for alpha) SL: Skip List SDLL: Sorted Doubly Linked List USLL: Unsorted Singly Linked List Which Implementation of the Dynamic Set ADT is fastest Including constant costs If you primarily will do the following operation(s), and what is the expected case cost to do so? Some operators may have implementations that are equivalent from an asymptotic perspective in that case, pick the simplest solution with smallest cost in space and time you do not have to use all of the options. Write only the acronyms (BST, HTC, SL, SDLL, USLL) In the first field for each question. Use simple Ascil notation in the field for analysis (no parentheses are needed for correct answers). a. Insert a new key into the set: Use implementation with expected of ) per insertion per search ) per iteration b. Search for a key: Use implementation with expected on c. Iterate over all the keys in sorted order: Use implementation with expected ( d. Find the predecessor given a position (not key) in the data structure: Use implementation retrieval with expected Of ) per predecessor with e. Optimize a mixture of insertion, searching, and deletion, regardless of whether data arrives 'randomly' or in some order: Use implementation expected el ) per Insertion, search, or deletion