tysm

Árvore AVL

• Tipo de árvore balanceada pela altura.
• O nome AVL vem das iniciais de seus criadores: Adelson Velsky e Landis.

Balanceamento

• Está balanceada quando, para cada nó da árvore, a diferença entre as alturas das subárvores (direita e esquerda) não é maior que 1.

Fator de Balanceamento

• É dado por: altura da subárvore esquerda - altura da subárvore direita.
• Corolário: nós balanceados possuem fator de balanceamento = 1, 0 ou -1.
• Corolário: um nó com fator de balanceamento = 2 ou -2 requer um balanceamento.
• Corolário: Fator de balanceamento = 1 indica que a subárvore da esquerda é maior que a da direita.

tysm

Árvores

Definição

• Relação de hierarquia ou de composição entre nós.
• Conjunto finito de um ou mais nós, tais que:

a) sempre existe um nó raiz;
b) os demais nós formam subárvores;

• Cada nó de uma árvore é também raíz de uma subárvore.

Terminologia