AbstractA 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.
RightsThis Item is protected by copyright and/or related rights.You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use.For other uses you need to obtain permission from the rights-holder(s).