Biased dictionaries with fast insert/deletes
Funda Ergün, Cenk Sahinalp, Jonathan Sharp, Rakesh Kumar Sinha · 2001
A dictionary data structure supports efficient search, insert, and delete operations on n keys from a totally ordered universe. Red-black trees, 2-3 trees, AVL trees, skip lists and other classic data structures facilitate O(logn) time search, insert and deletes, matching the information theoretic lower bound when access probabilities are uniform i.i.d. If access probabilities are non-uniform but still i.i.d., there are other weighted data structures such as D-trees, biased search trees, splay trees and treaps which can achieve optimality.