| dbo:abstract
|
- 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. Všechny obvyklé operace na binárních vyhledávacích stromech jsou spojeny s jednou základní, které se říká splay. Splay uzlu přeuspořádá strom tak, že se daný uzel dostane do kořene. Způsob, jak toho docílit, je provést standardní vyhledávání daného uzlu v binárním stromu a následně provést speciální takové, aby se uzel dostal do kořene. (cs)
- 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 für diese Sequenz. Diese Eigenschaft bezeichnet man als „statische Optimalität“. Es wird vermutet, dass die asymptotische Laufzeit der Anfragesequenz auch äquivalent zu der einer optimalen dynamischen Datenstruktur ist. Diese Vermutung ist als „dynamische Optimalität“ bekannt und gilt als eines der bekanntesten offenen Probleme auf dem Gebiet der Datenstrukturen. Splay-Bäume wurden 1985 von Daniel Sleator und Robert Tarjan unter dem Namen Self-Adjusting Binary Search Trees vorgestellt. (de)
- 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. Toutes les opérations courantes sur les structures de données sont suivies d'une opération basique nommée évasement (splaying en anglais). Évaser un arbre autour d'un certain élément consiste à réarranger l'arbre afin que cet élément soit placé à la racine tout en conservant la structure ordonnée de l'arbre. Une manière d'obtenir cela est d'effectuer une recherche ordinaire sur un arbre binaire en mémorisant le chemin suivi, puis d'effectuer une série de rotations d'arbre afin d'amener l'élément à la racine. D'autres implémentations permettent d'effectuer ces deux opérations en une seule passe. (fr)
- 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. Todas las operaciones normales de un árbol binario de búsqueda son combinadas con una operación básica, llamada biselación. Esta operación consiste en reorganizar el árbol para un cierto elemento, colocando éste en la raíz. Una manera de hacerlo es realizando primero una búsqueda binaria en el árbol para encontrar el elemento en cuestión y, a continuación, usar rotaciones de árboles de una manera específica para traer el elemento a la cima. Alternativamente, un algoritmo "de arriba abajo" puede combinar la búsqueda y la reorganización del árbol en una sola fase. (es)
- 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 self-adjusting binary search tree, even one selected to fit that pattern. The splay tree was invented by Daniel Sleator and Robert Tarjan in 1985. All normal operations on a binary search tree are combined with one basic operation, called splaying. Splaying the tree for a certain element rearranges the tree so that the element is placed at the root of the tree. One way to do this with the basic search operation is to first perform a standard binary tree search for the element in question, and then use tree rotations in a specific fashion to bring the element to the top. Alternatively, a top-down algorithm can combine the search and the tree reorganization into a single phase. (en)
- 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)
- 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 è . Gli alberi splay sono preferiti per l'implementazione di cache, in cui le informazioni non sono accedute uniformemente (accesso casuale), ma una parte degli elementi vengono acceduti più frequentementente di altri (accesso localizzato). Ad ogni accesso l'algoritmo splay sposta tale nodo alla radice, e di conseguenza gli elementi acceduti più frequentemente si trovano sempre vicino alla radice dell'albero, rendendi più velocemente accessibili e migliorando sensibilmente i tempi di accesso globali alla cache nelle operazioni di ricerca e cancellazione. Nonostante il vantaggio prestazionale rispetto a un Albero AVL, esistono più implementazioni e migliori librerie del secondo tipo, per la sua maggiore semplicità e per il fatto che il collo di bottiglia di molte cache è l'accesso al disco (più lento di tre ordini di grandezza) e non le operazioni sulla struttura dati. (it)
- 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. W porównaniu do innych drzew BST, drzewa splay zmieniają swoją strukturę również podczas wyszukiwana kluczy (a nie tylko dodawania lub usuwania), przesuwając znaleziony węzeł w kierunku korzenia, dzięki temu często wyszukiwane węzły stają się szybsze do znalezienia. Z tego powodu drzewa splay bywają wykorzystywane w systemach typu cache. Drzewa splay nie są samorównoważące, ponieważ ich wysokość nie jest ograniczona przez – można np. tak wykonać operacje, że drzewo zdegeneruje się do listy. Podstawowe operacje na drzewie splay, tj. wyszukiwanie elementu oraz wstawianie i usuwanie, są wykonywane w zamortyzowanym czasie gdzie jest liczbą elementów w drzewie. Oznacza to, że dla dowolnego ciągu operacji na drzewie splay, łączny koszt wykonania tych operacji jest rzędu (pl)
- 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 tree) є двійковим деревом пошуку, у якому підтримується збалансованість. Це дерево належить до класу «саморегульованих дерев», які підтримують необхідний баланс галуження дерева, щоб забезпечити виконання операції пошуку, додавання і видалення за логарифмічний час від числа елементів, що зберігаються. Це реалізується без використання яких-небудь додаткових полів у вузлах дерева (як, наприклад, в Червоно-чорних деревах або АВЛ-деревах, де у вершинах зберігається, відповідно, колір вершини і глибина піддерева). Замість цього «розширювальні операції» (splay operation), частиною яких є повороти дерева, які виконуються при кожному зверненні до дерева. Облікова вартість з розрахунку на одну операцію з деревом складає . Розширюване дерево придумали і в 1985 році. (uk)
- Расширяющееся (англ. splay tree) или косое дерево является двоичным деревом поиска, в котором поддерживается свойство сбалансированности. Это дерево принадлежит классу «саморегулирующихся деревьев», которые поддерживают необходимый баланс ветвления дерева, чтобы обеспечить выполнение операций поиска, добавления и удаления за логарифмическое время от числа хранимых элементов. Это реализуется без использования каких-либо дополнительных полей в узлах дерева (как, например, в Красно-чёрных деревьях или АВЛ-деревьях, где в вершинах хранится, соответственно, цвет вершины и глубина поддерева). Вместо этого «расширяющие операции» (splay operation), частью которых являются вращения, выполняются при каждом обращении к дереву. в расчёте на одну операцию с деревом составляет . Расширяющееся дерево придумали Роберт Тарьян и в 1983 году. (ru)
|
| 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)
|
