Pesquisa sobre o problema da ABB

Árvores (binárias) são muito utilizadas para representar um grande conjunto de dados, quando se deseja encontrar um elemento de acordo com sua chave. Definição de Árvore Binária de Busca (Niklaus Wirth): em uma árvore de busca é possível encontrar qualquer chave existente descendo a árvore sempre à esquerda quando a chave procurada for menor do que a chave do nó visitado, e sempre à direita quando for maior.

A escolha da direção de busca depende apenas da chave procurada e da chave que o nó atual possui. A busca de um elemento em uma árvore balanceada com n elementos leva tempo médio de log(n), ou seja, O(log n). Graças à estrutura de árvore, a busca pode ser feita com apenas log(n) comparações.

A altura de uma Árvore de Busca Binária depende da sequência de inserção das chaves. Considere, por exemplo, o que acontece se uma sequência já ordenada de chaves é inserida — seria possível gerar uma árvore balanceada com essa mesma sequência, se ela fosse conhecida a priori. A busca é eficiente quando a árvore está razoavelmente balanceada, e daí surge o problema de deterioração: ao inserir elementos com inserção simples, dependendo da distribuição dos dados, um lado da árvore pode crescer muito mais que o outro a partir da raiz, gerando desequilíbrio e ineficiência ao manter a árvore balanceada sob inserções e remoções constantes.

Foi pensando nisso que os soviéticos Adelson-Velsky e Landis criaram a árvore AVL — uma árvore binária com regras de balanceamento que, embora nem sempre fique totalmente balanceada, mantém operações de inserção, remoção e balanceamento razoavelmente rápidas.

Pesquisa realizada na disciplina de Estrutura de Dados II.