O que é uma Árvore AVL?

Cada nó em uma Árvore AVL rastreia sua própria altura: o número de arestas no caminho mais longo até uma folha. Uma folha tem altura 1, e uma subárvore vazia conta como altura 0. A partir da altura dos dois filhos de um nó, você pode calcular seu fator de equilíbrio: height(left) - height(right).

Um nó está equilibrado quando seu fator de equilíbrio é -1, 0 ou 1. A regra da Árvore AVL é simples: cada nó individual deve permanecer equilibrado, o tempo todo. Sempre que uma inserção ou exclusão empurra o fator de equilíbrio de um nó para 2 ou -2, a árvore realiza uma rotação: um rearranjo local de alguns ponteiros que restaura o equilíbrio em tempo constante sem quebrar a ordenação da árvore de busca.

Existem quatro casos de rotação (esquerda-esquerda, direita-direita, esquerda-direita, direita-esquerda), mas todos se resumem a dois blocos de construção: uma única rotação à esquerda e uma única rotação à direita. Você construirá ambas do zero nas próximas lições.