Abstract
A split tree is a special kind of a binary search tree introduced by Sheil [S]. He conjectured that constructing an optimum split tree is an intractable problem since there is a difficulty in applying the dynamic programming technique. We realize that the difficulty arise since top down decisions are required while applying the bottom up dynamic programming technique. We demonstrate that it is possible in this case to overcome such a difficulty, and present a polynomial algorithm for constructing an optimum split tree, This algorithm incorporates top down decisions into a dynamic programming procedure similar to Knuth's EK21 algorithm for constructing an optimum binary search tree. An improved algorithm of complexity O(n 4 ) is finally presented. A modification for the case that equiprobable keys are permitted is discussed.