Random binary tree

[2] In a binary search tree the internal nodes are labeled by numbers or other ordered values, called keys, arranged so that an inorder traversal of the tree lists the keys in sorted order.

[3] Binary trees may also be studied with all nodes unlabeled, or with labels that are not given in sorted order.

The position for each insertion can be found by a binary search in the previous tree.

The sum of these probabilities forms two copies of the harmonic series extending away from

This bound also holds for the expected search path length for a value

satisfying the equation In the random permutation model, each key except the smallest and largest has probability

-node random binary search trees, simulations suggest that the expected Strahler number is

[10] In applications of binary search tree data structures, it is rare for the keys to be inserted without deletion in a random order, limiting the direct applications of random binary trees.

However, algorithm designers have devised data structures that allow arbitrary insertions and deletions to preserve the property that the shape of the tree is random, as if the keys had been inserted randomly.

Such a data structure is known as a treap or a randomized binary search tree.

-node tree of this type is The expected Strahler number of a uniformly random

, lower than the expected Strahler number of random binary search trees.

Then, while the current tree has not reached the target size, repeatedly choose one of its nodes (internal or external) uniformly at random.

of tails, until the first flip at which the number of tails exceeds the number of heads (for the model in which an external root is allowed) or exceeds one plus the number of heads (when the root must be internal), and then use this sequence of coin flips to determine the choices made by the recursive generation process, in depth-first order.

of nodes are generated from (unique) coin flip sequences of the same length, and are equally likely, regardless of

will produce trees with a smaller expected size, while larger values of

there is no finite bound on the expected size of trees generated by this process.

, and the probability that a random tree has this size is this probability multiplied by a Catalan number, Galton–Watson processes were originally developed to study the spread and extinction of human surnames, and have been widely applied more generally to the dynamics of human or animal populations.

These processes have been generalized to models where the probability of being an internal or external node at a given level of the tree (a generation, in the population dynamics application) is not fixed, but depends on the number of nodes at the previous level.

[30] Another application of critical Galton–Watson trees (in the version where the root must be internal) arises in the Karger–Stein algorithm for finding minimum cuts in graphs, using a recursive edge contraction process.

The random tree models the subtree of correct recursive calls.

vertices whenever this random tree of correct recursive calls has a branch of depth at least

The number of external nodes in the tree, at any time, is modeled by a simple birth process or Yule process in which the members of a population give birth at a constant rate: giving birth to one child, in the Yule process, corresponds to being replaced by two children, in Devroye and Robson's model.

If this process is stopped at any fixed time, the result is a binary tree of a random size (depending on the stopping time), distributed according to the random permutation model for that size.

Devroye and Robson use this model as part of an algorithm to quickly generate trees in the random permutation model, described by their numbers of nodes at each depth rather than by their exact structure.

The internal nodes of the tree represent prefixes of their binary representations that are shared by two or more of the numbers.

The analysis of these trees can be applied to the computational complexity of trie-based sorting algorithms.

The remaining internal nodes correspond to prefixes for which both possible extensions, by a zero or a one bit, are used by at least one of the randomly chosen numbers.

uniformly distributed binary numbers, the shortest leaf-root path has length

[34] Luc Devroye and Paul Kruszewski describe a recursive process for constructing random binary trees with

Two random distributions on three-vertex binary trees, the binary search trees on three keys a , b , and c . These five trees are each assigned probability 1/5 by the uniform distribution (top). The distribution generated by random insertion orderings (bottom) assigns the center tree probability 1/3, because two of the six possible insertion orderings generate the same tree; the other four trees have probability 1/6.
An extended binary tree, showing internal nodes as yellow circles and external nodes as red squares
Binary tree generated from 100-element random permutation
Uniformly random binary tree with 100 nodes
A binary trie and radix tree for the same data, eight numbers in the unit interval. The labels are prefixes of the binary representations of the numbers, shared by two or more of the numbers.