mirror of
https://github.com/trekhleb/javascript-algorithms.git
synced 2025-12-08 19:06:00 +00:00
51 lines
2.1 KiB
Markdown
51 lines
2.1 KiB
Markdown
# Árvore AVL (AVL Tree)
|
|
|
|
Na ciência da computação, uma **árvore AVL** (em homenagem aos
|
|
inventores Adelson-Velsky e Landis) é uma árvore de pesquisa
|
|
binária auto balanceada. Foi a primeira estrutura de dados a
|
|
ser inventada.
|
|
Em uma árvore AVL, as alturas de duas sub-árvores filhas
|
|
de qualquer nó diferem no máximo em um; se a qualquer momento
|
|
diferirem por em mais de um, um rebalanceamento é feito para
|
|
restaurar esta propriedade.
|
|
Pesquisa, inserção e exclusão possuem tempo `O(log n)` tanto na
|
|
média quanto nos piores casos, onde `n` é o número de nós na
|
|
árvore antes da operação. Inserções e exclusões podem exigir
|
|
que a árvore seja reequilibrada por uma ou mais rotações.
|
|
|
|
|
|
Animação mostrando a inserção de vários elementos em uma árvore AVL.
|
|
Inclui as rotações de esquerda, direita, esquerda-direita e direita-esquerda.
|
|
|
|
|
|
|
|
Árvore AVL com fatores de equilíbrio (verde)
|
|
|
|
|
|
|
|
### Rotações de Árvores AVL
|
|
|
|
**Rotação Esquerda-Esquerda**
|
|
|
|
|
|
|
|
**Rotação direita-direita**
|
|
|
|
|
|
|
|
**Rotação Esquerda-Direita**
|
|
|
|
|
|
|
|
**Rotação Direita-Esquerda**
|
|
|
|
|
|
|
|
## Referências
|
|
|
|
* [Wikipedia](https://en.wikipedia.org/wiki/AVL_tree)
|
|
* [Tutorials Point](https://www.tutorialspoint.com/data_structures_algorithms/avl_tree_algorithm.htm)
|
|
* [BTech](http://btechsmartclass.com/data_structures/avl-trees.html)
|
|
* [AVL Tree Insertion on YouTube](https://www.youtube.com/watch?v=rbg7Qf8GkQ4&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8&index=12&)
|
|
* [AVL Tree Interactive Visualisations](https://www.cs.usfca.edu/~galles/visualization/AVLtree.html)
|