Left and Right Length of Paths in Binary Trees or on a Question of Knuth |
| |
Authors: | Alois Panholzer |
| |
Institution: | 1. Institut für Diskrete Mathematik und Geometrie, Technische Universit?t Wien, Wiedner Hauptstr. 8-10/104, 1040, Wien, Austria
|
| |
Abstract: | We consider extended binary trees and study the joint right and left depth of leaf j, where the leaves are labelled from left to right by 0, 1, . . . , n, and the joint right and left external pathlength of binary trees of size n. Under the random tree model, i.e., the Catalan
model, we characterize the joint limiting distribution of the suitably scaled left depth and the difference between the right
and the left depth of leaf j in a random size-n binary tree when j ~ ρn with 0 < ρ > 1, as well as the joint limiting distribution of the suitably scaled left external pathlength and the difference
between the right and the left external pathlength of a random size-n binary tree.
This work was supported by the Austrian Science Foundation FWF, grant S9608-N13. |
| |
Keywords: | binary trees imbalance node depth |
本文献已被 SpringerLink 等数据库收录! |
|