Optimum multiway search trees | Acta Informatica Skip to main content
Springer Nature Link
Log in

Optimum multiway search trees

  • Published:
Acta Informatica Aims and scope Submit manuscript

Summary

The construction of optimum multiway search trees for n keys, n key weights and n+1 gap weights, is investigated. A new general optimality principle is presented, which can be “tuned” for specific applications. Moreover we consider the affects of three additional constraints, namely height, structural and node search restrictions, which lead to a number of new construction algorithms. In particular we concentrate on the construction of optimum t-ary search trees with linear and binary search within their nodes for which we obtain O(n 3 t) and O(n 3log2 t) time algorithms, respectively. Whether these algorithms are or are not optimal remains an important open problem, even in the binary case.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Allen B, Munro JI (1978) Self-organizing binary search trees. Journal ACM 25:526–535

    Google Scholar 

  2. Bayer R (1972) Symmetric binary B-trees: Data structures and maintenance algorithms. Acta Informat 1:290–306

    Google Scholar 

  3. Bayer R, McCreight EM (1972) Organization and maintenance of large ordered indexes. Acta Informat 1:173–189

    Google Scholar 

  4. Brown KQ (1979) Dynamic programming in computer science. Carnegie-Mellon University, Department of Computer Science Technical Report CMU-CS-79-106

  5. Culik II K, Ottmman T, Wood D (1979) Dense multiway search trees. McMaster University, Unit for Computer Science Technical Report 79-CS-5

  6. Fredman ML (1975) Two applications of a probabilistic search technique: sorting X + Y and building balanced search trees. Proceedings of the Seventh Annual ACM Symposium on the Theory of Computing p. 240

  7. Garcia AM, Wachs ML (1977) A new algorithm for minimum cost binary trees. SIAM J Comput 6:622–642

    Google Scholar 

  8. Garey MR (1974) Optimal binary search trees with restricted maximal depth. SIAM J of Comput 2:101–110

    Google Scholar 

  9. Gotlieb L (1978) Optimal multi-way search trees. Doctoral Dissertation, University of Toronto

  10. Gotlieb L, Kriegel HP, Vaishnavi VK, Wood D (1979) Optimal multiway search trees. Proceedings of the 1979 John Hopkins Conference on Information Sciences and Systems 255–256

  11. Gotlieb L, Wood D (1980) The construction of optimal multiway search trees and the monotonicity principle. Internat J Comput Math, (in press)

  12. Hu TC, Tucker AC (1971) Optimal computer search trees and variable length alphabetic codes. SIAM J. Appl Math 21:514–532

    Google Scholar 

  13. Itai A (1976) Optimal alphabetic trees. SIAM Comput 5:9–18

    Google Scholar 

  14. Knuth DE (1971) Optimum binary search trees. Acta Informat 1:14–25

    Google Scholar 

  15. Knuth DE (1973) The art of computer programming, Vol III: Sorting and searching. Reading, MA, Addison-Wesley

    Google Scholar 

  16. Kwong YS, Wood D (1978) T-trees: a variant of B-trees. McMaster University, Unit for Computer Science Technical Report 78-CS-18

  17. Melhorn K (1975) Nearly optimal binary search trees. Acta Informat 5:287–295

    Google Scholar 

  18. Melhorn K (1977) A best possible bound for the weighted path length of binary search trees. SIAM J Comput 6:235–239

    Google Scholar 

  19. Melhorn K (1979) Dynamic binary search. SIAM J Comput 8:175–198

    Google Scholar 

  20. Miller RE, Pippenger N, Rosenberg AL, Snyder L (1979) Optimal 2, 3-trees. SIAM J Comput 8:42–59

    Google Scholar 

  21. Ottmann T, Wood D (1980) 1–2 brother trees or AVL trees revisited. Comput J, in press

  22. Rosenberg AL, Snyder L (1978) Minimal-comparison 2, 3-trees. SIAM J Comput 7:465–480

    Google Scholar 

  23. Rosenberg AL, Snyder, L (1978) Compact B-trees. IBM Research Report RC-7343

  24. Wessner RL (1976) Optimum alphabetic search trees with restricted maximal height. Information Processing Lett 4:90–94

    Google Scholar 

  25. Zaki A, Baer J-L (1978) A comparison of query costs in AVL and 2–3 trees. Technical Report 78-02-01, Department of Computer Science, University of Washington, Seattle, Washington

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Concordia University, H4B 1R6, Montréal, Québec, Canada

    V. K. Vaishnavi

  2. Lehrstuhl Informatik VI, Universität Dortmund, Postfach 50 05 00, 4600, Dortmund 50, Germany (Fed. Rep.)

    H. P. Kriegel

  3. Unit for Computer Science, McMaster University, L8S 4K1, Hamilton, Ontario, Canada

    D. Wood

Authors
  1. V. K. Vaishnavi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. H. P. Kriegel
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. D. Wood
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Vaishnavi, V.K., Kriegel, H.P. & Wood, D. Optimum multiway search trees. Acta Informatica 14, 119–133 (1980). https://doi.org/10.1007/BF00288540

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00288540

Keywords

Search

Navigation