ABSTRACT
Given an initially empty set S, the dictionary problem consists of executing online 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 store or retrieve it. It is well known that 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).
