ABSTRACT
Given an initially empty set S, the dictionary problem consists of executing on-line any sequence of operations of the form S.membership(s), S.insert(s) and S.delete(s), where each element s is an object (or point in one dimensional space). Each object can be stored in a single word, and it takes O(1) time to save and/or retrieve it. The set may be represented by using arrays (sorted or unsorted), linked lists (sorted or unsorted), hash tables, binary search trees, AVL-trees, B-trees, 2-3 trees, weighted balanced trees, or balanced binary search trees (i.e., 2-3-4 trees,symmetric B-trees, half balanced trees or red-black trees). The worst case time complexity for performing each of these operations is O(log n), where n is the maximum number of elements in a set, when using AVL-trees, B-trees (fixed order), 2-3 trees, weighted balanced trees, or balanced binary search trees. See Chapters 2, 3, 9, 10 and 15 for details on these structures. The insertion or deletion of elements in these structures requires a set of operations to preserve certain properties of the resulting trees. For binary search trees, these operations are called rotations, and for m-way search trees they are called splitting or combining nodes. The balanced binary search trees are the only trees that require a constant number of rotations for both the insert and delete operations [13, 15].
