Maps and Dictionaries

From

---

Revision as of 14:57, 28 March 2009

A dictionary is an abstract data structure that consists of a collection of ordered pairs of objects ( Key, Data ), where the Key object is an identifier for the Data object. Commonly, the Key object is unique; that is, no two Key objects are identical, but this is not required. However, it is required that no two copies of the same Data object may be associated with two different Key objects. Some common examples of a dictionary structure are—of course—a dictionary, where the Key object is the word and the Data object is the definition of the word; and a telephone book, where the Key object is the name and the Data object is the telephone number.

The standard operations on a dictionary data structure are Insert( (Key, Data) ), Delete( Key ) or Delete( (Key, Data) ) if Key objects are not unique, and Search( Key ). There can be other operations, such as Replace( Key, Data ) or Count( Key ), etc.

Because it is an abstract data type, the definition of a dictionary does not imply an implementation. Therefore, there are many ways in which a dictionary structure may be implemented. In the following, we will look at several data structures that can be used to implement a dictionary. Among these structures are: Binary Search Tree, AVL Tree, Red-Black Tree, Splay Tree, and B+ Trees. Non-tree based ADT's can also be used such as Hash Tables.