Maps
It's time for a new ADT: the Map. Every piece of data in a Map has two parts: a key and an element. We find the element, by searching for the key. For example, a dictionary is a map: we look up the word (the key), and get the definition (the element). So is a phone book: we look up the name, and get the phone number and address. In 210, you did a lab where you counted how many times words appeared in a document; the word was the key, and the count was the element. The important thing is that the keys be sortable (like numbers, or strings), so that we can be smart about storing them.
The operations are:
- insert(k,e): Insert element e with key k.
- get(k): Return the element associated with key k.
- remove(k): Return the element associated with key k.
Think about how you would implement these methods with sorted and unsorted arrays and linked lists, as well as binary trees.
| insert(k,e) | get(k) | remove(k) | |
|---|---|---|---|
| Unsorted array | O(1) (amortized) | O(n) | O(n) |
| Sorted array | O(n) | O(log(n)) | O(n) |
| Unsorted Linked List | O(1) | O(n) | O(n) |
| Sorted Linked List | O(n) | O(n) | O(n) |
| Binary Search Trees | O(height) | O(height) | O(height) |
For now, we know that the height of a tree is somewhere between log(n) and n. If only we had a way to guarantee the tree would be balanced! If only...