AN ESSAY SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF

Binary search tree (BST) is a fundamental data structure widely used for accesses to ordered data. Despite its wide usage, no online algorithm has yet been proven to be O(1) competitive to the optimal offline dynamic BST algorithm. The first part of this essay surveys different optimality measures with a greater emphasis on dynamic and static optimality. Lower bounds on the performance of an optimal dynamic BST are discussed. Online splay tree algorithm which is conjectured to be dynamically optimal and two different O(lg lg(n)) competitive online algorithms (Tango tree and Multi-Splay tree) are studied. Secondly variable-to-fixed length scheme of lossless compression is discussed and the entropy lower bound is tied to the static optimality of search trees. Different techniques (based on renewal theory and Markov processes) for analyzing plurally parsable dictionaries with memoryless sources and sources with memory are discussed. i