| dbo:abstract
|
- AVL strom je datová struktura pro uchovávání údajů a jejich vyhledávání. Pracuje v logaritmicky omezeném čase. Jedná se o samovyvažující se binární vyhledávací strom. Jméno stromu pochází z iniciál jeho objevitelů. a popsali tuto strukturu v roce 1962 v článku An algorithm for the organization of information. Dokázali, že AVL-strom bude maximálně o 45 % vyšší než dokonale vyvážený strom, složený ze stejných vrcholů. Pokud v(n) je výška AVL-stromu s n uzly, potom platí log(n+1) ≤ v(n) ≤ 1.4404 log(n+2) − 0.328. (cs)
- في علم الحاسوب، شجرة إي في إل (بالإنجليزية: AVL Trees) هي ، وهي أول بنية بيانات تم اختراعها.في شجرة AVL، ارتفاع الأشجار الجزئية لأية عقدة تختلف بواحد على الأكثر. البحث، الإدخال، والحذف يتطلبون زمن (O(log n في كل من الحالات المتوسطة والأسوء، حيث أن n هو عدد العقد في شجرة قبل العملية. الإدخال والحذف قد يستلزم إعادة توازن الشجرة عن طريق واحد أو أكثر. شجرة AVL سميت نسبة لمخترعَيها السوفيتيين، غيورغي ماكسيموفيتش أدلسن-فالسكي (Adelson-Velskii) (Landis). الذين نشراها في مقالهما سنة 1962 «خوارزمية لتنظيم المعلومات». عامل التوازن لعقدة ما هو ارتفاع الشجرة الجزئية اليسرى ناقص ارتفاع الشجرة الفرعية اليمنى (أحيانا العكس). والعقدة مع عامل توازن 1، 0 أو -1 تعتبر متوازنة. عقدة مع عامل توازن غير ذلك تعتبر غير متوازنة وتتطلب إعادة توازن الشجرة. عامل التوازن إما أن يكون محفوظا في كل عقدة، أو يتم حسابه من ارتفاعات أشجاره الجزئية. عادة ما يتم مقارنة أشجار AVL مع لأنهما يدعمان نفس العمليات، ولأن أشجار أحمر-أسود يتطلبون زمن (O(log n في العمليات الأساسية. لأن أشجار AVL صارمون بالتوازن، هم أسرع من أشجار أحمر-أسود لتطبيقات المكثفة البحث.من ناحية أخرى، أشجار أحمر-أسود هم أسرع بالإدخال والحذف. (ar)
- Der AVL-Baum ist eine Datenstruktur in der Informatik. Es handelt sich dabei um einen binären Suchbaum mit der zusätzlichen Eigenschaft, dass sich an jedem Knoten die Höhe der beiden Teilbäume um höchstens eins unterscheidet. Diese Eigenschaft lässt seine Höhe nur logarithmisch mit der Zahl der Schlüssel wachsen und macht ihn zu einem balancierten binären Suchbaum. Die maximale (und mittlere) Anzahl der Schritte (Vergleiche), die nötig sind, um An- oder Abwesenheit eines Schlüssels festzustellen, hängt direkt mit der Höhe zusammen. Ferner ist der maximale Aufwand für Operationen zum und eines Schlüssels proportional zur Höhe des Baums und damit ebenfalls logarithmisch in der Zahl der Schlüssel; der mittlere Aufwand ist sogar konstant, wenn das Positionieren auf das Zielelement nicht mitgerechnet wird. Viele Operationen, insbesondere die Navigationsoperationen, sind direkt von den binären Suchbäumen zu übernehmen. Bei den modifizierenden Operationen jedoch muss das AVL-Kriterium beobachtet werden, womit auf jeden Fall kleine Anpassungen verbunden sind, die bis zu Höhenkorrekturen durch sogenannte reichen können. Der AVL-Baum ist benannt nach den sowjetischen Mathematikern Georgi Maximowitsch Adelson-Velski und Jewgeni Michailowitsch Landis, die die Datenstruktur im Jahr 1962 vorstellten. Damit ist der AVL-Baum die älteste Datenstruktur für balancierte Bäume. (de)
- In computer science, an AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree. 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; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where 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, Georgy Adelson-Velsky and Evgenii Landis, who published it in their 1962 paper "An algorithm for the organization of information". AVL trees are often compared with red–black trees because both support the same set of operations and take time for the basic operations. For lookup-intensive applications, AVL trees are faster than red–black trees because they are more strictly balanced. Similar to red–black trees, AVL trees are height-balanced. Both are, in general, neither weight-balanced nor -balanced for any ; that is, sibling nodes can have hugely differing numbers of descendants. (en)
- Un árbol AVL es un tipo especial de árbol binario ideado por los matemáticos soviéticos Adelson-Velskii y Landis. Fue el primer árbol de búsqueda binario auto-balanceable que se ideó. (es)
- Dalam ilmu komputer, sebuah pohon AVL adalah sebuah pohon biner terurut yang dapat menyeimbangkan dirinya sendiri. Pada sebuah pohon AVL, tinggi dari dua anak sub pohon dari simpul apapun memiliki perbedaan paling besar 'satu'. Lookup, penyisipan (insertion), dan penghapusan (deletion) semuanya memerlukan O(logn) kali dalam kasus biasa dan kasus terburuk. Penambahan (additions) dan penghapusan membutuhkan pohon tersebut untuk menyeimbangkan kembali dirinya melalui rotasi pohon satu kali atau lebih.cara perurutannya yaitu sebelah kiri nilai yang paling rendah sedangkan sebelah kanan nilai paling besar dari nilai utamanya (root),left
* l
*
* s (in)
- AVL木（えーぶいえるき、AVL tree、Adelson-Velskii and Landis' tree）とは、コンピュータサイエンスにおいて、「どのノードの左右部分木の高さの差も1以下」という条件を満たす二分探索木のことである。 平衡二分探索木の1つで、木に対する操作によって条件を満たさないノードが発生しても、回転と呼ばれる操作を行うだけで木をAVL木に再構成でき、平衡を維持できる。 AVL木は最初に考案された平衡二分探索木であり、その名は1962年に論文を発表したソ連の2人の数学者、とに由来する。 (ja)
- 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 respectifs de ses deux inventeurs, respectivement (en) et (en), 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 respectives 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). (fr)
- 컴퓨터 과학에서 AVL 트리(발명자의 이름인 Adelson-Velsky and Landis에서 따온 이름)는 자가 균형 이진 탐색 트리이다. 스스로 균형을 잡는 데이터 구조 중 처음으로 발명되었다. AVL 트리에서, 두 자식 서브트리의 높이는 항상 최대 1만큼 차이난다. 만약 어떤 시점에서 높이 차이가 1보다 커지면 이 속성을 유지하기 위해서 스스로 균형을 잡는다. 검색, 삽입, 삭제는 모두 평균과 최악의 경우 O(log n)의 시간복잡도가 걸린다. 삽입과 삭제는 한 번 이상의 트리 회전을 통해 균형을 잡을 수 있다. (ko)
- Drzewo AVL, nazywane również drzewem dopuszczalnym – 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. Skrót AVL pochodzi od nazwisk rosyjskich matematyków: Adelsona-Velskiego oraz Landisa (właściwie: Gieorgij Adelson-Wielski i Jewgienij Łandis), którzy zaproponowali rozwiązanie problemu utrzymania dobrego drzewa wyszukiwań w roku 1962. Drzewo AVL pozostaje drzewem binarnych poszukiwań, co oznacza, że wierzchołki są uporządkowane w określony sposób. Zazwyczaj przyjmuje się, że 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, by 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 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 drzewami czerwono-czarnymi, ponieważ pozwalają na wykonanie tych samych operacji (dodawanie, usuwanie oraz wyszukiwanie elementów) przy 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ć unikatowy 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. (pl)
- L'albero AVL è, in informatica, un albero binario di ricerca bilanciato in cui il coefficiente di bilanciamento per ciascun nodo vale 1, 0 oppure -1 (nel caso di un albero AVL completo tutti i coefficienti di bilanciamento sono uguali a 0). Il nome AVL viene dai suoi inventori e , che pubblicarono il loro algoritmo nel saggio in russo "Odin algoritm organizacii informacii" ("un algoritmo di organizzazione dell'informazione") del 1962. Viene definito il coefficiente di bilanciamento come la differenza tra le altezze, rispettivamente, del sottoalbero sinistro e del sottoalbero destro di un nodo: dove è il nodo di cui si vuole calcolare il coefficiente e e sono rispettivamente il figlio sinistro e il figlio destro di . può quindi assumere solo valori interi sia positivi che negativi. La condizione per tenere l'albero bilanciato è semplice: per ogni nodo dell'albero, la differenza di altezza dei suoi 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 di una serie di inserzioni, questi sono O(1). 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. (it)
- Árvore AVL é uma árvore binária de busca balanceada, ou seja, uma árvore balanceada (árvore completa) são as árvores que minimizam o número de comparações efetuadas no pior caso para uma busca com chaves de probabilidades de ocorrências idênticas. Contudo, para garantir essa propriedade em aplicações dinâmicas, é preciso reconstruir a árvore para seu estado ideal a cada operação sobre seus nós (inclusão ou exclusão), para ser alcançado um custo de algoritmo com o tempo de pesquisa tendendo a . As operações de busca, inserção e remoção de elementos possuem complexidade (no qual é o número de elementos da árvore), que são aplicados a árvore de busca binária. O nome AVL vem de seus criadores soviéticos Adelson Velsky e Landis, e sua primeira referência encontra-se no documento "Algoritmos para organização da informação" de 1962 . Nessa estrutura de dados cada elemento é chamado de nó. Cada nó armazena uma chave e dois ponteiros, uma para a subárvore esquerda e outro para a subárvore direita. No presente artigo serão apresentados: os conceitos básicos, incluindo uma proposta de estrutura; apresentação das operações busca, inserção e remoção, todas com complexidade . (pt)
- АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1. АВЛ — аббревиатура, образованная первыми буквами создателей (советских учёных) Адельсон-Вельского Георгия Максимовича и Ландиса Евгения Михайловича. (ru)
- Ett 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. (sv)
- AVL树（Adelson-Velsky and Landis Tree）是计算机科学中最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的時間複雜度都是。增加和删除元素的操作则可能需要藉由一次或多次树旋转，以实现树的重新平衡。AVL树得名于它的发明者G. M. Adelson-Velsky和，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。 节点的平衡因子是它的左子树的高度减去它的右子树的高度（有時相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。 (zh)
- АВЛ-дерево — збалансоване по висоті двійкове дерево пошуку: для кожної його вершини висота її двох піддерев відрізняється не більше ніж на 1. АВЛ — абревіатура, утворена першими літерами творців (радянських учених) Адельсон-Вельського Георгія Максимовича і Ландіса Євгена Михайловича. (uk)
|
| rdfs:comment
|
- AVL strom je datová struktura pro uchovávání údajů a jejich vyhledávání. Pracuje v logaritmicky omezeném čase. Jedná se o samovyvažující se binární vyhledávací strom. Jméno stromu pochází z iniciál jeho objevitelů. a popsali tuto strukturu v roce 1962 v článku An algorithm for the organization of information. Dokázali, že AVL-strom bude maximálně o 45 % vyšší než dokonale vyvážený strom, složený ze stejných vrcholů. Pokud v(n) je výška AVL-stromu s n uzly, potom platí log(n+1) ≤ v(n) ≤ 1.4404 log(n+2) − 0.328. (cs)
- Un árbol AVL es un tipo especial de árbol binario ideado por los matemáticos soviéticos Adelson-Velskii y Landis. Fue el primer árbol de búsqueda binario auto-balanceable que se ideó. (es)
- AVL木（えーぶいえるき、AVL tree、Adelson-Velskii and Landis' tree）とは、コンピュータサイエンスにおいて、「どのノードの左右部分木の高さの差も1以下」という条件を満たす二分探索木のことである。 平衡二分探索木の1つで、木に対する操作によって条件を満たさないノードが発生しても、回転と呼ばれる操作を行うだけで木をAVL木に再構成でき、平衡を維持できる。 AVL木は最初に考案された平衡二分探索木であり、その名は1962年に論文を発表したソ連の2人の数学者、とに由来する。 (ja)
- 컴퓨터 과학에서 AVL 트리(발명자의 이름인 Adelson-Velsky and Landis에서 따온 이름)는 자가 균형 이진 탐색 트리이다. 스스로 균형을 잡는 데이터 구조 중 처음으로 발명되었다. AVL 트리에서, 두 자식 서브트리의 높이는 항상 최대 1만큼 차이난다. 만약 어떤 시점에서 높이 차이가 1보다 커지면 이 속성을 유지하기 위해서 스스로 균형을 잡는다. 검색, 삽입, 삭제는 모두 평균과 최악의 경우 O(log n)의 시간복잡도가 걸린다. 삽입과 삭제는 한 번 이상의 트리 회전을 통해 균형을 잡을 수 있다. (ko)
- АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1. АВЛ — аббревиатура, образованная первыми буквами создателей (советских учёных) Адельсон-Вельского Георгия Максимовича и Ландиса Евгения Михайловича. (ru)
- Ett 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. (sv)
- AVL树（Adelson-Velsky and Landis Tree）是计算机科学中最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的時間複雜度都是。增加和删除元素的操作则可能需要藉由一次或多次树旋转，以实现树的重新平衡。AVL树得名于它的发明者G. M. Adelson-Velsky和，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。 节点的平衡因子是它的左子树的高度减去它的右子树的高度（有時相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。 (zh)
- АВЛ-дерево — збалансоване по висоті двійкове дерево пошуку: для кожної його вершини висота її двох піддерев відрізняється не більше ніж на 1. АВЛ — абревіатура, утворена першими літерами творців (радянських учених) Адельсон-Вельського Георгія Максимовича і Ландіса Євгена Михайловича. (uk)
- في علم الحاسوب، شجرة إي في إل (بالإنجليزية: AVL Trees) هي ، وهي أول بنية بيانات تم اختراعها.في شجرة AVL، ارتفاع الأشجار الجزئية لأية عقدة تختلف بواحد على الأكثر. البحث، الإدخال، والحذف يتطلبون زمن (O(log n في كل من الحالات المتوسطة والأسوء، حيث أن n هو عدد العقد في شجرة قبل العملية. الإدخال والحذف قد يستلزم إعادة توازن الشجرة عن طريق واحد أو أكثر. شجرة AVL سميت نسبة لمخترعَيها السوفيتيين، غيورغي ماكسيموفيتش أدلسن-فالسكي (Adelson-Velskii) (Landis). الذين نشراها في مقالهما سنة 1962 «خوارزمية لتنظيم المعلومات». (ar)
- In computer science, an AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree. 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; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where 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. (en)
- Der AVL-Baum ist eine Datenstruktur in der Informatik. Es handelt sich dabei um einen binären Suchbaum mit der zusätzlichen Eigenschaft, dass sich an jedem Knoten die Höhe der beiden Teilbäume um höchstens eins unterscheidet. Diese Eigenschaft lässt seine Höhe nur logarithmisch mit der Zahl der Schlüssel wachsen und macht ihn zu einem balancierten binären Suchbaum. Die maximale (und mittlere) Anzahl der Schritte (Vergleiche), die nötig sind, um An- oder Abwesenheit eines Schlüssels festzustellen, hängt direkt mit der Höhe zusammen. Ferner ist der maximale Aufwand für Operationen zum und eines Schlüssels proportional zur Höhe des Baums und damit ebenfalls logarithmisch in der Zahl der Schlüssel; der mittlere Aufwand ist sogar konstant, wenn das Positionieren auf das Zielelement nicht mitg (de)
- 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 respectifs de ses deux inventeurs, respectivement (en) et (en), qui l'ont publié en 1962 sous le titre An Algorithm for the Organization of Information. (fr)
- Dalam ilmu komputer, sebuah pohon AVL adalah sebuah pohon biner terurut yang dapat menyeimbangkan dirinya sendiri. Pada sebuah pohon AVL, tinggi dari dua anak sub pohon dari simpul apapun memiliki perbedaan paling besar 'satu'. Lookup, penyisipan (insertion), dan penghapusan (deletion) semuanya memerlukan O(logn) kali dalam kasus biasa dan kasus terburuk. Penambahan (additions) dan penghapusan membutuhkan pohon tersebut untuk menyeimbangkan kembali dirinya melalui rotasi pohon satu kali atau lebih.cara perurutannya yaitu sebelah kiri nilai yang paling rendah sedangkan sebelah kanan nilai paling besar dari nilai utamanya (root),left (in)
- L'albero AVL è, in informatica, un albero binario di ricerca bilanciato in cui il coefficiente di bilanciamento per ciascun nodo vale 1, 0 oppure -1 (nel caso di un albero AVL completo tutti i coefficienti di bilanciamento sono uguali a 0). Il nome AVL viene dai suoi inventori e , che pubblicarono il loro algoritmo nel saggio in russo "Odin algoritm organizacii informacii" ("un algoritmo di organizzazione dell'informazione") del 1962. Viene definito il coefficiente di bilanciamento come la differenza tra le altezze, rispettivamente, del sottoalbero sinistro e del sottoalbero destro di un nodo: (it)
- Drzewo AVL, nazywane również drzewem dopuszczalnym – 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. Skrót AVL pochodzi od nazwisk rosyjskich matematyków: Adelsona-Velskiego oraz Landisa (właściwie: Gieorgij Adelson-Wielski i Jewgienij Łandis), którzy zaproponowali rozwiązanie problemu utrzymania dobrego drzewa wyszukiwań w roku 1962. (pl)
- Árvore AVL é uma árvore binária de busca balanceada, ou seja, uma árvore balanceada (árvore completa) são as árvores que minimizam o número de comparações efetuadas no pior caso para uma busca com chaves de probabilidades de ocorrências idênticas. Contudo, para garantir essa propriedade em aplicações dinâmicas, é preciso reconstruir a árvore para seu estado ideal a cada operação sobre seus nós (inclusão ou exclusão), para ser alcançado um custo de algoritmo com o tempo de pesquisa tendendo a . (pt)
|