Please enable JavaScript.
Coggle requires JavaScript to display documents.
Árvores Autobalanceáveis - AVL - Coggle Diagram
Árvores Autobalanceáveis - AVL
AVL é uma árvore binária no qual as alturas das duas subárvores de todo o nó nunca difere em mais de 1.
A altura de uma árvore vazia é -1.
O balanceamento de um nó é definido com a altura de sua subárvore a esquera menos a altura de sua subárvore direita.
Uma AVL está desbalanceada quando qualquer um de seus nós tiver o fator de balanceamento diferente de: -1, 0 ou 1
Rotações = reorganizam a estrutura da árvore para restaurar o equilíbrio.
Uma AVL pode ficar "torta" (desequilibrada) após inserções ou remoções.
As operações de busca, inserção e remoção em uma árvore com n elementos podem ser efetuadas em O(logN). Isso acontece pois a altura da árvore é mantida balanceada.
O processo de rebalanceamento é conduzido utilizando 4 tipos de rotações: LL, RR, LR, RL
ROTAÇÕES
RR - Rotação simples à Esquerda:
Quando a árvore tem a subárvore a direita mais pesada.
O filho da direita vira nova raíz;
O filho da esquerda do filho da direita vira filho da direita do filho da esquerda; (caso o filho da direita tenha filho da esquerda)
A raíz original vira filho da esquerda a nova raíz.
LL - Rotação simples à Direita
Quando a árvore tem a subávore a esquerda mais pesada.
Filho da esquerda vira nova raíz;
O filho da direita do filho da esquerda vira filho da esquerda do filho da direita; (caso o filho da esquerda tenha filho da direita)
A raíz original vira filho da direita da nova raíz.
RL - Rotação dupla à Esquerda
Quando o nó desbalanceado tem o filho direito com subárvore à esquerda mais pesada.
Rotação à direita na subárvore da direita
Rotação à esquerda na árvore original.
LR - Rotação dupla à Direita
Quando o nó desbalanceado tem o filho esquerdo com subárvore à direita mais pesada.
Rotação à esquerda na subárvore da direita
Rotação à direita na árvore original.
Também são chamadas de árvore de pesquisa binária com autoequilíbrio.
Inserções: Igual BST + verificação de FB + Rotação (se necessário
Remoções: Igual BST + rebalanceamento no caminho de volta
Busca: Igual à BST (O(logn))