GLOSSARY ENTRY (DERIVED FROM QUESTION BELOW) | ||||||
---|---|---|---|---|---|---|
|
14:39 Apr 25, 2018 |
Polish to English translations [Non-PRO] Tech/Engineering - Games / Video Games / Gaming / Casino / Computer games development | |||||||
---|---|---|---|---|---|---|---|
|
| ||||||
| Selected response from: Frank Szmulowicz, Ph. D. United States Local time: 05:52 | ||||||
Grading comment
|
Summary of answers provided | ||||
---|---|---|---|---|
3 | random/randomized search |
|
random/randomized search Explanation: In computer science and probability theory, a random binary tree is 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. Treaps and randomized binary search trees In applications of binary search tree data structures, it is rare for the values in the tree 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 insertions and deletions to be performed in a binary search tree, at each step maintaining as an invariant the property that the shape of the tree is a random variable with the same distribution as a random binary search tree. If a given set of ordered numbers is assigned numeric priorities (distinct numbers unrelated to their values), these priorities may be used to construct a Cartesian tree for the numbers, a binary tree that has as its inorder traversal sequence the sorted sequence of the numbers and that is heap-ordered by priorities. Although more efficient construction algorithms are known, it is helpful to think of a Cartesian tree as being constructed by inserting the given numbers into a binary search tree in priority order. Thus, by choosing the priorities either to be a set of independent random real numbers in the unit interval, or by choosing them to be a random permutation of the numbers from 1 to n (where n is the number of nodes in the tree), and by maintaining the heap ordering property 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 https://en.wikipedia.org/wiki/Random_binary_tree |
| |
Grading comment
| ||
Login to enter a peer comment (or grade) |
Login or register (free and only takes a few minutes) to participate in this question.
You will also have access to many other tools and opportunities designed for those who have language-related jobs (or are passionate about them). Participation is free and the site has a strict confidentiality policy.