Sequential optimization of binary search trees for multiple cost functions
Maram Alnafie, Igor Chikalov, Shahid Hussain, Mikhail Moshkov · Computing: The Australasian Theory Symposium · 2011
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.