Random binary tree

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.

In computer science and probability theory, a random binary tree is a binary tree selected at random from some probability distribution on binary trees. Different distributions have been used, leading to different properties for these trees.

Random binary trees have been used for analyzing the average-case complexity of data structures based on binary search trees. For this application it is common to use random trees formed by inserting nodes one at a time according to a random permutation.[1] The resulting trees are very likely to have logarithmic depth and logarithmic Strahler number. The treap and related balanced binary search trees use update operations that maintain this random structure even when the update sequence is non-random.

Other distributions on random binary trees include the uniform discrete distribution in which all distinct trees are equally likely, distributions on a given number of nodes obtained by repeated splitting, binary tries and radix trees for random data, and trees of variable size generated by branching processes.

For random trees that are not necessarily binary, see random tree.

  1. ^ Drmota (2009), p. 19.