| dbpedia-owl:abstract
|
- A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log n) amortized time. For many sequences of operations, splay trees perform better than other search trees, even when the specific pattern of the sequence is unknown. The splay tree was invented by Daniel Dominic Sleator and Robert Endre 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 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.
- In der Informatik ist ein Splay-Baum (auch Spreizbaum genannt, englisch Splay tree) eine baumartige Datenstruktur zum Verwalten verschiedener Elemente. Die Besonderheit von Splay-Bäumen ist, dass sie erwartet balanciert sind, wodurch alle wichtigen Operationen wie Einfügen, Suchen und Löschen effizient ausgeführt werden können. Splay-Bäume wurden 1985 von Daniel Sleator und Robert Tarjan unter dem Namen Self-Adjusting Binary Search Trees vorgestellt.
- 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 a abajo" puede combinar la búsqueda y la reorganización del árbol en una sola fase.
- Tietojenkäsittelytieteessä splay-puu (mukautuva puu, viistopuu, engl. splay tree) on tasapainotettu binäärihakupuu, jonka erityisominaisuus on mukautuminen: peräkkäin samoihin avaimiin kohdistuvat operaatiot ovat erityisen nopeita. Splay-puun kehittivät Daniel Sleator ja Robert Tarjan vuonna 1985.
- 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 albero bilanciato. 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 costo ammortizzato 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.
- スプレー木（スプレーき、Template:Lang-en-short）は、平衡2分探索木の一種で、最近アクセスした要素に素早く再アクセスできるという特徴がある。挿入、参照、削除といった基本操作を O(log) の償却時間で実行できる。多くの一様でない一連の操作において、その順序パターンが未知の場合でも、スプレー木は他の探索木よりもよい性能を示す。スプレー木はダニエル・スレイターとロバート・タージャンが発明した。 2分探索木の通常のあらゆる操作は、「スプレー操作」という1つの基本操作と組み合わせられる。スプレー操作とは、特定の要素が木の根に位置するよう再配置を行うことである。そのためには、まず通常の2分探索木での要素の探索を行い、次にその要素がトップになるように木の回転を行う。別の方法として、トップダウンアルゴリズムで探索と木の再配置を単一フェーズに統合することもできる。
- 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(log) tijd. 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 Daniel Sleator en Robert Tarjan
- Drzewo splay (drzewo rozchylane) – w informatyce – struktura danych w formie samodostosowującego się drzewa poszukiwań binarnych, wynaleziona przez Daniela Sleatora 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 Splay(T, x), która powoduje taką zmianę struktury drzewa T, że węzeł x 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 .
- 伸展树(Splay Tree)是一种二叉排序树，它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。 它的优势在于不需要记录用于平衡树的冗余信息。 在伸展树上的一般操作都基于伸展操作。 假设想要对一个二叉查找树执行一系列的查找操作。为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法， 在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方。splay tree应运而生。splay tree是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。
- Расширяющееся дерево является двоичным деревом поиска, в котором поддерживается свойство сбалансированности. Это дерево принадлежит классу «саморегулирующихся деревьев», которые поддерживают необходимый баланс ветвления дерева, чтобы обеспечить выполнение операций поиска, добавления и удаления за логарифмическое время от числа хранимых элементов. Это реализуется без использования каких-либо дополнительных полей в узлах дерева (как, например, в Красно-чёрных деревьях или АВЛ-деревьях, где в вершинах хранится, соответственно, цвет вершины и глубина поддерева). Вместо этого «расширяющие операции» (splay operation), частью которых являются вращения, выполняются при каждом обращении к дереву. Учётная стоимость в расчёте на одну операцию с деревом составляет . Расширяющееся дерево придумали Роберт Тарьян и Даниель Слейтор в 1983 г.
- Un arbre splay est une structure de données inventée par Sleator et Tarjan en 1985. Cette structure de données est essentiellement un arbre binaire avec des règles spéciales de mise à jour et d'accès. L'opération splay sur une valeur fait remonter le nœud visé à la racine de l'arbre tout en conservant son ordonnancement. De plus, m opérations sur un arbre de n nœuds prennent un temps O (n ln + m ln).
|
| rdfs:comment
|
- In der Informatik ist ein Splay-Baum (auch Spreizbaum genannt, englisch Splay tree) eine baumartige Datenstruktur zum Verwalten verschiedener Elemente. Die Besonderheit von Splay-Bäumen ist, dass sie erwartet balanciert sind, wodurch alle wichtigen Operationen wie Einfügen, Suchen und Löschen effizient ausgeführt werden können. Splay-Bäume wurden 1985 von Daniel Sleator und Robert Tarjan unter dem Namen Self-Adjusting Binary Search Trees vorgestellt.
- Tietojenkäsittelytieteessä splay-puu (mukautuva puu, viistopuu, engl. splay tree) on tasapainotettu binäärihakupuu, jonka erityisominaisuus on mukautuminen: peräkkäin samoihin avaimiin kohdistuvat operaatiot ovat erityisen nopeita. Splay-puun kehittivät Daniel Sleator ja Robert Tarjan vuonna 1985.
- スプレー木（スプレーき、Template:Lang-en-short）は、平衡2分探索木の一種で、最近アクセスした要素に素早く再アクセスできるという特徴がある。挿入、参照、削除といった基本操作を O(log) の償却時間で実行できる。多くの一様でない一連の操作において、その順序パターンが未知の場合でも、スプレー木は他の探索木よりもよい性能を示す。スプレー木はダニエル・スレイターとロバート・タージャンが発明した。 2分探索木の通常のあらゆる操作は、「スプレー操作」という1つの基本操作と組み合わせられる。スプレー操作とは、特定の要素が木の根に位置するよう再配置を行うことである。そのためには、まず通常の2分探索木での要素の探索を行い、次にその要素がトップになるように木の回転を行う。別の方法として、トップダウンアルゴリズムで探索と木の再配置を単一フェーズに統合することもできる。
- 伸展树(Splay Tree)是一种二叉排序树，它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。 它的优势在于不需要记录用于平衡树的冗余信息。 在伸展树上的一般操作都基于伸展操作。 假设想要对一个二叉查找树执行一系列的查找操作。为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法， 在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方。splay tree应运而生。splay tree是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。
- A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log n) amortized time. For many sequences of operations, splay trees perform better than other search trees, even when the specific pattern of the sequence is unknown. The splay tree was invented by Daniel Dominic Sleator and Robert Endre Tarjan in 1985.
- 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).
- 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 albero bilanciato. 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.
- 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(log) tijd.
- Drzewo splay (drzewo rozchylane) – w informatyce – struktura danych w formie samodostosowującego się drzewa poszukiwań binarnych, wynaleziona przez Daniela Sleatora 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 Splay(T, x), która powoduje taką zmianę struktury drzewa T, że węzeł x zostaje umieszczony w korzeniu przy zachowaniu porządku charakterystycznego dla drzewa BST.
- Расширяющееся дерево является двоичным деревом поиска, в котором поддерживается свойство сбалансированности. Это дерево принадлежит классу «саморегулирующихся деревьев», которые поддерживают необходимый баланс ветвления дерева, чтобы обеспечить выполнение операций поиска, добавления и удаления за логарифмическое время от числа хранимых элементов.
- Un arbre splay est une structure de données inventée par Sleator et Tarjan en 1985. Cette structure de données est essentiellement un arbre binaire avec des règles spéciales de mise à jour et d'accès. L'opération splay sur une valeur fait remonter le nœud visé à la racine de l'arbre tout en conservant son ordonnancement. De plus, m opérations sur un arbre de n nœuds prennent un temps O (n ln + m ln).
|
