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. 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.
26=13 of being generated, whereas the other four trees each have \\tfrac16</math>.{{sfnp|Sedgewick|Flajolet|2013|p=286}}"}},"i":0}}]}'>probability n keys, the expected value of the length of the path from the root to log" denotes the natural logarithm function and the y, of the probability that y is an ancestor of [x,y]. Because each key in the interval is equally likely to be first, this happens with probability inverse to the length of the interval. Thus, the keys that are adjacent to x, the keys one step away have probability 2logn+O(1) bound above. This bound also holds for the expected search path length for a valueStrahler number
editThe Strahler number of vertices in any tree is a measure of the complexity of the subtrees under those vertices. A leaf (external node) has Strahler number one. For any other node, the Strahler number is defined recursively from the Strahler numbers of its children. In a binary tree, if two children have different Strahler numbers, the Strahler number of their parent is the larger of the two child numbers. But if two children have equal Strahler numbers, their parent has a number that is greater by one. The Strahler number of the whole tree is the number at the root node. For log3n+o(logn) has been proven.
Treaps and randomized binary search trees
editIn 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.
If a given set of keys is assigned numeric priorities (unrelated to their values), these priorities may be used to construct a Cartesian tree for the numbers, the binary search tree that would result from inserting the keys in priority order. By choosing the priorities to be independent random real numbers in the unit interval, and by maintaining the Cartesian tree structure using tree rotations after any insertion or deletion of a node, it is possible to maintain a data structure that behaves like a random binary search tree. Such a data structure is known as a treap or a randomized binary search tree.
Variants of the treap including the zip tree and zip-zip tree replace the tree rotations by "zipping" operations that split and merge trees, and that limit the number of random bits that need to be generated and stored alongside the keys. The result of these optimizations is still a tree with a random structure, but one that does not exactly match the random permutation model.
Uniformly random binary trees
edit
Uniformly random binary tree with 100 nodes
The number of binary trees with n-node tree of this type is
\\sqrt{\\pi n} - 3 + O\\left(\\frac{1}{\\sqrt n}\\right)</math>.{{sfnp|Sedgewick|Flajolet|2013|p=288}}"}},"i":0}}]}'>n-node binary tree is 1−p. If it is internal, its two children are trees generated recursively by the same process.Trees generated in this way have been called binary Galton–Watson trees. In the special case where p≤12 the resulting tree is almost certainly finite, whereas for \\tfrac12"}}'>p>12 it is infinite with positive probability. More precisely, for p</math>,"}},"i":0}}]}'>any
Because the number of internal nodes equals the number of heads in this coin flip sequence, all trees with a given number p affects the variation in the size of trees generated by this process, but for a given size the trees are generated uniformly at random. For values of p=12, smaller values of p=12 there is no finite bound on the expected size of trees generated by this process. More precisely, for p</math>,"}},"i":0}}]}'>any is p=12 this gives 1 + 1 + 1 + 1 + ⋯, a divergent series.
p=\\tfrac12</math>,"}},"i":0}}]}'>For probability
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. This algorithm calls itself twice recursively, with each call having probability at least 2log2n, reaching the base case of its recursion. The success probability \\Omega(1/\\log n)</math>,"}},"i":0}}]}'>is 2log2n. The analysis of these trees can be applied to the computational complexity of trie-based sorting algorithms.
A variant of the trie, the radix tree or compressed trie, eliminates empty external nodes and their parent internal nodes. 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. For a radix tree for log2n+2log2n+o(logn), both with high probability.
Random split trees
editLuc Devroye and Paul Kruszewski describe a recursive process for constructing random binary trees with (0,1), assigns the first n) for
| View original on Wikipedia | Back | FazBrowse Home |