Information | |
---|---|
has gloss | eng: 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, both on trees with a fixed number n of nodes: 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. |
lexicalization | eng: random binary tree |
instance of | e/Binary tree |
Lexvo © 2008-2024 Gerard de Melo. Contact Legal Information / Imprint