| rdfs:comment
| - Een splayboom is een zelf-balancerende binaire zoekboom, met de extra eigenschap dat vaak bezochte toppen dichter bij de wortel zitten (en dus sneller gevonden worden). Standaardbewerkingen zoals toevoegen, opzoeken en verwijderen van een top worden uitgevoerd in O(n) tijd voor één bewerking, maar geamortiseerd in O(log(n)) tijd voor een reeks van n bewerkingen. Voor vele niet (volledig) willekeurig reeksen van bewerkingen presteren splaybomen beter dan standaard binaire zoekbomen, voornamelijk wanneer een relatief kleine deelverzameling van de toppen van de boom vaak bezocht worden.Alle bewerkingen op een splayboom worden uitgevoerd zoals bij een normale binaire zoekboom, maar ze worden gevolgd door een splaystap.De splayboom is ontwikkeld door en Robert Tarjan (nl)
- スプレー木（スプレーき、英: splay tree）は、平衡2分探索木の一種で、最近アクセスした要素に素早く再アクセスできるという特徴がある。挿入、参照、削除といった基本操作を O(log(n)) の償却時間で実行できる。多くの一様でない一連の操作において、その順序パターンが未知の場合でも、スプレー木は他の探索木よりもよい性能を示す。スプレー木はダニエル・スレイターとロバート・タージャンが発明した。 2分探索木の通常のあらゆる操作は、「スプレー操作」という1つの基本操作と組み合わせられる。スプレー操作とは、特定の要素が木の根に位置するよう再配置を行うことである。そのためには、まず通常の2分探索木での要素の探索を行い、次にその要素がトップになるように木の回転を行う。別の方法として、トップダウンアルゴリズムで探索と木の再配置を単一フェーズに統合することもできる。 (ja)
- Uma árvore splay é uma árvore binária de busca autoajustável, com a propriedade adicional de tornar os elementos recentemente acessados, fáceis de acesso novamente, pois os mantém em sua raiz. Suas operações básicas, como remoção e inserção, são executadas em O(log n). Todas as suas operações colocam o elemento envolvido na operação na raiz, através de . Para muitas sequências de operações não aleatórias, as árvores splay têm melhor desempenho do que outras árvores de busca, mesmo quando o padrão específico da sequência é desconhecido. A árvore splay foi inventada por Daniel Sleator e Robert Tarjan em 1985. (pt)
- 伸展树（英語：Splay Tree）是一种能够自我平衡的二叉查找树，它能在均摊的时间内完成基于伸展（Splay）操作的插入、查找、修改和删除操作。它是由（Daniel Sleator）和羅伯特·塔揚在1985年发明的。 在伸展树上的一般操作都基于伸展操作：假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法，在每次查找之后对树进行調整，把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。 它的优势在于不需要记录用于平衡树的冗余信息。 (zh)
- Splay strom je samovyvažující se binární vyhledávací strom mající tu vlastnost, že prvky, k nimž se nedávno přistupovalo, jsou rychle znovu dostupné. Provádí základní operace jako vkládání, vyhledávání a odstraňování prvků v amortizovaném čase O(log n). Pro mnoho nerovnoměrných posloupností operací pracují splay stromy lépe než ostatní vyhledávací stromy, a to i v případě, že charakteristika posloupnosti není předem známá. Splay strom byl vynalezen a Robertem Tarjanem. (cs)
- Un Árbol biselado o Árbol Splay es un Árbol binario de búsqueda auto-balanceable, con la propiedad adicional de que a los elementos accedidos recientemente se accederá más rápidamente en accesos posteriores. Realiza operaciones básicas como pueden ser la inserción, la búsqueda y el borrado en un tiempo del orden de O(log n). Para muchas secuencias no uniformes de operaciones, el árbol biselado se comporta mejor que otros árboles de búsqueda, incluso cuando el patrón específico de la secuencia es desconocido. Esta estructura de datos fue inventada por Robert Tarjan y Daniel Sleator. (es)
- In der Informatik ist ein Splay-Baum (auch Spreizbaum genannt, englisch splay tree) ein spezieller Typ eines binären Suchbaums. Der Splay-Baum ist eine selbst-organisierende Datenstruktur mit der Besonderheit, dass die Organisation der gespeicherten Elemente sich potentiell nicht nur bei Modifikationen (wie bei AVL-Baum und Rot-Schwarz-Baum) ändert, sondern auch bei bloßen Anfragen. Die angefragten Elemente werden in die Nähe der Wurzel „gespült“, so dass sie bei einer alsbaldigen erneuten Suche schneller gefunden werden. Alle wichtigen Operationen wie Einfügen, Suchen und Löschen werden (amortisiert) effizient ausgeführt. Für eine gegebene Anfragesequenz verhält sich der Splay-Baum bezüglich der asymptotischen Laufzeit aller Anfragen äquivalent zu einer optimalen statischen Datenstruktur (de)
- A splay tree is a binary search tree with the additional property that recently accessed elements are quick to access again. Like self-balancing binary search trees, a splay tree performs basic operations such as insertion, look-up and removal in O(log n) amortized time. For random access patterns drawn from a non-uniform random distribution, their amortized time can be faster than logarithmic, proportional to the entropy of the access pattern. For many patterns of non-random operations, also, splay trees can take better than logarithmic time, without requiring advance knowledge of the pattern. According to the unproven dynamic optimality conjecture, their performance on all access patterns is within a constant factor of the best possible performance that could be achieved by any other sel (en)
- Un albero splay è un albero binario di ricerca con la proprietà che gli elementi cui si è acceduto più di recente tendono a trovarsi più vicini alla radice. In questo modo la loro ricerca è più efficiente che in un normale albero binario e talvolta anche più che in un . Per ottenere questa proprietà, si allarga (in inglese splay) l'albero in modo che il nodo contenente la chiave cercata, viene spostato alla radice attraverso delle rotazioni. Queste rotazioni, oltre a portare il nodo alla radice, accorciano di circa la metà la distanza tra la radice e tutti i nodi visitati durante la ricerca. Tuttavia, esse non garantiscono che l'albero risultante sia bilanciato, e nel caso peggiore un accesso a un nodo può richiedere di visitare tutti i nodi dell'albero (complessità lineare); il invece è (it)
- Un arbre splay (ou arbre évasé) est un arbre binaire de recherche auto-équilibré possédant en outre la propriété que les éléments auxquels on a récemment accédé (pour les ajouter, les regarder ou les supprimer) sont rapidement accessibles. Ils disposent ainsi d'une complexité amortie en O(log n) pour les opérations courantes comme insertion, recherche ou suppression. Ainsi dans le cas où les opérations possèdent une certaine structure, ces arbres constituent des bases de données ayant de bonnes performances, et ceci reste vrai même si cette structure est a priori inconnue. Cette structure de données a été inventée par (en) et Robert Tarjan en 1985. (fr)
- Drzewo splay (drzewo rozchylane, drzewo Sleatora-Tarjana) – struktura danych w formie samodostosowującego się drzewa poszukiwań binarnych (BST), wynaleziona przez i Roberta Tarjana, reprezentująca zbiór elementów z porządkiem liniowym. Wykonywanie podstawowych operacji na drzewie splay wiąże się z wykonaniem procedury która powoduje taką zmianę struktury drzewa że węzeł zostaje umieszczony w korzeniu przy zachowaniu porządku charakterystycznego dla drzewa BST. (pl)
- Расширяющееся (англ. splay tree) или косое дерево является двоичным деревом поиска, в котором поддерживается свойство сбалансированности. Это дерево принадлежит классу «саморегулирующихся деревьев», которые поддерживают необходимый баланс ветвления дерева, чтобы обеспечить выполнение операций поиска, добавления и удаления за логарифмическое время от числа хранимых элементов. Это реализуется без использования каких-либо дополнительных полей в узлах дерева (как, например, в Красно-чёрных деревьях или АВЛ-деревьях, где в вершинах хранится, соответственно, цвет вершины и глубина поддерева). Вместо этого «расширяющие операции» (splay operation), частью которых являются вращения, выполняются при каждом обращении к дереву. (ru)
- Розширюване дерево (англ. splay tree) є двійковим деревом пошуку, у якому підтримується збалансованість. Це дерево належить до класу «саморегульованих дерев», які підтримують необхідний баланс галуження дерева, щоб забезпечити виконання операції пошуку, додавання і видалення за логарифмічний час від числа елементів, що зберігаються. Це реалізується без використання яких-небудь додаткових полів у вузлах дерева (як, наприклад, в Червоно-чорних деревах або АВЛ-деревах, де у вершинах зберігається, відповідно, колір вершини і глибина піддерева). Замість цього «розширювальні операції» (splay operation), частиною яких є повороти дерева, які виконуються при кожному зверненні до дерева. Облікова вартість з розрахунку на одну операцію з деревом складає . (uk)
|
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
![[RDF Data]](/fct/images/sw-rdf-blue.png)