Árvore de Busca Binária

                Uma árvore de busca binária nada mais é do que uma arvore binária organizada especificamente para procuras, a busca de um nó dentro arvore se inicia pela raiz da arvore e desce de nível a nível até encontrar o nó desejado, utilizando a seguinte escolha, encontrou um nó maior que o desejado segue o ponteiro esquerdo, encontrou nó menor que o desejado segue o ponteiro direito, caso a procura alcance uma folha antes de encontrar um equivalente, o mesmo não existe na árvore.

                A eficiência de uma busca binária em árvores é excelente, uma vez que o pior caso, basta procurar a informação em apenas uma ramificação, ao invés de percorrer cada um de todos os dados, se uma arvore tem N nós distribuídos aleatoriamente, deverá ter uma altura media de lg N de nós. Por exemplo, se inserir em uma arvore os números 7, 3, 9, 2, 6,  11, 1, 5, 4 e 10, teremos como resultado a árvore da figura 1 com três níveis e razoavelmente bem balanceada. Se iniciar uma busca pelo numero 6, começa seguindo pelo ponteiro esquerdo na raiz 7, seguido do ponteiro direito na subárvore de árvore de valor 3 e já terá encontrado o equivalente.

Figura 1

               

                Pode ser melhorado? Certamente, a árvore da figura 1 precisa apenas de dois níveis de altura,lembre que uma árvore balanceada consiste em manter a mesma com a menor altura possível para um dado numero de nós, com o balanceamento correto na árvore, acaba eliminando o surgimento de uma ramificação demasiadamente longa que precise ser percorrida.

Entretanto  o formato desta árvore binária depende de em qual ordem o conjunto de itens foi carregado, os exemplos de árvores vistos anteriormente não possuem nenhum mecanismo interno que impeça o desbalanceamento entre subárvores.

Para melhor compreender a importância do balanceamento de uma arvore de busca binária, considere o pior caso ocorre quando toda a informação de entrada se encontra ordenada, na figura 2 temos o exemplo do que acontece na arvore quando recebe os números em ordem crescente, com cada elemento sendo sempre inserido a direita, que resulta em uma arvore desbalanceada a tal ponto que se assemelha a uma lista encadeada.

Figura 2

Em situações como esta, altura da arvore não é lg N e sim N, devido a péssima eficiência do pior caso que acaba tornando inaceitável o uso da árvore, de imediato duas soluções para o problema ocorrem, primeira alternativa aonde garante-se uma ordem aleatória de dados como no exemplo da figura 1 resultando num balanceamento ou a segunda opção em que todos os dados são analisados antes de adiciona-los.

Caso se conheça de antemão os itens que serão carregados, é possível construída uma arvore binária completa ou quase completa, mas como é de praxe na programação pratica, a ordem pela qual os nós são adicionados e excluídos não pode ser antecipada, o que irá requerer uma abordagem mais proativa utilizando algoritmos que forçam a arvore a se balancear sempre que executa uma ação de adição ou exclusão.

Nas próximas postagens veremos mais sobre o assunto através das analises das árvores AVL, Splay e Rubro-negra.