| dbpedia-owl:abstract
|
- In computer science, an AVL tree is a self-balancing binary search tree, and it was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations. The AVL tree is named after its two Soviet inventors, G.M. Adelson-Velskii and E.M. Landis, who published it in their 1962 paper "An algorithm for the organization of information. " The balance factor of a node is the height of its left subtree minus the height of its right subtree (sometimes opposite) and a node with balance factor 1, 0, or −1 is considered balanced. A node with any other balance factor is considered unbalanced and requires rebalancing the tree. The balance factor is either stored directly at each node or computed from the heights of the subtrees. AVL trees are often compared with red-black trees because they support the same set of operations and because red-black trees also take O(log n) time for the basic operations. Because AVL trees are more rigidly balanced, they are faster than red-black trees for lookup intensive applications. However, it looks like red-black trees could have been faster for insertion and element removal.
- Datei:AVL-tree-wBalance. svg AVL-Baum mit Balance-Werten (blau) Der AVL-Baum ist eine Datenstruktur in der Informatik, genauer ein balancierter binärer Suchbaum. Als Invariante beim AVL-Baum gilt, dass sich für jeden Knoten die Höhen der beiden Teilbäume um höchstens unterscheiden. Diese Bedingung verhindert (bei einem moderaten Aufwand), dass der Baum zu sehr aus der Balance gerät. Die Höhe eines AVL-Baums mit n Knoten liegt in O(log n) und damit auch die maximale Anzahl der Schritte, um ein Element zu finden oder festzustellen, dass es nicht enthalten ist. Der Name AVL leitet sich von den Erfindern Adelson-Welski und Landis ab, die diese Datenstruktur 1962 entwickelten. Der AVL-Baum ist damit die älteste Datenstruktur für balancierte Bäume. Eine Alternative mit schwächeren Bedingungen ist der Rot-Schwarz-Baum.
- Árbol AVL es un tipo especial de árbol binario ideado por los matemáticos rusos Adelson-Velskii y Landis. Fue el primer árbol de búsqueda binario auto-balanceable que se ideó.
- Tietojenkäsittelytieteessä AVL-puu on binäärinen hakupuu. Se on ensimmäinen tietojenkäsittelytieteessä esitetty itsestään tasapainottuva binäärinen hakupuu. AVL-puussa kaikkien solmujen alipuiden korkeusero on korkeintaan yksi. Haun, lisäyksen ja poiston asymptoottinen suoritusaika on O(log n) sekä keskimääräisessä että pahimmassa tapauksessa. Lisäykset ja poistot saattavat vaatia puun tasapainottamisen uudelleen yhdellä tai useammalla kierrolla. AVL-puu on nimetty keksijöidensä Georgi Adelson-Velskin ja Jevgeni Landisin mukaan. He esittelivät puun vuonna 1962 artikkelissaan ”An algorithm for the organization of information. ”
- L'albero AVL è, in informatica, un particolare tipo di albero bilanciato che possiede, oltre alle caratteristiche tipiche di un albero bilanciato, il coefficiente di bilanciamento definito per ogni nodo (vedi più in basso). In realtà si tratta di un albero approssimativamente bilanciato, cioè tale che i coefficienti di bilanciamento siano 1, 0 oppure -1 (nel caso ideale di albero AVL bilanciato tutti i coefficienti di bilanciamento sono uguali a 0). La condizione per tenerlo bilanciato è semplice: per ogni nodo dell'albero, la differenza di altezza dei suoi sottoalberi figli deve differire al massimo di uno. Grazie a questa restrizione, l'altezza massima dell'albero, ossia la più grande distanza tra la radice e le foglie, è logaritmica nel numero dei nodi. È per questo che questa struttura di dati permette di compiere l'inserimento, la ricerca e l'eliminazione di un elemento in O(log n). Inoltre se si considerano i costi ammortizzati di una serie di inserzioni, questi sono O(1). Il nome AVL viene dai suoi inventori Georgij Adelson-Velskij e Evgenij Landis, che pubblicarono il loro algoritmo nel saggio in russo "Odin algoritm organizacii informacii" ("un algoritmo di organizzazione dell'informazione") del 1962. Per evitare di dover contare ogni volta l'altezza di un sottoalbero, si salva nel nodo il coefficiente di bilanciamento di un nodo, che è definito come la differenza tra l'altezza del sottoalbero SINISTRO e quella del sottoalbero DESTRO del nodo considerato.
- AVL木（えーぶいえるき、AVL-tree）は、コンピュータプログラムにおけるデータ構造、特に木構造の一つ。AVL木平衡条件を満たす平衡2分探索木である。左右の部分木の高さの差を多くとも1にする。 このAVL木を平衡2分木と呼ぶことがあるが、平衡2分探索木と混同して使用されることが多い。
- Drzewo AVL, nazywane również drzewem dopuszczalnym, to zrównoważone binarne drzewo poszukiwań (BST), w którym wysokość lewego i prawego poddrzewa każdego węzła różni się co najwyżej o jeden. Nazwa AVL pochodzi od nazwisk rosyjskich matematyków: Adelsona-Velskiego oraz Landisa, którzy zaproponowali rozwiązanie problemu utrzymania dobrego drzewa wyszukiwań w roku 1962 . Drzewo AVL pozostaje drzewem BST, co oznacza, że wierzchołki są uporządkowane w określony sposób. Zazwyczaj przyjmuje się, iż elementy w lewym poddrzewie są mniejsze od wierzchołka, zaś w prawym - większe. Zrównoważenie drzewa osiąga się przypisując każdemu węzłowi współczynnik wyważenia, który jest równy różnicy wysokości lewego i prawego poddrzewa. Może wynosić 0, +1 lub -1. Wstawiając lub usuwając elementy drzewa (tak aby zachować własności drzewa BST) modyfikuje się też współczynnik wyważenia, a gdy przyjmie on niedozwoloną wartość wykonuje specjalną operację rotacji węzłów, która przywraca zrównoważenie. Koszt modyfikacji drzewa jest nieco większy niż dla zwykłego drzewa BST, ale za to własności drzewa AVL gwarantują, że pesymistyczny czas wyszukiwania elementu w drzewie o n węzłach wynosi 1.44(log2n), podczas gdy dla niezrównoważonego BST (w postaci listy) czas ten wynosi n. Drzewa AVL są często porównywane z czerwono-czarnymi drzewami, ponieważ pozwalają na wykonanie tych samych operacji (dodawanie, usuwanie oraz wyszukiwanie elementów) o równej co do rzędu pesymistycznej złożoności czasowej O(log n). Przy powtarzających się wyszukiwaniach drzewa AVL są jednak wydajniejsze. W wielu praktycznych zastosowaniach zdarza się, że do części obiektów sięga się częściej niż do pozostałych, przykładem może być słownik. Wówczas lepszym rozwiązaniem jest zastosowanie optymalnego drzewa poszukiwań. Podobnie jak w BST, nie jest możliwe, by drzewo posiadało dwa równe elementy. Zazwyczaj oznacza to, iż elementy muszą posiadać unikalny klucz identyfikacyjny; problem polega na tym, że drzewa z równymi elementami - nawet po zmodyfikowaniu porządku dzielącego elementy do lewych i prawych poddrzew - nie da się później zrównoważyć. Problem ten można rozwiązać na przykład przez przechowywanie w węzłach drzewa list zawierających elementy o identycznych kluczach.
- Árvore AVL (ou árvore balanceada pela altura), em Ciência da Computação, é uma árvore de busca binária auto-balanceada. Em tal árvore, as alturas das duas sub-árvores a partir de cada nó difere no máximo em uma unidade. As operações de busca, inserção e remoção de elementos possuem complexidade (no qual é o número de elementos da árvore). Inserções e remoções podem também requerer o rebalanceamento da árvore, exigindo uma ou mais rotações. O nome AVL vem de seus criadores Adelson Velsky e Landis, e sua primeira referência encontra-se no documento "Algoritmos para organização da informação" de 1962. Não acoselharia o uso de árvores completas, pois o seu tempo de processamento seria bastante elevado, melhor caso seria utilizar arvores AVL. Pois para todo nó de uma arvore binária de busca suas alturas(grau) das subárvores esquerda e direita sejam iguais ou diferentes a uma unidade.
- AVL-träd, är en datastruktur i form av ett balanserat binärt sökträd där höjden av två underträd högst skiljer sig med ett. Sökning, insättning och radering har tidskomplexitet O(log n) där n är antalet noder
- 在计算机科学中，AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G.M. Adelson-Velsky和E.M. Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了它。 节点的平衡因子是它的右子树的高度减去它的左子树的高度。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。
- АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1. АВЛ — аббревиатура, образованная первыми буквами создателей (советских учёных) Адельсон-Вельскго, Георгия Максимовича и Е. М. Ландиса.
- Fichier:Unbalanced binary tree. svg Un exemple d'arbre non-AVL. En informatique théorique, les arbres AVL ont été historiquement les premiers arbres binaires de recherche automatiquement équilibrés. Dans un arbre AVL, les hauteurs des deux sous-arbres d'un même nœud diffèrent au plus de un. La recherche, l'insertion et la suppression sont toutes en dans le pire des cas. L'insertion et la suppression nécessitent d'effectuer des rotations. La dénomination "arbre AVL" provient des noms de ses deux inventeurs, respectivement Georgii Adelson-Velsky et Evguenii Landis, qui l'ont publié en 1962 sous le titre An algorithm for the organization of information. Le facteur d'équilibrage d'un nœud est la différence entre la hauteur de son sous-arbre droit et celle de son sous-arbre gauche. Un nœud dont le facteur d'équilibrage est 1, 0, ou -1 est considéré comme équilibré. Un nœud avec tout autre facteur est considéré comme déséquilibré et requiert un rééquilibrage. Le facteur d'équilibrage est soit calculé à partir des hauteurs des sous-arbres, soit stocké dans chaque nœud de l'arbre (ce qui permet un gain de place, ce facteur pouvant être stocké sur deux bits, mais complexifie les opérations d'insertion et de suppression). Fichier:AVLtreef. svg Le même arbre après un rééquilibrage.
|
| rdfs:comment
|
- Árbol AVL es un tipo especial de árbol binario ideado por los matemáticos rusos Adelson-Velskii y Landis. Fue el primer árbol de búsqueda binario auto-balanceable que se ideó.
- AVL木（えーぶいえるき、AVL-tree）は、コンピュータプログラムにおけるデータ構造、特に木構造の一つ。AVL木平衡条件を満たす平衡2分探索木である。左右の部分木の高さの差を多くとも1にする。 このAVL木を平衡2分木と呼ぶことがあるが、平衡2分探索木と混同して使用されることが多い。
- AVL-träd, är en datastruktur i form av ett balanserat binärt sökträd där höjden av två underträd högst skiljer sig med ett. Sökning, insättning och radering har tidskomplexitet O(log n) där n är antalet noder
- 在计算机科学中，AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G.M. Adelson-Velsky和E.M. Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了它。 节点的平衡因子是它的右子树的高度减去它的左子树的高度。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。
- АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1. АВЛ — аббревиатура, образованная первыми буквами создателей (советских учёных) Адельсон-Вельскго, Георгия Максимовича и Е. М. Ландиса.
- Datei:AVL-tree-wBalance. svg AVL-Baum mit Balance-Werten (blau) Der AVL-Baum ist eine Datenstruktur in der Informatik, genauer ein balancierter binärer Suchbaum. Als Invariante beim AVL-Baum gilt, dass sich für jeden Knoten die Höhen der beiden Teilbäume um höchstens unterscheiden. Diese Bedingung verhindert (bei einem moderaten Aufwand), dass der Baum zu sehr aus der Balance gerät.
- In computer science, an AVL tree is a self-balancing binary search tree, and it was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.
- Tietojenkäsittelytieteessä AVL-puu on binäärinen hakupuu. Se on ensimmäinen tietojenkäsittelytieteessä esitetty itsestään tasapainottuva binäärinen hakupuu. AVL-puussa kaikkien solmujen alipuiden korkeusero on korkeintaan yksi. Haun, lisäyksen ja poiston asymptoottinen suoritusaika on O(log n) sekä keskimääräisessä että pahimmassa tapauksessa. Lisäykset ja poistot saattavat vaatia puun tasapainottamisen uudelleen yhdellä tai useammalla kierrolla.
- L'albero AVL è, in informatica, un particolare tipo di albero bilanciato che possiede, oltre alle caratteristiche tipiche di un albero bilanciato, il coefficiente di bilanciamento definito per ogni nodo (vedi più in basso). In realtà si tratta di un albero approssimativamente bilanciato, cioè tale che i coefficienti di bilanciamento siano 1, 0 oppure -1 (nel caso ideale di albero AVL bilanciato tutti i coefficienti di bilanciamento sono uguali a 0).
- Drzewo AVL, nazywane również drzewem dopuszczalnym, to zrównoważone binarne drzewo poszukiwań (BST), w którym wysokość lewego i prawego poddrzewa każdego węzła różni się co najwyżej o jeden. Nazwa AVL pochodzi od nazwisk rosyjskich matematyków: Adelsona-Velskiego oraz Landisa, którzy zaproponowali rozwiązanie problemu utrzymania dobrego drzewa wyszukiwań w roku 1962 . Drzewo AVL pozostaje drzewem BST, co oznacza, że wierzchołki są uporządkowane w określony sposób.
- Árvore AVL (ou árvore balanceada pela altura), em Ciência da Computação, é uma árvore de busca binária auto-balanceada. Em tal árvore, as alturas das duas sub-árvores a partir de cada nó difere no máximo em uma unidade. As operações de busca, inserção e remoção de elementos possuem complexidade (no qual é o número de elementos da árvore). Inserções e remoções podem também requerer o rebalanceamento da árvore, exigindo uma ou mais rotações.
- Fichier:Unbalanced binary tree. svg Un exemple d'arbre non-AVL. En informatique théorique, les arbres AVL ont été historiquement les premiers arbres binaires de recherche automatiquement équilibrés. Dans un arbre AVL, les hauteurs des deux sous-arbres d'un même nœud diffèrent au plus de un. La recherche, l'insertion et la suppression sont toutes en dans le pire des cas. L'insertion et la suppression nécessitent d'effectuer des rotations.
|
