Optimum split trees

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)367-374
Number of pages8
JournalJournal of Algorithms
Volume5
Issue number3
DOIs
StatePublished - Sep 1984
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Optimum split trees'. Together they form a unique fingerprint.

Cite this