Árvores AVL

  • Árvore de busca binária balanceada
  • balanceada com respeito a altura das sub-arvores
  • altura maxima entre sub-arvores é de +- 1 (1 ≤ |hL — hR| ≥ -1)
  • Para inserir nessa árvore, usamos o mesmo algoritmo das árvores de busca binária, depois checamos o balanceamento, caso esteja desbalanceado, rotacionamos o primeiro nó que quebrou o balanceamento.
  • Para remover é quase a mesma coisa de inserir, só que dessa vez você aplica a rotação contrária.

exemplo arvore\u00a0avl

Rotações

LL (left-left)

image

image

LR (left-right)

image

image

RR (right-right)

image

image

RL (right-left)

image

image

Nota: LR é o mesmo que LL e depois RR