Árvore Binária

Sendo um arranjo de nós hierárquicos, onde cada nó possui mais dois nós imediatamente abaixo, uma árvore binária é um conjunto finito de elementos que está vazio ou está divido em três subconjuntos. O primeiro subconjunto contém um único elemento, chamado raiz da árvore. Os outros dois subconjuntos são em si mesmas árvores binárias, chamadas subárvores esquerda e direita da árvore original. Uma subárvore esquerda ou direita pode estar vazia. Cada elemento de uma árvore binária é chamado nó da árvore.

Em termos de implementação, cada nó em um arvore contem três partes, o membro informação e dois ponteiros denominados ponteiro esquerdo e ponteiro direito. Usando uma estrutura com três membros, monta-se uma arvore binária apontando os nos para seus filhos. Se o nó não tiver filhos, utiliza o terminador nulo como uma sentinela para indicar o fim da ramificação.

Cada grupo de nós diretamente abaixo de um nó é chamado de filhos, enquanto que o nó acima é nomeado de pai, os nós podem ter irmãos, descendentes e ancestrais, como se pode concluir, irmãos são os nós de um mesmo pai, descendentes são os nós que se ramificam de um dado nó abaixo e ancestrais são todos os nós que ficam no caminho ente o nó e a raiz, o desempenho de uma arvore é associado em termos de altura, o numero de níveis em que os nós residem.

Figura 1 – representação típica de uma árvore binária

Árvore da figura 1 consiste em nove nós com A como sua raiz. Sua subárvore esquerda está enraizada em B e sua subárvore direita, em C. Isso aparece indicado pelas duas ramificações que saem de A: para B, no lado esquerdo e para C, no lado direito. Por exemplo, a subárvore esquerda, da árvore binária enraizada em C e a subárvore direita da árvore binária enraizada em E estão, ambas, vazias. As árvores binárias enraizadas em D, G, H e I têm subárvores direita e esquerda vazias.

Um nó sem filhos (como D, G, H ou I) é chamado folha, na árvore acima, A é um ancestral de G, e H é um descendente de C, mas E não é nem ancestral nem descendente de C. Dois nós são irmãos (como H e I) se forem filhos esquerdo e direito do mesmo pai.

Todo nó que não é folha numa árvore binária tiver subárvores esquerda e direita não vazia, a árvore será considerada uma árvore estritamente binária, a da Figura 1 não é (porque os nós C e E tem somente um filho), uma árvore estritamente binária com n folhas contém sempre 2n - 1 nós, pode ser observado duas árvores estritamente binária respectivamente na figura 2 e 3.

Dois outros termos também são usados para descrever uma arvore binária, o termo arvore binária completa em que todos os níveis têm o numero máximo de elementos e o termo arvore binária quase completa, que possui um nível incompleto, mas que, entretanto continua estritamente binária.

Figura 2 - Arvore binária quase completa, balanceada de nível 3

A terminologia de uma arvore é um caso clássico de metáfora confusa, árvores naturais crescem com suas raízes fincadas na terra e suas folhas no ar, os cientistas de computação retratam de forma invertida a estruturas de dados em árvore com a raiz no topo e as folhas no chão. O sentido da raiz para as folhas é "para baixo" e o sentido oposto é "para cima". Percorre-se uma árvore a partir das folhas na direção da raiz, diz-se que está "subindo" a árvore, e se partir da raiz para as folhas, você está "descendo" a árvore.

Graças a essa metáfora que acaba gerando relações aonde à altura de uma arvore está relacionada com o termo profundidade, no exemplo de árvore binária da Figura 1, o nó E está no nível 2 e o nó H, no nível 3. A profundidade de uma árvore binária significa o nível máximo de qualquer folha na árvore. Isso equivale ao tamanho do percurso mais distante da raiz até qualquer folha. Sendo assim, a profundidade da árvore da Figura 1 é 3. Uma árvore binária completa de profundidade d é a árvore estritamente binária em que todas as folhas estejam no nível d. A Figura 3 ilustra a árvore binária completa de profundidade 2.

Percorrer uma arvore binária implica em visitar cada nó em uma ordem especifica, pode-se comparar com algumas estruturas de dados encadeadas, tais como listas ligadas, pensando na travessia da arvore sempre em termos recorrentes, fica ainda mais simples de compreender, existem quatro formas de como percorrer uma arvore binária.

Figura 3 - Árvore binária completa e balanceada a ser percorrida.

Métodos de Travessia
Pré-ordem	Em uma travessia preordenada de uma subarvore, primeiro a percorre será sua raiz, então vai para a ramificação da esquerda e procede para a da direita, conforme se explora a subarvore da esquerda para a direita, irá repetir o processo usando o nó esquerdo ou direito como a raiz de uma nova subarvore, conhecido também como uma exploração por profundidade. Exemplo da fig.2: D, B, A, C, F, E e G.
Ordem	Numa travessia ordenada de uma subarvore, primeiro vai para a ramificação da esquerda, depois para a raiz e termina na direita, sempre repetindo o processo ao tratar como subarvores os nós da esquerda e da direita. Exemplo da fig.2: A, B, C, D, E, F e G.
Pós-ordem	A sequência de travessia pós-ordenada, inicia pela ramificação esquerda, seguida pela ramificação direita e termina na raiz, refaz o processo quando atinge um dos nós e passa a trata-lo como uma subarvore. Exemplo da fig.2: A, C, B, E, G, F e D.
Ordem de Nível	Neste tipo de travessia, começa a percorrer na raiz e visita cada nó que se encontra no nível a partir da esquerda para direita, para seguir nível abaixo e repetir o processo, se trata de uma exploração por amplitude. Exemplo da fig.2: D, B, F, A, C, E e G.

Balanceamento de uma arvore é o processo de manter a altura a menor possível para uma quantidade de nós, isto implica que em certificar de que um nível da arvore está completo antes de permitir que um nó seja inserido em outro nível, portanto uma arvore balanceada irá ter todos os nós folhas no mesmo nível (figura 3), ou todos os nós folhas nos últimos dois níveis, com o penúltimo nível lotado (figura 2).

Noções de Árvore

Um dos problemas mais pertinentes na computação é capacidade de localizar rapidamente um item armazenado, técnicas de pesquisa como a tabela de dispersão ou busca em elementos ordenados representam diferentes grupos de algoritmos que apresentam soluções para este problema.  A partir deste ponto será apresentando uma diferente técnica conhecida como árvore.

Na computação uma árvore consiste em elementos organizados dentro de um arranjo hierárquico, como exemplos para a organização de uma estrutura como a árvore tem-se um mapa genealógico, a tabela de um torneio, ou as raízes de uma planta.

Pensando como tipo de dados abstrato, uma árvore consiste em um conjunto finito de elementos, dividido em no mínimo dois subconjuntos, o primeiro subconjunto é a raiz da árvore que tem o valor, os demais subconjuntos são em si mesmos outras árvores, denominadas de subárvores. Podendo ter quantidades fixas de subárvores e serem representadas como elemento vazio para indicar o fim de sua expansão. Altura de uma árvore é igual ao numero de camadas da raiz até o subárvore mais distante.

Tratando como uma estrutura de dados, considere o encadeamento para árvore análogo ao do encadeamento para lista, com um grupo de nós, com cada nó tendo um valor e apontando para outros nós (descendentes), tem-se o nó do topo da hierarquia nomeado de raiz, os nós diretamente abaixo da raiz são os nós filhos, que por sua vez tem outros nós filhos. Com exceção do nó raiz, cada nó na hierarquia tem apenas um nó pai, o numero de nós filhos que um nó pai pode ter é chamado fator de ramificação, que determina a quão rápido uma árvore irá ramificar conforme forem adicionados outros nós. Consideramos um nó sem subárvores ligadas a ele como nó terminal.

A maioria das rotinas de árvores é recursiva, pelo fato da própria árvore ser uma estrutura de dado recorrente, aonde cada subárvore é uma árvore, embora árvores sejam simples de se visualizar, apresentam um grande grau de dificuldade para conceber soluções não recursivas.

Durante as próximas postagens, o foco será árvore binária, uma eficaz árvore com fator de ramificação de 2, ou seja, árvores contendo até 2 nós filhos, a árvore binária é bastante popular devido ao seu uso extenso em diversas aplicações e por servir de base para outros tipos de árvores.