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 |
 (from crpit.com)
(local if available)
|