×

A note on the expected path length of trees with known fringe. (English) Zbl 0875.68705

Summary: The path length of a tree, that is, the sum of the lengths of all root-leaf paths, is an important measure of efficiency of the tree. The fringe of a tree is the difference between the lengths of the longest path and the shortest path in the tree. The minimal and the maximal path length of trees with N leaves and given fringe have been well studied. We initiate the study of the expected path length of the class of trees with N leaves and fringe \(\Delta\) by giving a closed expression for the expected path length when \(\Delta =2.\)

MSC:

68R10 Graph theory (including graph drawing) in computer science
68P05 Data structures
68W10 Parallel algorithms in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cameron, H.; Wood, D., The maximal path length of binary trees, Discrete Appl. Math., 55, 15-35 (1994) · Zbl 0821.68094
[2] Cameron, H.; Wood, D., The internal path length of red black trees, Inform. Process. Lett., 42, 287-292 (1992) · Zbl 0780.68053
[3] De Prisco, R.; Parlati, G.; Persiano, G., Minimal path length of trees with known fringe, Theoret. Comput. Sci., 143, 175-188 (1995) · Zbl 0873.68151
[4] De Santis, A.; Persiano, G., Tight upper and lower bounds on the path length of binary trees, SIAM J. Comput., 23, 12-23 (1994) · Zbl 0802.68034
[5] De Santis, A.; Persiano, G., Tight bounds on the path length of binary trees, (Proc. STACS’91. Proc. STACS’91, Lecture Notes in Computer Science, 480 (1991), Springer: Springer Berlin), 478-487 · Zbl 0767.05060
[6] Klein, R.; Wood, D., On the path length of binary trees, J. ACM, 36, 280-289 (1989) · Zbl 0674.68012
[7] Klein, R.; Wood, D., On binary trees, (Information Processing (1989)), 449-454
[8] Klein, R.; Wood, D., A tight upper bound for the path length of AVL tree, Theoret. Comput. Sci., 72, 251-264 (1990) · Zbl 0698.68019
[9] Nievergelt, J.; Wong, C. K., Upper bounds for the total path length of binary trees, J. ACM, 20, 1-6 (1973) · Zbl 0263.68022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.