Just as linked lists and dynamic arrays are convenient implementations of the idea of a "vector"/"list" ADT, so we can regard trees as a convenient implementation of the map ADT.
In mathematical terms, a map (as the term is commonly used in computer science) is a partial function whose domain is a set of keys and whose range is a set of values. The idea behind this function is that it "maps" each key onto a unique value.
In pseudocode, the following interface defines the important map operations:
class Map { // Insert/"associate" a given value for the given key. void insert(KeyType key, ValueType value); // Returns true if the given key exists in the map bool contains(KeyType key); // Retrieve the value associated with the given key. // Precondition: contains(key) is true ValueType find(KeyType key); // Remove the pointer to the value associated with // the given key. Returns the value removed. // Precondition: contains(key) is true ValueType remove(KeyType key); }; Common uses for maps are as dictionaries (in fact, you will often hear the "dictionary" ADT used as a synonym for "map"). Sometimes maps are called "associative arrays", because it is natural to subscript maps as you might subscript an array:
// Overloaded indexing operator ValueType& operator[](KeyType key) { return find(key); } // Usage example Map my_map; KeyType key( /* ... */ ); // Assume we construct the key ValueType value( /* ... */ ); // and value somehow. my_map.insert(key, value); // Associate the key with the value // Now, we can index the map using the key type, and // obtain a value. ValueType another_value = my_map[key];