Optimum split trees |
| |
Authors: | Yehoshua Perl |
| |
Institution: | 1. Department of Computer Science, Rutgers University, New Brunswick, New Jersey 08903 USA;2. Bar Ilan University, Ramat-Gan, Israel |
| |
Abstract: | A split tree is a special kind of a binary search tree introduced by B. A. Sheil (Comm. ACM21 (1978), 947–958). He conjectured that constructing an optimum split tree is an intractable problem since there is a difficulty in applying the dynamic programming technique. It is realized that the difficulty arises since top down decisions are required while applying the bottom up dynamic programming technique. It is demonstrated that it is possible in this case to overcome such a difficulty, and a polynomial algorithm for constructing an optimum split tree is presented. This algorithm incorporates top down decisions into a dynamic programming procedure similar to D. E. Knuth's (Acta Inform. 1 (1971), 14–25) algorithm for constructing an optimum binary search tree. The probabilities of unsuccessful searches are taken into account. A modification for the case that equiprobable keys are permitted is discussed. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|