Árvore binária

Olá pessoal! Todo bom computeiro deve conhecer as estruturas de dados básicas, como listas, pilhas, entre outras. Porém, algumas estruturas de dados que proporcionam uma maior eficiência na busca, inserção e remoção de dados são as árvores. Existem diversos tipos de árvores, como ávores B, B+, B*, Rubro-negras, entre outras. Árvores são estruturas eficientes para buscar, inserir e remover elementos. Hoje eu irei descrever brevemente sobre uma árvore simples, a árvore binária. Definindo de uma forma informal, uma árvore binária é composta por um nó raiz, nós intermediários e nós folhas, sendo que cada nó possui 0, 1 ou 2 filhos. A figura abaixo ilustra um exemplo de uma árvore binária.

Uma árvore binária pode ser implementada facilmente usando-se ponteiros. Porém, com isso é desperdiçado espaço de memória pois para cada nó mantêm-se dois ponteiros. Uma forma eficiente é a de representar árvores binárias em vetores. Dessa forma, a árvore binária acima ficaria da forma (A,B,C,D,E,F,G,-,-,-,-,H,I), caso armazenada em um vetor. As posições com o caracter '-' indicam posições vazias. Por que? Foi escolhida essa forma pois adotou-se o seguinte: para cada nó i, seus filhos estão em 2*i+1 e 2*i+2. Assim:

• A está na posição zero e seus filhos nas posições 1 e 2
• B está na posição um e seus filhos nas posições 3 e 4
• e assim por diante..

Mas por que não armazenar H e I nas posições 7 e 8 do vetor? Porque futuramente os filhos de D podem ser inseridos na árvore e também porque isso invalidaria o acesso eficiente aos filhos de um nó simplesmente calculando-se 2*i+1 e 2*i+2.
Descrevi brevemente o que é uma árvore binária, porém um maior aprofundamento pode ser feito no livro "Introdução a algoritmos", Cormen, ou até mesmo fazendo-se uma busca pelo google. Segue o link para a implementação descrita neste post, que eu fiz para um trabalho para a disciplina de ED da pós graduação. Qualquer bug, me informem! :-D.
Árvore binária implementada em vetor, na linguagem C.

[]'s a tds,
André Ferrizzi.