Please enable JavaScript.
Coggle requires JavaScript to display documents.
AVL Trees - Coggle Diagram
AVL Trees
Tipo de árvore binária de busca (BST) que é
auto-balanceada
FB(nó) = altura(subárvore esquerda) - altura(subárvore direita)
No balanceamento, Para cada nó, a diferença de altura entre a subárvore esquerda e a subárvore direita (fator de balanceamento) é no máximo 1
Operações
Inserção
Inserir um novo nó como em uma BST normal.
Ajustar fatores de balanceamento
Realizar rotações para balancear a árvore, se necessário
Remoção
Remover o nó como em uma BST normal
Ajustar fatores de balanceamento
Realizar rotações para balancear a árvore, se necessário
Busca
Operação igual à BST padrão
Rotações
Simples
Rotação à Direita:
Corrige o desbalanceamento à esquerda
Rotação à Esquerda:
Corrige o desbalanceamento à direita
Duplas
Rotação à Esquerda-Direita:
Corrige o desbalanceamento à esquerda-direita
Rotação à Direita-Esquerda:
Corrige o desbalanceamento à direita-esquerda
Vantagens:
busca eficiente e auto-balanceamento
Graças ao balanceamento, as operações têm garantia de tempo logarítmico