Upper Bounds for the Total Path Length of Binary Trees

ABSTRACT

Two upper bounds for the total path length of binary trees are obtained. One is for node-trees, and bounds the internal (or root-to-node) path length; the other is for leaf-trees, and bounds the external (or root-to-leaf) path length. These bounds involve a quantity called the balance, which allows the bounds to adapt from the n log n behavior of a completely balanced tree to the n2 behavior of a most skewed tree. These bounds are illustrated for the case of Fibonacci trees.

REFERENCES

• 1: Robert G. Gallager, Information Theory and Reliable Communication, John Wiley & Sons, Inc., New York, NY, 1968
• 2: Thomas N. Hibbard, Some Combinatorial Properties of Certain Trees With Applications to Searching and Sorting, Journal of the ACM (JACM), v.9 n.1, p.13-28, Jan. 1962 [doi>10.1145/321105.321108]
• 3: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 4: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 5: LANDAUER, W. I. The balanced tree and its utilization in information retrieval. IEEE Trans. EC-12 (Dec 1963), 863-871.
• 6: NIEVEROELT, J , AND WONG, C. K On binary search trees Proc IFIP Congress 1971, North-Holland Pubhsb, ing Co, Amsterdam, pp. 91-98.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Measurement, Theory, Verification