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.