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\)