arvores balanceadas

ÁRVORES BALANCEADAS
Como já foi visto, um aspecto fundamental do estudo de árvores é o custo de acesso a uma chave desejada. Com intuito de minimizar esse custo, foram desenvolvidas as árvores binárias de busca e de partilha ótimas.
Porém, ambas se restringem a aplicações estáticas, isto é, após um certo número de inserções e remoções as árvores deixam de ser ótimas, e sua reorganização exige a reconstrução da estrutura.
Para estruturas em que as probabilidades de acesso são idênticas entre si, existem alternativas para manter o custo de acesso na mesma ordem de grandeza de uma árvore ótima, ou seja, O(log n), mesmo após inserções e remoções.
Para alcançar essa finalidade, a estrutura deve ser atualizada periodicamente, de forma a se moldar aos novos dados. O custo dessas alterações, contudo, se mantém em O(log n). Uma estrutura que opera com essas características é denominada balanceada.
O CONCEITO DE BALANCEAMENTO
Conforme já foi observado, as árvores completas são aquelas que minimizam o número de comparações efetuadas no pior caso para uma busca com chaves com probabilidades de ocorrência idênticas.
Porém, manter uma árvore completa exigiria aplicar um algoritmo que tornasse a árvore novamente completa, tão logo tal

característica fosse perdida. A dificuldade reside em como efetuar essa operação de forma eficiente, pois no pior caso é, pelo menos,
O(n).
Para aplicações que requeiram estruturas dinâmicas, uma alternativa consiste em utilizar um determinado tipo de árvore binária cujo pior caso de busca não seja necessariamente 1+log2n passos, mas algo também O(log n).
A idéia é exigir que a altura dessa árvore seja da ordem de grandeza a de uma completa, isto é, O(log n), porém com uma estrutura menos rígida do que a de uma árvore completa, tornando mais fácil o seu rebalanceamento.
ÁRVORES AVL
Uma árvore T é denominada AVL quando, para qualquer nó de T, as alturas de suas duas subárvores, esquerda e direita, diferem em módulo de até uma unidade.