Árvores binárias

Uma outra forma de organizar dados em memoria principal é utilizando-se de árvores binárias. Elas são, assim como pilhas, filas, e listas, estruturas de dados que visam armazenar e manipular informações, mas apresentam uma peculiaridade, são estruturas hierárquicas, isto é, para cada nó que contém um certo dado, há uma relação de ordem entre o sucessor e o antecessor.

Para tornar claro esta ideia de hierarquia e ordem, veja o seguinte esboço:

 Terminologia:

-Nós: são os dados armazenados na árvore, que podem ser estruturas, chars, inteiros, etc.  

-Raiz da árvore: é o nó do topo da árvore, no exemplo o numero 10.

-Pai: são todos os nós acompanhados por outros dois nós, exemplo, 7 é pai de 2 e 8.

-Filhos:  são os nós descentendes de um nó pai ( antecessor ), exemplo, 7 e 15 são os filhos de 10.

-Folhas: são todos os nós do ultimo nível da arvore, os mais externos.

Na definição de árvore binária os elementos à esquerda da raiz, que contem o numero 10, devem ser menores que ela, e os elementos dos nodos a direita devem ser maiores. Observe que esta definição é recursiva e para a confecção de códigos que manipulam os dados e implementam uma árvore binária há a possibilidade de serem escritos de modo recursivo. Lembre-se que qualquer código recursivo têm seu correspondente iterativo, que é mais eficiente mas perde em legibilidade.

A complexidade de busca das árvores binárias é muito menor que nas listas ligadas, haja vista a disposição dos elementos e no modo binário como a busca se dá, se menor vai para esquerda, se maior vai para direita, até encontrar o elemento procurado. No entanto se a árvore se degenera, isto é, se a mesma é construída com elementos sucessivos, o efeito é o mesmo que construir uma lista ligada, culminando na mesma complexidade O(n), para busca e inserção. A árvore do desenho acima é dita completa, pois todos os níveis da arvore possui dois filhos para cada pai, sendo a complexidade de busca para tal arranjo na ordem de O(lg n), a melhor possível.

Nos próximos posts vou explicar como construir uma árvore binária, as codificações de inserção, remoção e busca em termos de orientação a objeto, usando C++.