6600tom@ucsbuxa.ucsb.edu (Thomas Kwong) (12/08/90)
Hi! Can anyone tell me what a recursive tree is? and, what is the major use of this kind of tree? Just be brief. Thanx. Thomas. -------------------------------- 6600tom@ucsbuxa.ucsb.edu
flajolet@margaux.inria.fr (Philippe Flajolet) (12/09/90)
Meir and Moon in a paper of 1978 define a recursive tree as follows.
``A tree T_n with n labelled nodes, rooted at node 1, is a recursive tree
if n=1 or if T_n can be constructed by successively joining the j-th node to
one of the first j-1 nodes for 2<=j<=n.''
From the context, Meir and Moon use the term "tree" in the graph theoretic sense
(no distinction between left and right!). In other words, a recursive tree is
a [rooted unordered] tree without constraints on the node degrees allowed, with
labels that proceed in increasing order along any branch from
the root (which is by necessity labelled by 1).
There are (n-1)! such trees of size n, as Meir and Moon point out.
Meir and Moon present an approach to the analysis of such trees
which is based on generating functions.
Actually, if you order subtrees by the values of their labels,
then represent the resulting tree as a binary tree (there is a well-known
``rotation'' correspondence to achieve this), you obtain a
(binary) heap-ordered tree of size n-1.
Heap ordered trees are useful as a means of representing priority
queues (see Vuillemin's CACM paper; he calls them
binary tournaments), and they obey the same
``statistics'' as binary search trees.
From all this results, e.g., that recursive trees have expected height
O(log n), by results of Devroye. Their parameters essentially
reduce to similar parameters of binary search trees and
heap ordered trees.
Finally, there are interesting connections between recursive trees
(or BST's) and the analysis of union find algorithms (the random component
model, see [KnSc78,p. 313, about Doyle & Rivest, or Devroye's paper)
Philippe FLAJOLET
<flajolet@inria.fr>
References:
@string{CJM = "Canadian Journal of Mathematics"}
@article{MeMo78,
author = "A. Meir and J. W. Moon",
title = "On the altitude of nodes in random trees",
journal = CJM,
volume = 30,
year = 1978,
pages = "997--1015",
keywords = "random trees"
}
@Article{Vuillemin80,
author = "J. Vuillemin",
title = "A Unifying Look at Data Structures",
journal = "Communications of the ACM",
year = "1980",
volume = "23",
number = "4",
pages = "229--239",
month = "April"
}
@string{AI = "Acta Informatica"}
@Article{Devroye87,
author = "L. Devroye",
title = "Branching Processes in the Analysis of the Heights of Trees",
journal = AI,
volume = "24",
year = "1987",
pages = "277--298",
keywords = "trees, search problems, probabilistic analysis"
}
@string{TCS = "Theoretical Computer Science"}
@Article{KnSc78,
author = "Donald E. Knuth and Arnold Sch{\"o}nage",
title = "The expected linearity of a simple equivalence algorithm",
journal = TCS,
volume = "6",
pages = "281--315",
keywords = "probabilistic analysis, random graph, union-find"
}