Estruturas de Dados Intermediário/Árvore

Árvore é uma estrutura de dados que herda as características das topologias em árvore. Conceptualmente diferente das listas encadeadas, em que os dados se encontram numa sequência, nas árvores os dados estão dispostos de forma hierárquica.

A árvore é composta por um elemento principal chamado raiz, que possui ligações para outros elementos, que são denominados de galhos ou filhos. Estes galhos levam a outros elementos que também possuem outros galhos. O elemento que não possui galhos é conhecido como folha ou nó terminal.

O número máximo de galhos em um elemento é chamado ordem da árvore. Uma árvore binária é aquela de ordem 2, i.e., em que cada elemento possui no máximo 2 galhos.

Uma das operações importantes consiste em percorrer cada elemento da árvore uma única vez. Esse percurso, tambem chamado de travessia da árvore, pode ser feito em pré-ordem (os filhos de um nó são processados após o nó) ou em pós-ordem (os filhos são processados antes do nó). Em árvores binárias é possível ainda fazer uma traversia em-ordem, em que se processa o filho à esquerda, o nó, e finalmente o filho à direita.

O algoritmo abaixo descreve uma travessia pré-ordem:

PercursoPreordem(nó): 
  Processa nó
  Para cada filho de nó (se houver)
     Executa recursivamente PrecursoPreordem(filho)      

Outra operação, utilizada nas árvores de pesquisa é a travessia da raiz até uma das folhas. Essa operação tem um custo computacional proporcional ao número de níveis da árvore. O pior caso é a travessia de todos os elementos até a folha de nível mais baixo. A árvore balanceada, em que todas as folhas possuem o mesmo nível (com exceção de uma delas, que pode estar um nível acima) apresenta o melhor pior caso possível, para um certo número de nós. O pior pior caso apresenta-se na árvore degenerada em que cada nó possui exatamente um filho, e a árvore tem o mesmo número de níveis que de nós, assemelhando-se a uma lista ligada.

Topologia em árvore

Diagrama conceptual de uma topologia em árvore. Cada número é um nó.

Um configuração em árvore ou topologia em árvore é uma caracterização física de um objecto (ou seus componentes), que, pela sua configuração, se assemelha a uma árvore, no sentido em que as suas ramificações tendem a convergir para uma raíz, ou uma origem (por exemplo, árvore genealógica).

Introduz-se, portanto, a noção de raíz e descendência.

Em informática é vulgarmente utilizada como topologia, ao lado de outras como topologia em anel ou topologia em estrela. Em programação são largamente utilizadas como estruturas de dados para resolver problemas complexos, como indexação, por exemplo.

Nós de uma árvore

Por definição, uma árvore é constituída por nós. Um árvore vazia (sem nós) é também uma árvore.

Um nó de uma árvore é o elemento unitário da árvore. Deste nó podem derivar (descender) outros nós, designados de nós-filho, sendo o nó atual o nó-pai.

O grau de uma árvore é o número máximo de descendentes encontrado, para cada um dos nós. Se todos os nós derivam (no máximo) outros 2 nós, então estaremos perante uma árvore binária.