# Przeszukiwanie losowe

## English translation: random/randomized search

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.

GLOSSARY ENTRY (DERIVED FROM QUESTION BELOW)
 Polish term or phrase: Przeszukiwanie losowe English translation: random/randomized search Entered by:

 14:39 Apr 25, 2018
Polish to English translations [Non-PRO]
Tech/Engineering - Games / Video Games / Gaming / Casino / Computer games development
 Polish term or phrase: Przeszukiwanie losowe Praca dyplomowa dotyczy metod przeszukiwania losowego w projektowaniu gier komputerowych. Pytanie dotyczy ogólnego terminu "Przeszukiwanie losowe" Zbliżony termin "binary search tree" - przeszukiwanie drzewa gry "W kolejnym punkcie pierwszego rozdziału pojawia się wyjaśnienie pojęcia przeszukiwanie losowe, opis wybranych algorytmów oraz wybrane techniki wspomagające przeszukiwania drzewa gry"
 Katarzyna Wolnicka-ErsesPoland
 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
Selected response from:

Frank Szmulowicz, Ph. D.
United States
Local time: 07:01
 Thank you very much for a prompt answer. It saved my day. 4 KudoZ points were awarded for this answer

3random/randomized search
 Frank Szmulowicz, Ph. D.

22 mins   confidence:
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

 Frank Szmulowicz, Ph. D.United StatesLocal time: 07:01Native speaker of: English, PolishPRO pts in category: 4
 Thank you very much for a prompt answer. It saved my day.

## KudoZ™ translation help

The KudoZ network provides a framework for translators and others to assist each other with translations or explanations of terms and short phrases.