✦ LIBER ✦

On the distribution of binary search trees under the random permutation model

✍ Scribed by James Allen Fill

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 865 KB
Volume: 8
Category: Article
ISSN: 1042-9832
DOI: 10.1002/(sici)1098-2418(199601)8:1<1::aid-rsa1>3.0.co;2-1

No coin nor oath required. For personal study only.

✦ Synopsis

We study the distribution Q on the set B, of binary search trees over a linearly ordered set of n records under the standard random permutation model. This distribution also arises as the stationary distribution for the move-to-root (MTR) Markov chain taking values in B,, when successive requests are independent and identically distributed with each record equally likely. We identify the minimum and maximum values of the functional Q and the trees achieving those values and argue that Q is a crude measure of the "shape" of the tree. We study the distribution of Q ( T ) for two choices of distribution for random trees T ; uniform over B, and Q. In the latter case, we obtain a limiting normal distribution for -In Q ( T ) .

📜 SIMILAR VOLUMES

On the Total Heights of Random Rooted Bi

On the Total Heights of Random Rooted Binary Trees

✍ L. Takacs 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 306 KB

Denote by \(S_{n}\) the set of all distinct rooted binary trees with \(n\) unlabeled vertices. Define \(\sigma_{n}\) as a total height of a tree chosen at random in the set \(S_{n}\), assuming that all the possible choices are equally probable. The total height of a tree is defined as the sum of the

On the complexity of branch-and-bound se

On the complexity of branch-and-bound search for random trees

✍ Luc Devroye; Carlos Zamora-Cura 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 256 KB 👁 2 views

Let T be a b-ary tree of height n, which has independent, non-negative, n identically distributed random variables associated with each of its edges, a model previously considered by Karp, Pearl, McDiarmid, and Provan. The value of a node is the sum of all the edge values on its path to the root. Co

On the joint distribution of the nodes i

On the joint distribution of the nodes in uniform multidimensional binary trees

✍ Rainer Kemp 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 313 KB 👁 2 views

Multidimensional binary trees represent a symbiosis of trees and tries, and they essentially arise in the construction of search trees for multidimensional keys. The set of nodes in a d-dimensional binary tree can be partitioned into layers according to the nodes appearing in the ith dimension. We d

Conducting inference in semiparametric d

Conducting inference in semiparametric duration models under inequality restrictions on the shape of the hazard implied by job search theory

✍ Charles J. Romeo 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 208 KB 👁 2 views

Using a four-month panel of revised Current Population Survey data from September±December 1993, we extend the class of semiparametric hazard models of the type ®rst studied by Prentice and Gloeckler (1978), and brought to the attention of economists by Meyer (1988Meyer ( , 1990)), to incorporate in

On the mathematical modeling of thermoel

On the mathematical modeling of thermoelastic systems with random emission under physical constraints and its simulation studies

✍ Masaaki Ishikawa 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 368 KB 👁 2 views

It is known that the stress generated in an elastic material depends on the temperature distribution if the temperature field is not uniform. In such cases, it is necessary to carry out an analysis using a model taking into account the thermoelastic characteristics. In an actual problem, it is not u