Representação simples de uma árvore. O nodo A, a raiz, tem como filhos diretos: B, C, E e filhos indiretos: D, F e G. B, C e E são irmãos, assim como D e F.
São estruturas eficientes e simples em relação ao tratamento computacional, diferentemente dos grafos.[3] Há inúmeros problemas no mundo real que podem ser modelados e resolvidos através das árvores. Estruturas de pastas de um sistema operacional, interfaces gráficas, bancos de dados e sites da Internet são exemplos de aplicações de árvores.[1]
Uma árvore é formada por um conjunto de elementos que armazenam informações chamados nodos ou nós.[2][4] Toda a árvore possui o elemento chamado raiz, que possui ligações para outros elementos denominados ramos ou filhos. Estes ramos podem estar ligados a outros elementos que também podem possuir outros ramos. O elemento que não possui ramos é conhecido como nó folha, nó terminal ou nó externo.[2]
Uma terminologia muito utilizada nas estruturas de árvores tem origem das árvores genealógicas. O relacionamento entre nodos é descrito com os termos "pai" (ou "mãe") para os antecessores diretos de um nodo, "filhos" (ou "filhas") para os descendentes diretos e "irmãos" (ou "irmãs") para todos os nodos com mesmo pai.[1][2]
Definições básicas
Definição formal de árvore
Formalmente, definimos uma árvore como um conjunto finito de zero ou mais nodos tal que[3]:
se o número de nodos = , temos uma árvore vazia, ou
se o número de nodos >
existe um nó especialmente denominado raiz de
os nós restantes formam conjuntos disjuntos , cada um desses conjuntos é uma árvore em si, chamada subárvore da raiz de , ou simplesmente subárvore.
O número máximo de filhos em um nodo é chamado ordem da árvore. Uma árvore binária é aquela de ordem 2, i.e., em que cada elemento possui no máximo 2 filhos.
Representação
Diferentes representações de uma árvore: a) hierárquica, b) diagrama de barras, c) diagrama de inclusão, d) aninhamento e e) numeração por níveis
Há diversas formas de representação de uma árvore: hierárquica, diagrama de inclusão, diagrama de barras, numeração por níveis, por aninhamento.
A hierárquica é parecida com um organograma de uma empresa, linhas unem dois nodos e indicam o relacionamento lógico entre eles. Tradicionalmente desenha-se a raiz na parte superior e todos os nodos subordinados na parte inferior, mas o contrário também é possível.[4] Na figura acima, o item (a) é um exemplo desta representação.
Diagrama de inclusão, um círculo representa cada nodo e seus nodos descendentes são inseridos dentro do círculo de seus pais. Também conhecida como diagrama de Venn, é muito utilizada na representação de conjuntos.[3] O item (c) da figura ao lado mostra a árvore do item (a) usando diagrama de inclusão.
Em um diagrama de barras, linhas são usadas para mostrar a hierarquia dos nodos. A raiz possui a linha de maior tamanho e os nodos irmãos possuem linhas de tamanhos iguais. Método bastante utilizado na criação de índices de livros.[3] É similar à indentação usada em linguagens de programação.[2] O item (b) da imagem ao lado indica como seria a árvore do item (a) usando essa representação.
Usando numeração por níveis o nodo raiz recebe o número um e todos os nodos seguintes recebem uma numeração sequencial, sempre antecedidos pela numeração de seus nodos superiores.[3] Item (e) da figura à direita representa a árvore (a) com representação por níveis.
Na representação por aninhamento, também conhecida por "representação por parênteses aninhados", a sucessão de parênteses reproduz as relações entre os nodos, aninhando um nodo filho ao seu pai.[2] Como exemplo temos o item (d) da imagem ao lado representando a árvore (a).
Algoritmos
Uma das operações importantes consiste em percorrer cada elemento da árvore uma única vez. Esse percurso, também 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 travessia 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 PercursoPreordem(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. Árvores balanceadas apresentam o melhor pior caso possível, para um certo número de nós. O 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.
