# Ordered dictionaries

## Dictionaries

In real life, a dictionary contains a list of words together with their meaning/translation/etymology etc. It is usually sorted alphabetically, so that the words can be easily found. Another example is a phone book which contains phone numbers that can be searched by name. In computer science, these would be called *static* dictionaries, since the set of records doesn’t change.

We would often like to insert new records or remove old ones. Such data structure is called a *(dynamic) dictionary*, an *associative array*, or a *look-up table*.

We say that a data structure is a dictionary (a set), if it can support the following operations:

`insert(x)`

– adds value \(x\) to the dictionary;`delete(x)`

– removes \(x\) from the dictionary;`find(x)`

## Ordered dictionaries

Ordered dictionaries further support:

`first()`

`last()`

`successor(v)`

– return the node with the smallest key bigger than \(v\) (or null if \(v\) was the last node)`predecessor(v)`

– return the node with the biggest key smaller than \(v\) (or null if \(v\) was the first node)`range(a, b)`

– return all items in the dictionary with a key between \(a\) and \(b\)