Arvore binaria | Algoritmos II: MergeSort, QuickSort, Busca Binária e Análise de Algoritmo

Olá Silvio,

árvores binárias são estruturas de dados que podem ser utilizadas para fazer uma busca binária, além de vários outros usos.

Uma árvore binária é uma estrutura teórica (chamamos de grafo, em matemática) que pode ser implementada de várias maneiras diferentes mas que tem basicamente a seguinte propriedade: cada um dos seus nós podem ter zero, um ou dois filhos que serão chamados de filho esquerdo e filho direito.

Além disso, para que seja utilizada em buscas binárias, é necessário que ela tenha uma propriedade de ordem: todos os nós à esquerda de um nó são menores que ele e todos os nós à direita de um nó são maiores que ele, como pode ser vista nessa imagem.

Podemos implementar árvores na prática de várias maneiras diferentes. Uma das mais simples é utilizar um vetor e o seguinte mapeamento (começando do índice 0): para cada nó n, seu filho esquerdo é dado pelo índice 2n+1 e seu filho direito é dado pelo índice 2n+2. Assim temos:

índice filho_esquerdo filho_direito
0            1                  2
1            3                  4
2            5                  6
3            7                  8
4            9                 10
5            11                12
6            13                14

Implementando a árvore da imagem utilizando um array teríamos:

Índice: 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 ...
Valor : 8  3 10  1  6 -1 14 -1 -1  4  7 -1 -1 13 -1 ...

E um algoritmo de busca binária recursivo poderia ser da seguinte forma:

busca_binaria(int valor_busca, int indice_atual)
    if( vetor[indice_atual] == -1) // Valor não está na árvore
        return -1;
    if( vetor[indice_atual] == valor_busca) // Encontrei o nó correto
        return indice_atual;
    if( vetor[indice_atual] > valor_busca) // Então devo procurar valores menores
        return busca_binaria(valor_busca, 2*(indice_atual) + 1)
    if( vetor[indice_atual] < valor_busca) // Então devo procurar valores maiores
        return busca_binaria(valor_busca, 2*(indice_atual) + 2)

Como o assunto é bem complexo, vou deixar você com alguns links para aprofundar os estudos. Os artigos da wikipedia de árvore binária e árvore binária de busca dão uma boa introdução e alguns códigos em java.

Para se aprofundar mais ainda, recomendo o excelente livro Algoritmos: Teoria e Prática de Charles Eric Leiserson, Ronald Rivest, Thomas H. Cormen e Clifford Stein

Bons estudos!