𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Patterns in random binary search trees

✍ Scribed by Philippe Flajolet; Xavier Gourdon; Conrado Martínez

Publisher
John Wiley and Sons
Year
1997
Tongue
English
Weight
243 KB
Volume
11
Category
Article
ISSN
1042-9832

No coin nor oath required. For personal study only.

✦ Synopsis

In a randomly grown binary search tree BST of size n, any fixed pattern occurs with a frequency that is on average proportional to n. Deviations from the average case are highly unlikely and well quantified by a Gaussian law. Trees with forbidden patterns occur with an exponentially small probability that is characterized in terms of Bessel functions. The results obtained extend to BSTs a type of property otherwise known for strings and combinatorial tree models. They apply to paged trees or to quicksort with halting on short subfiles. As a consequence, various pointer saving strategies for maintaining trees obeying the random BST model can be precisely quantified. The methods used are based on analytic models, especially bivariate generating function subjected to singularity perturba-Ž .

📜 SIMILAR VOLUMES

On the distribution of binary search tre
On the distribution of binary search trees under the random permutation model
✍ James Allen Fill 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 865 KB

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 ar

Weighted Binary Trees for Concurrent Sea
Weighted Binary Trees for Concurrent Searching
✍ David Cohen; Michael L. Fredman 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 225 KB

A traditional cost measure for binary search trees is given by weighted path length, which measures the expected cost of a single random search. In this paper, we investigate a generalization, the k-cost, which is suitable for applications involving independent parallel processors each utilizing a c

Large Trees in a Random Mapping Pattern
Large Trees in a Random Mapping Pattern
✍ Lyuben Mutafchiev 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 224 KB

Mapping patterns may be represented by unlabelled directed graphs in which each point has outdegree one. We consider the uniform probability measure on the set of all mapping patterns on \(n\) points and derive the limiting distribution of the size of the largest tree as \(n \rightarrow \infty\). It

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

An Almost-Greedy Search on Random Binary
An Almost-Greedy Search on Random Binary Vectors and Random Graphs
✍ Avner Dor; Eitan Greenshtein 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 193 KB

A random vector is sampled from a general binary probability space and a search goes through the coordinates until a 1-coordinate is found. A search algorithm called ''almost greedy'' is shown to posses some novel characteristics. Its expectation is shown to be sharply bounded by four times the expe

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