Sequential Optimization of Binary Search Trees for Multiple Cost Functions

Alnae, M., Chikalov, I., Hussain, S. and Moshkov, M.

    In this paper, we present a methodology to model the optimal binary search tree problem as a directed acyclic graph to extract all possible optimal solutions. We provide a mechanism to find optimal binary search trees relative to different types of cost functions, sequentially. We prove that for a set of n keys our optimization procedure makes O(n3) arithmetic operations per cost function such as weighted depth or average weighted depth.
Cite as: Alnae, M., Chikalov, I., Hussain, S. and Moshkov, M. (2011). Sequential Optimization of Binary Search Trees for Multiple Cost Functions. In Proc. Computing: The Australasian Theory Symposium (CATS 2011) Perth, Australia. CRPIT, 119. Alex Potanin and Taso Viglas Eds., ACS. 41-44
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS