Pesquisa sobre o problema da ABB

Árvores (binárias) são muito utilizadas para se representar uma grande conjunto de dados onde se deseja encontrar um elemento de acordo com a sua chave.</br> Definição: Árvore Binária de Busca (Niklaus Wirth): Em uma árvore de busca é possível encontrar-se qualquer chave existente descendo-se a árvore sempre à esquerda toda vez que a chave procurada for menor do que a chave do nodo visitado e sempre à direita toda vez que for maior.

A escolha da direção de busca só depende da chave que se procura e da chave que o nodo atual possui. A busca de um elemento em uma árvore balanceada com n elementos toma tempo médio < log(n), tendo a busca então O(log n). </br> Graças à estrutura de árvore a busca poderá ser feita com apenas log(n) comparações de elementos. </br></br> A altura da Árvore de Busca Binária depende da sequência de inserção das chaves.</br> Considere, por exemplo, o que acontece se uma sequência ordenada de chaves é inserida.</br>Seria possível gerar uma árvore balanceada com essa mesma sequência, se ela fosse conhecida a priori.</br> A busca pode ser considerada eficiente se a árvore estiver razoavelmente balanceada. </br> A partir podemos identificar o problema de deterioração da busca na árvore, por exemplo: Quando inserimos utilizando a inserção simples, dependendo da distribuição de dados, um lado da arvore, poderá ficar muito grande em relação ao outro a partir do nó raiz gerando um desequilíbrio entre os lados, resultando na ineficiência de manter um arvore binaria de busca sempre balanceada sob a presença constante de inserções e deleções. </br> Foi pensando nisso que os soviéticos Adelson Velsky e Landis criaram a árvore AVL que nada mais é do que uma arvore binaria com opções de balanceamento, porém nem sempre podem ficar totalmente balanceadas, além disso, suas operações de inserção, deleção e balanceamento são razoavelmente rápidas.

Pesquisa Realizada na disciplina de Estrutura de Dados II