Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On the maximum path length of AVL trees

  • Tree Algorithms
  • Conference paper
  • First Online:
CAAP '88 (CAAP 1988)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 299))

Included in the following conference series:

  • 172 Accesses

Abstract

We prove that the internal path length of an AVL tree of size N is bounded from above by

$$1.4404N(\log _2 N - \log _2 \log _2 N) + O(N)$$

and show that this bound is achieved by an infinite family of AVL trees. But AVL trees of maximal height do not have maximal path length. These results carry over to the comparison cost of brother trees.

This work was partially supported by a Natural Sciences and Engineering Research Council of Canada Grant A-5692. It was done during the first author's stay with the Data Structuring Group in Waterloo in 1986/1987.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. G.M. Adel'son-Vel'skii and Y.M. Landis. An algorithm for the organization of information. Doklady Akademi Nauk, 146:263–266, 1962.

    Google Scholar 

  2. A. Brüggemann-Klein and D. Wood. Drawing Trees Nicely with T EX. Technical Report CS-87-05, Department of Computer Science, University of Waterloo, 1987.

    Google Scholar 

  3. C.C. Foster. Information storage and retrieval using AVL trees. In Proccedings of the ACM National Conference, pages 192–205, 1965.

    Google Scholar 

  4. G. Gonnet. Balancing binary trees by internal path reduction. Communications of the ACM, 26:1074–1081, 1983.

    Google Scholar 

  5. R. Klein and D. Wood. On the Path Length of Binary Trees. Technical Report CS-87-06, Department of Computer Science, University of Waterloo, 1987.

    Google Scholar 

  6. D.E. Knuth. The Art of Computer Programming, Vol.3: Sorting and Searching. Addison-Wesley Publishing Co., Reading, Mass., 1973.

    Google Scholar 

  7. Th. Ottmann, D.St. Parker, A.L. Rosenberg, H.-W. Six, and D. Wood. Minimal-cost brother trees. SIAM Journal on Computing, 13:197–217, 1984.

    Google Scholar 

  8. Th. Ottmann and H.-W. Six. Eine neue Klasse von ausgeglichenen Binärbäumen. Angewandte Informatik, 9:395–400, 1976.

    Google Scholar 

  9. Th. Ottmann, H.-W. Six, and D. Wood. On the correspondence between AVL trees and brother trees. Computing, 23:43–54, 1979.

    Google Scholar 

  10. Th. Ottmann and D. Wood. 1–2 brother trees or AVL trees revisited. Computer Journal, 23:248–255, 1981.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Informatik, Universität Freiburg, Rheinstr. 10–12, 7800, Freiburg, Fed. Rep. of Germany

    Rolf Klein

  2. Data Structuring Group, Department of Computer Science, University of Waterloo, N2L 3G1, WATERLOO, Ontario, Canada

    Derick Wood

Authors
  1. Rolf Klein
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Derick Wood
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

M. Dauchet M. Nivat

Rights and permissions

Reprints and permissions

Copyright information

© 1988 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Klein, R., Wood, D. (1988). On the maximum path length of AVL trees. In: Dauchet, M., Nivat, M. (eds) CAAP '88. CAAP 1988. Lecture Notes in Computer Science, vol 299. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0026093

Download citation

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

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-19021-9

  • Online ISBN: 978-3-540-38930-9

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation