| dbo:abstract
|
- In der Informatik ist ein Treap (gebildet aus binary search Tree, Binärer Suchbaum + Heap, wörtlich Haufen, Halde) ein binärer Suchbaum. Jeder Knoten x besteht aus zwei Elementen:
* x.key (Element)
* x.priority (Priorität) Treaps wurden im Jahr 1989 von und (Universität des Saarlandes) erfunden. Eine alternative Bezeichnung ist Balde (gebildet aus Baum und Halde). (de)
- En Ciencias de la Computación, el treap y el árbol binario de búsqueda aleatorio son dos formas de árbol binario de búsqueda estrechamente relacionadas que mantienen un conjunto dinámico de llaves ordenadas y permiten búsqueda binaria sobre las llaves almacenadas. Después de una secuencia de inserciones y borrados de llaves, la forma del treap es una variable aleatoria con la misma distribución de probabilidad que un árbol binario de búsqueda aleatorio; en particular, con alta probabilidad, su altura es proporcional al logaritmo del número de llaves, de modo que cada operación de búsqueda, inserción, o borrado toma tiempo logarítmico. (es)
- En informatique, les notions de treap ou arbretas et d'arbres binaires de recherche randomisés sont deux formes très proche d'arbre binaire de recherche, des structures de données qui maintiennent un ensemble dynamique de clés ordonnées et permettent d'effectuer une recherche binaire parmi ces clés. Après une séquence quelconque d'insertion et de suppression des clés, la forme de l'arbre est une variable aléatoire dont la distribution de probabilité est la même que celle d'un arbre binaire aléatoire; en particulier, sa hauteur est proportionnelle au logarithme de son nombre de nœuds selon une forte probabilité, de sorte que chaque opération de recherche, d'insertion, ou de suppression s'effectue en un temps logarithmique. (fr)
- In 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. After any sequence of insertions and deletions of keys, the shape of the tree is a random variable with the same probability distribution as a random binary tree; in particular, with high probability its height is proportional to the logarithm of the number of keys, so that each search, insertion, or deletion operation takes logarithmic time to perform. (en)
- Treap (ツリープ)は、乱択アルゴリズムを使用した平衡2分探索木の1つ。1989年に Cecilia R. Aragon と Raimund Seidel が発表した。平衡2分探索木のアルゴリズムの中ではアルゴリズムが単純であり、コード量が少なくてすむ。Treap という名称は Tree (木構造)と Heap (ヒープ)という2つの単語を組み合わせて作られた。 (ja)
- In informatica, il treap è un particolare tipo di che mette insieme le tipiche caratteristiche di un albero binario di ricerca e quelle di un heap. Ogni nodo dell'albero ha un valore, come ogni altro nodo di un ABR. Oltre al valore, è aggiunto un campo priorità, che è un numero casuale scelto in modo indipendente per ogni nodo. (it)
- Drzewiec – forma binarnego drzewa poszukiwań pozwalająca na wyszukiwanie binarne wśród kluczy. Po każdej sekwencji wstawień i usunięć kluczy kształt drzewa wyraża się zmienną losową z jednakowym prawdopodobieństwem dystrybucji, jak przy drzewach losowych; w szczególności, z dużym prawdopodobieństwem, jego wysokość jest proporcjonalna do logarytmu ilości kluczy tak, że każde wyszukiwanie, wstawianie lub usuwanie trwa przez czas logarytmiczny. Drzewiec został po raz pierwszy przedstawiony przez i w 1989 roku. Nazwa ta jest zbitką wyrazów „drzewo” i „kopiec”. (pl)
- 樹堆（英語：Treap），是計算機科學中術語。是有一个随机附加域满足堆的性质的二叉搜索树，其結構相当于以随机數據插入的二叉搜索树。其基本操作的期望時間複雜度为。相對於其他的平衡二叉搜索樹，Treap的特点是實現簡單，且能基本實現隨機平衡的結構。属于弱平衡树。 (zh)
- Дека́ртово де́рево — это двоичное дерево, в узлах которого хранятся:
* ссылки на правое и левое поддерево;
* ссылка на родительский узел (необязательно);
* ключи x и y, которые являются двоичным деревом поиска по ключу x и двоичной кучей по ключу y; а именно, для любого узла дерева n:
* ключи x узлов правого (левого) поддерева больше (меньше) либо равны ключу x узла n;
* ключи y узлов правого и левого детей больше либо равны ключу y узла n. Ссылка на родительский узел не обязательна, она желательна только для линейного алгоритма построения дерева. Декартово дерево не является в обычном смысле, и применяют его по следующим причинам:
* Проще реализуется по сравнению, например, с настоящими самобалансирующимися деревьями вроде красно-чёрного.
* Хорошо ведёт себя «в среднем», если ключи y раздать случайно.
* Типичная для сортирующего дерева операция «разделить по ключу x на „меньше x0“ и „не меньше x0“» работает за O(h), где h — высота дерева. На красно-чёрных деревьях придётся восстанавливать балансировку и окраску узлов. Недостатки декартового дерева:
* Большие накладные расходы на хранение: вместе с каждым элементом хранятся два-три указателя и случайный ключ y.
* Скорость доступа O(n) в худшем, хотя и маловероятном, случае. Поэтому декартово дерево недопустимо, например, в ядрах ОС. (ru)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 23051 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:buildAvg
| |
| dbp:buildWorst
| |
| dbp:deleteAvg
| |
| dbp:deleteWorst
| |
| dbp:insertAvg
| |
| dbp:insertWorst
| |
| dbp:name
| |
| dbp:searchAvg
| |
| dbp:searchWorst
| |
| dbp:spaceAvg
| |
| dbp:spaceWorst
| |
| dbp:type
|
- Randomized binary search tree (en)
|
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- In der Informatik ist ein Treap (gebildet aus binary search Tree, Binärer Suchbaum + Heap, wörtlich Haufen, Halde) ein binärer Suchbaum. Jeder Knoten x besteht aus zwei Elementen:
* x.key (Element)
* x.priority (Priorität) Treaps wurden im Jahr 1989 von und (Universität des Saarlandes) erfunden. Eine alternative Bezeichnung ist Balde (gebildet aus Baum und Halde). (de)
- En Ciencias de la Computación, el treap y el árbol binario de búsqueda aleatorio son dos formas de árbol binario de búsqueda estrechamente relacionadas que mantienen un conjunto dinámico de llaves ordenadas y permiten búsqueda binaria sobre las llaves almacenadas. Después de una secuencia de inserciones y borrados de llaves, la forma del treap es una variable aleatoria con la misma distribución de probabilidad que un árbol binario de búsqueda aleatorio; en particular, con alta probabilidad, su altura es proporcional al logaritmo del número de llaves, de modo que cada operación de búsqueda, inserción, o borrado toma tiempo logarítmico. (es)
- En informatique, les notions de treap ou arbretas et d'arbres binaires de recherche randomisés sont deux formes très proche d'arbre binaire de recherche, des structures de données qui maintiennent un ensemble dynamique de clés ordonnées et permettent d'effectuer une recherche binaire parmi ces clés. Après une séquence quelconque d'insertion et de suppression des clés, la forme de l'arbre est une variable aléatoire dont la distribution de probabilité est la même que celle d'un arbre binaire aléatoire; en particulier, sa hauteur est proportionnelle au logarithme de son nombre de nœuds selon une forte probabilité, de sorte que chaque opération de recherche, d'insertion, ou de suppression s'effectue en un temps logarithmique. (fr)
- In 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. After any sequence of insertions and deletions of keys, the shape of the tree is a random variable with the same probability distribution as a random binary tree; in particular, with high probability its height is proportional to the logarithm of the number of keys, so that each search, insertion, or deletion operation takes logarithmic time to perform. (en)
- Treap (ツリープ)は、乱択アルゴリズムを使用した平衡2分探索木の1つ。1989年に Cecilia R. Aragon と Raimund Seidel が発表した。平衡2分探索木のアルゴリズムの中ではアルゴリズムが単純であり、コード量が少なくてすむ。Treap という名称は Tree (木構造)と Heap (ヒープ)という2つの単語を組み合わせて作られた。 (ja)
- In informatica, il treap è un particolare tipo di che mette insieme le tipiche caratteristiche di un albero binario di ricerca e quelle di un heap. Ogni nodo dell'albero ha un valore, come ogni altro nodo di un ABR. Oltre al valore, è aggiunto un campo priorità, che è un numero casuale scelto in modo indipendente per ogni nodo. (it)
- Drzewiec – forma binarnego drzewa poszukiwań pozwalająca na wyszukiwanie binarne wśród kluczy. Po każdej sekwencji wstawień i usunięć kluczy kształt drzewa wyraża się zmienną losową z jednakowym prawdopodobieństwem dystrybucji, jak przy drzewach losowych; w szczególności, z dużym prawdopodobieństwem, jego wysokość jest proporcjonalna do logarytmu ilości kluczy tak, że każde wyszukiwanie, wstawianie lub usuwanie trwa przez czas logarytmiczny. Drzewiec został po raz pierwszy przedstawiony przez i w 1989 roku. Nazwa ta jest zbitką wyrazów „drzewo” i „kopiec”. (pl)
- 樹堆（英語：Treap），是計算機科學中術語。是有一个随机附加域满足堆的性质的二叉搜索树，其結構相当于以随机數據插入的二叉搜索树。其基本操作的期望時間複雜度为。相對於其他的平衡二叉搜索樹，Treap的特点是實現簡單，且能基本實現隨機平衡的結構。属于弱平衡树。 (zh)
- Дека́ртово де́рево — это двоичное дерево, в узлах которого хранятся:
* ссылки на правое и левое поддерево;
* ссылка на родительский узел (необязательно);
* ключи x и y, которые являются двоичным деревом поиска по ключу x и двоичной кучей по ключу y; а именно, для любого узла дерева n:
* ключи x узлов правого (левого) поддерева больше (меньше) либо равны ключу x узла n;
* ключи y узлов правого и левого детей больше либо равны ключу y узла n. Ссылка на родительский узел не обязательна, она желательна только для линейного алгоритма построения дерева. Недостатки декартового дерева: (ru)
|
| rdfs:label
|
- Treap (de)
- Treap (es)
- Treap (fr)
- Treap (it)
- Treap (ja)
- Drzewiec (informatyka) (pl)
- Treap (en)
- Декартово дерево (ru)
- 树堆 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
