Carleton University
Technical Report TR-02-07
November 2002
Putting Your Dictionary on a Diet
Pat Morin
Abstract
We show that any comparison-based dictionary data structure that requires c*n memory in addition to the storage required for the data elements can be transformed into a dictionary that requires only e*n additional memory, for any e>0. This transformation does not increase the running times of algorithms for searching, inserting and deleting, except by a small constant factor that is independent of e and an additive term of O(1/e) or O(1/e^2) depending on the implementation used.