|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc020303,
author = {Markus E. Nebel},
title = {New Results on the Stack Ramification of Binary Trees},
journal = jalc,
year = 1997,
volume = 2,
number = 3,
pages = {161--175},
keywords = {analysis of algorithms, combinatorial problems},
abstract = {The stack-size of a tree $T$ is the number of cells of a
stack needed to traverse $T$ in postorder. In this paper we
show that the average number of proper subtrees having the
same stack-size as the whole tree is asymptotically $1$ with
a variance of $2+o(1)$. The total number of subtrees with a
stack-size one less than that of the whole tree is identical
to $2$. Counting only maximal subtrees changes this number
to $1+o(1)$ with a variance of $o(1)$.}
}