# Ordered Sets and Maps

Hashtables are fantastic at what they do (which is why Python has chosen them
for their implementation of
[sets](https://docs.python.org/2/library/stdtypes.html#set-types-set-frozenset)
and
[maps](https://docs.python.org/2/library/stdtypes.html#mapping-types-dict)).
They are $O(1)$ (amortized) at insertion and $O(1)$ at accessing. They are
easy to implement. There really aren't many downsides.

There is one big downside though, which is that hashtables can really only be
used for these Set and Map applications, and there are many related operations
that they can't do. To illustrate these, we introduce the "Ordered Set or
Map".

It is pretty common that we want to iterate through the elements of a set or
map in some sort of organized order. Let's think about iterating through the
elements of a Set implemented with a hashtable. The easiest way would be to
start at index 0, and (if implemented with separate chaining) list everything
in index 0, then everything in index 1, then index 2, etc. However, since a
good hash function destroys any patterns in incoming data, they'll come out in
a random-seeming order. This is in fact what we see when we use Python sets or
dictionaries. We illustrate below with a Python set of some of my daughter's
favorite things:

```python
>>> favorite = {'bunny','mommy','daddy','playground','grandma','puddles'}
>>> for thing in favorite:
...   print(thing)
... 
puddles
playground
grandma
bunny
mommy
daddy
```

If we want these to be in sorted order, or if we want to execute a `range()`
operation (like we discussed for B+ Trees, or, give me everything my daughter
likes that starts with 'p'), we still have to iterate through everything,
because a thing that starts with 'p' could be anywhere in the array. On the
other hand, if the set is implemented in a Tree, these types of operations are
much easier, as they are organized in a sorted manner.

In an Ordered Set or Map, we add the following functions to the typical
set/map functions:

- `first()`: Return the smallest element of the set or smallest key
- `last()`: Return the largest element of the set or largest key
- `next(k)`: Return the element or key which comes immediately after key `k`
- `previous(k)`: Return the element or key which comes immediate before key
  `k`

In a set/map implemented with a *sorted* array or linked list, `first` and
`last` are $O(1)$, because they're right on the ends. `previous` and `next`
involve finding `k`, and then getting the next/previous one. This takes the
same amount of time as finding `k`.

In an *unsorted* array or linked list, you have no choice but to iterate
through all elements of the data structure to perform these operations.
$O(n)$.

In a tree, these are all $O(\log(n))$. The smallest and largest are the
leftmost/rightmost elements, and once you've found `k`, the previous and next
are no more than $\log(n)$ away.

In a hashtable, though they are highly organized, they're not organized in
this way, and you must treat them the same as unsorted data structures.

## The final Ordered Set/Map runtime table

|                 | UA | SA     | ULL | SLL | Tree   | HT |
|-----------------|----|--------|-----|-----|--------|----|
| insert(e)       | 1A | n      | 1   | n   | log(n) | 1A |
| contains(e)     | n  | log(n) | n   | n   | log(n) | 1  |
| remove(e)       | n  | log(n)* | n   | n   | log(n) | 1  |
| first()/last()  | n  | 1      | n   | 1   | log(n) | n  |
| prev(k)/next(k) | n  | log(n) | n   | n   | log(n) | n  |

\* Recall that for this removal runtime, we assume removal is rare, and we
simply mark elements as removed, rather than physically taking them out. If
this gets too unwieldy, we can run the occasional $O(n)$ removal operation
which rebuilds the data structure without all the removed elements (which
would make this an *amortized* runtime). Something similar is often done with
Trees. There is an $O(\log(n))$ algorithm for physically removing elements
from a BST which keeps the tree balanced, but it is complex to implement, and
so sometimes they are just marked as removed out of coder laziness.