Upper Bounds for the Total Path Length of Binary Trees
- 1 January 1973
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 20 (1) , 1-6
- https://doi.org/10.1145/321738.321739
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 n 2 behavior of a most skewed tree. These bounds are illustrated for the case of Fibonacci trees.Keywords
This publication has 2 references indexed in Scilit:
- Computer programming as an artPublished by Association for Computing Machinery (ACM) ,2007
- Some Combinatorial Properties of Certain Trees With Applications to Searching and SortingJournal of the ACM, 1962