In computer science and probability theory, a random binary tree refers to a binary tree selected at random from some probability distribution on binary trees. Two different distributions are commonly used: binary trees formed by inserting nodes one at a time according to a random permutation, and binary trees chosen from a uniform discrete distribution in which all distinct trees are equally likely. It is also possible to form other distributions, for instance by repeated splitting. Adding and removing nodes directly in a random binary tree will in general disrupt its random structure, but the treap and related randomized binary search tree data structures use the principle of binary trees formed from a random permutation in order to maintain a balanced binary search tree dynamically as nodes are inserted and deleted.
For random trees that are not necessarily binary, see random tree.
Read more about Random Binary Tree: Binary Trees From Random Permutations, Uniformly Random Binary Trees, Random Split Trees
Famous quotes containing the words random and/or tree:
“Assemble, first, all casual bits and scraps
That may shake down into a world perhaps;
People this world, by chance created so,
With random persons whom you do not know—”
—Robert Graves (1895–1985)
“Hope deferred makes the heart sick, but a desire fulfilled is a tree of life.”
—Bible: Hebrew, Proverbs 13:12.