Ordered Maps
Ordered Maps are just an extension of Maps, with a few extra methods.
- first - returns the element with the smallest key.
- last - returns the element with the largest key.
- next(k) - returns the element with the smallest key larger than k.
- prev(k) - returns the element with the largest key smaller than k.
Let's first look at the naive implementations:
| Unsorted Array | Sorted Array | Unsorted Linked List | Sorted Linked List | |
|---|---|---|---|---|
| insert(k,e) | O(1) | O(n) | O(1) | O(n) |
| get(k) | O(n) | O(log n) | O(n) | O(n) |
| remove(k) | O(n) | O(n) | O(n) | O(n) |
| first() | O(n) | O(1) | O(n) | O(1) |
| last() | O(n) | O(1) | O(n) | O(1) |
| next(k) | O(n) | O(log n) | O(n) | O(n) |
| prev(k) | O(n) | O(log n) | O(n) | O(n) |
Trees
Obviously, we're going to assume that we're using some flavor of our self-balancing trees: AVL, 2-3-4, Red-Black, or something else. These different flavors have slightly different heights, but these heights are all O(log n).
So, insert, get, and remove are easy - they're all O(log n). Let's consider our new methods.
Hopefully, you can write first() - it's just findMin(root). How long does this take? In the worst case, O(log n). last() is the same thing, just findMax.
To calculate next(k) (or prev(k)), we first have to find k, which is O(log n). If the node containing k has a right child, next() is found in findMin(n.getRight()). If it doesn't, it's the Node we most recently took a left at. In either case, that's an additional O(log n), in the worst case, making next and prev also O(log n).
Hashtables
Remember that if we have a well-built hash table, on average, we have O(1) performance in insert, get, and remove. Worst-case, we have O(n) for get and remove, while insert can still be O(1).
How long does first() or last() take? Unfortunately, because we have a good hash function that scatters hashes all over our array, we have NO clues as to where the smallest or largest keys might be. So, there's no better way to do this than just iterate through and look at everything. O(n).
Similarly, we have no guarantee that two keys that are close to each other will be hashed close to each other. So, again, we have to look at everything. O(n).
| Balanced Tree | Hashtable | |
|---|---|---|
| insert(k,e) | O(log n) | O(1)/O(n) |
| get(k) | O(log n) | O(1)/O(n) |
| remove(k) | O(log n) | O(1)/O(n) |
| first() | O(log n) | O(n) |
| last() | O(log n) | O(n) |
| next(k) | O(log n) | O(n) |
| prev(k) | O(log n) | O(n) |