Random tree

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

Random trees are trees built by chance. In math and computer science, a tree is a network of nodes connected by edges with no cycles. A random tree uses randomness to decide how the branches grow. There are several common models:

- Galton–Watson trees: each node creates a random number of children according to a fixed distribution.
- Uniform random labeled trees: all ways to label a tree with n nodes are equally likely (there are n^(n-2) such trees).
- Random recursive trees: a new node attaches to a randomly chosen existing node.
- Random plane trees: the order of children matters, producing different shapes.
- Random binary search trees: built by inserting keys in random order.

These models help researchers study typical features of trees, like how tall they get or how many nodes lie on average on a path.