Dictionaries
Dictionaries are data structures that support search,
insert, and delete operations. One of the most
effective representations is a hash table. Typically, a
simple function is applied to the key to determine its place in the
dictionary. Also presented are binary trees and
red-black trees. Both tree methods use a technique
similar to the binary search algorithm to minimize the number of comparisons
during search and update operations on the dictionary.
Finally, skip lists illustrate a simple approach that utilizes
random numbers to construct a dictionary.