Introdução

Uma árvore binária de busca mantém os valores ordenados: a subárvore esquerda de cada nó contém valores menores e sua subárvore direita contém valores maiores. Essa ordenação torna a busca rápida, mas apenas se a árvore permanecer aproximadamente balanceada. Insira valores em ordem classificada em uma árvore binária de busca comum e ela se degradará em uma linha reta, transformando cada busca em uma varredura linear lenta.

Uma Árvore AVL corrige isso mantendo-se balanceada automaticamente. Após cada inserção ou exclusão, ela verifica se algum nó tornou-se desequilibrado e, se for o caso, realiza um pequeno ajuste local chamado rotação para restaurar o equilíbrio. Não importa como você a construa, uma Árvore AVL nunca se degrada em uma linha.

Neste curso, você construirá uma Árvore AVL do zero em sua linguagem preferida: nós com altura rastreada, verificações de equilíbrio, os quatro casos de rotação e inserção e exclusão com autobalanceamento. Em seguida, você usará sua classe finalizada para resolver um conjunto de desafios práticos.