Metraipolis › archive › dc_9752c36073b6
AVL tree — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/AVL_tree
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-07T01:21:05.513Z
- SHA-256 of the archived text
bb37d00c21af54df3287330623d685225f698be33e96e7d15cfdcfbd07c355c4- Stable URL of this page
https://metraipolis.com/documento/dc_9752c36073b6
How to cite
AVL tree — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/AVL_tree (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_9752c36073b6 (Metraipolis archive dc_9752c36073b6, sha256 bb37d00c21af54df3287330623d685225f698be33e96e7d15cfdcfbd07c355c4)
BibTeX
@misc{dc9752c36073b6,
title = {AVL tree — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/AVL_tree},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_9752c36073b6; sha256 bb37d00c21af54df3287330623d685225f698be33e96e7d15cfdcfbd07c355c4},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/AVL_tree. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In computer science, an AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by not more than 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 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, Georgy Adelson-Velsky and Evgenii Landis, who published it in their 1962 paper "An algorithm for the organization of information". It was the first self-balancing binary search tree data structure to be invented. AVL trees are often compared with red–black trees because both support the same set of operations and take O(logn) 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 μ≤12; that is, sibling nodes can have hugely differing numbers of descendants. Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in inglese, in ordine alfabetico). Fonte: Wikipedia in inglese, voce «AVL tree» — https://en.wikipedia.org/wiki/AVL_tree Wikidata Q300159: «albero binario di ricerca bilanciato» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q300159 Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/AVL_tree?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 1384121402, consultata il 2026-11-07T01:16:57.474Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 18d02cdc405af09b9f5d7acb70834095c268bad0f5929e0b609afd7619bb504b