Random tree
Encyclopedia
In mathematics
and computer science
, a random tree is a tree
or arborescence
that is formed by a stochastic process
. Types of random trees include:
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
and computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, a random tree is a tree
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
or arborescence
Arborescence (graph theory)
In graph theory, an arborescence is a directed graph in which, for a vertex u called the root and any other vertex v, there is exactly one directed path from u to v....
that is formed by a stochastic process
Stochastic process
In probability theory, a stochastic process , or sometimes random process, is the counterpart to a deterministic process...
. Types of random trees include:
- Uniform spanning tree, a spanning tree of a given graph in which each different tree is equally likely to be selected
- Random minimal spanning treeRandom minimal spanning treeIn mathematics, random minimal spanning tree, or random MST, is a model for a random spanning tree of a graph . It might be compared against the uniform spanning tree, a different model for a random tree which has been researched much more extensively...
, spanning trees of a graph formed by choosing random edge weights and using the minimum spanning tree for those weights - Random binary treeRandom binary treeIn computer science and probability theory, a random binary tree refers to a binary tree selected at random from some probability distribution on binary trees...
, binary trees with a given number of nodes, formed by inserting the nodes in a random order or by selecting all possible trees uniformly at random
- Random recursive tree, increasingly labelled trees, which can be generated using a simple stochastic growth rule.
- TreapTreapIn computer science, the treap and the randomized binary search tree are two closely related forms of binary search tree data structures that maintain a dynamic set of ordered keys and allow binary searches among the keys...
or randomized binary search tree, a data structure that uses random choices to simulate a random binary tree for non-random update sequences - Rapidly-exploring random treeRapidly-exploring random treeA Rapidly-exploring random tree is a data structure and algorithm designed for efficiently searching nonconvex, high-dimensional search spaces. The tree is constructed in such a way that any sample in the space is added by connecting it to the closest sample already in the tree.RRTs, developed by...
, a fractal space-filling pattern used as a data structure for searching high-dimensional spaces - Brownian treeBrownian treeA Brownian tree, whose name is derived from Robert Brown via Brownian motion, is a form of computer art that was briefly popular in the 1990s, when home computers started to have sufficient power to simulate Brownian motion...
, a fractal tree structure created by diffusion-limited aggregation processes - Random forestRandom forestRandom forest is an ensemble classifier that consists of many decision trees and outputs the class that is the mode of the class's output by individual trees. The algorithm for inducing a random forest was developed by Leo Breiman and Adele Cutler, and "Random Forests" is their trademark...
, a machine-learning classifier based on choosing random subsets of variables for each tree and using the most frequent tree output as the overall classification - Branching processBranching processIn probability theory, a branching process is a Markov process that models a population in which each individual in generation n produces some random number of individuals in generation n + 1, according to a fixed probability distribution that does not vary from individual to...
, a model of a population in which each individual has a random number of children