Conceitos

Árvores como estrutura hierárquica. Definição recursiva, terminologia, propriedades com demonstração e formas de representar uma árvore qualquer.

Até aqui, todas as estruturas foram lineares: em vetores, listas, pilhas e filas, cada elemento tem no máximo um antecessor e um sucessor. Muitos dados, porém, são hierárquicos:

o sistema de arquivos, com pastas dentro de pastas;
o organograma de uma empresa;
uma árvore genealógica;
a estrutura de uma página HTML, com elementos dentro de elementos;
uma expressão aritmética, em que cada operador se aplica a subexpressões.

Para esses dados, a estrutura natural é a árvore. E as árvores servem também para algo menos óbvio: na tabela de símbolos, nem a lista nem o vetor ordenado conseguem buscar e inserir rápido. As árvores binárias de busca, que vêm adiante, conseguem. Esta página apresenta o vocabulário e as propriedades básicas que todas elas usam.

Definição

Definição 1(Árvore)

Uma árvore é um conjunto finito de nós tal que:

se o conjunto é vazio, a árvore é vazia;
senão, existe um nó especial, a raiz, e os demais nós formam conjuntos disjuntos , cada um deles também uma árvore, chamada subárvore da raiz.

A raiz é ligada por uma aresta à raiz de cada subárvore não vazia.

A raiz A ligada às raízes B, C e D de três subárvores T1, T2 e T3, desenhadas dentro de caixas tracejadas: T1 com B, E e F; T2 com C, G, J e K; T3 com D, H e I — A raiz A e as suas três subárvores.

A definição é recursiva: uma árvore é feita de árvores menores. Por isso, quase todo raciocínio sobre árvores (as demonstrações desta página) e quase todo algoritmo sobre árvores (as funções das próximas páginas) também é recursivo: resolve-se o problema para as subárvores e combina-se o resultado na raiz.

Terminologia

Definição 2(Pai, filho, folha e grau)

Se a raiz de uma árvore tem a raiz de uma subárvore ligada a ela, a primeira é o pai da segunda, e a segunda é filho da primeira.
Nós com o mesmo pai são irmãos.
Um nó sem filhos é uma folha (ou nó terminal); um nó com pelo menos um filho é um nó interno.
O grau de um nó é o número de filhos dele. Folhas têm grau 0.

Árvore com raiz A; A tem os filhos B, C e D; B tem E e F; C tem G; D tem H e I; G tem J e K. A está destacado como raiz, E, F, H, I, J e K como folhas e B, C, D e G como nós internos. Os níveis 0 a 3 estão marcados à esquerda, e a subárvore com raiz D está em uma caixa tracejada — A árvore de exemplo desta página.

Definição 3(Caminho, ancestral e descendente)

Um caminho é uma sequência de nós distintos em que cada par de nós consecutivos é ligado por uma aresta. O comprimento do caminho é o número de arestas, ; de cada nó para ele mesmo há um caminho de comprimento 0.

Se está no caminho da raiz até , então é ancestral de , e é descendente de .

Definição 4(Profundidade e altura)

A profundidade (ou nível) de um nó é o comprimento do caminho da raiz até ele. A raiz está no nível 0.

A altura de um nó é o comprimento do caminho mais longo dele até uma folha descendente. Toda folha tem altura 0. A altura da árvore é a altura da raiz; por convenção, a árvore vazia tem altura .

A mesma árvore com o caminho A, C, G, K destacado em vermelho e os nós G, J e K, descendentes de C, em verde. Ao lado: o caminho de A até K tem comprimento 3; os ancestrais de K são A, C e G; a profundidade de K é 3 e a altura de C é 2 — Caminho, ancestrais e descendentes.

A profundidade é medida de cima para baixo, a partir da raiz; a altura, de baixo para cima, a partir das folhas. Na árvore do exemplo, o nó C tem profundidade 1 e altura 2. Para a árvore inteira, as duas medidas coincidem, como mostra a Proposição 3.

Questão

Na árvore de exemplo, qual afirmação é falsa?

Propriedades

As demonstrações abaixo usam indução na estrutura da árvore: prova-se a propriedade para a árvore vazia (ou com um nó) e, supondo que ela vale para as subárvores, prova-se que vale para a árvore inteira. Como as subárvores têm menos nós que a árvore, isso é uma indução no número de nós.

Proposição 1

Uma árvore com nós tem exatamente arestas.

Demonstraçãotente antes de abrir

Por indução no número de nós. Se , a árvore é só a raiz, sem subárvores não vazias, e tem arestas.

Se , sejam as subárvores não vazias da raiz, com nós. Como elas são disjuntas e não contêm a raiz, , e cada . Pela hipótese de indução, tem arestas. As arestas da árvore são as das subárvores mais as que ligam a raiz a cada :

Outra forma de ver o mesmo fato: todo nó, exceto a raiz, tem exatamente um pai, e cada aresta liga um nó ao seu pai. As arestas correspondem, uma a uma, aos nós que não são a raiz.

Proposição 2

Para todo nó de uma árvore, existe exatamente um caminho da raiz até .

Demonstraçãotente antes de abrir

Por indução no número de nós.

Existência. Se é a raiz, o caminho de comprimento 0 serve. Senão, pertence a alguma subárvore , e, pela hipótese de indução, há um caminho em da raiz de até . Acrescentando a raiz da árvore no começo (ela é ligada à raiz de por uma aresta), obtemos um caminho da raiz até .

Unicidade. Se é a raiz, o único caminho é o de comprimento 0: um caminho mais longo teria que voltar à raiz, repetindo um nó. Se não é a raiz, ele pertence a exatamente uma subárvore (elas são disjuntas). Um caminho da raiz até deixa a raiz por uma aresta, que leva à raiz de alguma subárvore. As arestas só ligam nós da mesma subárvore ou a raiz às raízes das subárvores, e o caminho não volta à raiz, então ele precisa entrar diretamente em e ficar nela até . Esse trecho é um caminho em da raiz de até , que é único pela hipótese de indução. Portanto, o caminho inteiro é único.

Por isso, os ancestrais de um nó são bem definidos: são os nós do único caminho da raiz até ele. E a profundidade também é bem definida.

Uma árvore pode ser vista como um grafo: os nós são os vértices, e as ligações entre pai e filho são as arestas, sem direção.

Teorema 1

Vista como grafo, uma árvore não vazia é conexa (existe um caminho entre quaisquer dois nós) e acíclica (não tem ciclos).

Demonstraçãotente antes de abrir

Conexa. Sejam e dois nós. Pela Proposição 2, há um caminho da raiz até cada um deles. Juntando o caminho de até a raiz (o primeiro, percorrido ao contrário) com o da raiz até , obtemos uma sequência de nós consecutivos ligados por arestas. Se essa sequência repetir nós, basta cortar o trecho entre as duas ocorrências do nó repetido; o que sobra é um caminho de até .

Acíclica. Suponha que haja um ciclo, e seja o nó do ciclo de menor profundidade. Os dois vizinhos de no ciclo não podem ser o pai de , que é menos profundo; então são dois filhos, e , raízes de subárvores diferentes de . Retirando , o resto do ciclo é um caminho de até que não passa por . Mas, a partir de um nó da subárvore de , as únicas arestas levam ao seu pai ou aos seus filhos; sem passar por , nunca se sai da subárvore de . Como as subárvores são disjuntas, o caminho não chega a , uma contradição.

Corolário 1

Em uma árvore, existe exatamente um caminho entre quaisquer dois nós.

Demonstraçãotente antes de abrir

Pelo Teorema 1, existe pelo menos um. Se existissem dois caminhos diferentes de até , seja o primeiro nó a partir do qual eles se separam e o primeiro nó, depois de , em que eles voltam a se encontrar (existe, porque os dois terminam em ). Os dois trechos de até não têm nós em comum além de e , e juntos formam um ciclo, o que o Teorema 1 proíbe.

Observação 1

Repare na ordem dos argumentos: ser conexa garante que existe pelo menos um caminho; ser acíclica é o que garante que ele é único. Vale também a recíproca: todo grafo conexo e acíclico, com qualquer vértice escolhido como raiz, é uma árvore no sentido da Definição 1. É assim que árvores são definidas em Teoria dos Grafos.

Proposição 3

A altura de uma árvore não vazia é igual à maior profundidade de um nó. Além disso, para todo nó ,

é ã

Demonstraçãotente antes de abrir

Um caminho que parte da raiz e só desce termina em algum nó e tem comprimento igual à profundidade de (é o único caminho da raiz até ). O mais longo deles termina em um nó de profundidade máxima, que é necessariamente uma folha: se tivesse um filho, o filho seria mais profundo. Logo, a altura da raiz é a maior profundidade.

Para a fórmula: um caminho de até uma folha descendente, se não é folha, começa pela aresta de até algum filho e continua por um caminho de até uma folha. O mais longo deles tem, portanto, arestas para o melhor filho .

A fórmula recursiva da altura é exatamente o que o código das próximas páginas calcula. Com a convenção de que a árvore vazia tem altura , a folha deixa de ser um caso especial: em uma árvore binária.

Representando uma árvore qualquer

O número de filhos de cada nó (o grau) é o que mais distingue os tipos de árvore. Em uma árvore qualquer, ele não tem limite, e isso complica a representação: quantos ponteiros reservar em cada nó? Duas soluções comuns evitam a pergunta.

Vetor de pais

Se os nós são numerados de a , basta um vetor pai, em que pai[v] é o número do pai de e a raiz tem pai[raiz] = -1. Para a árvore de exemplo, numerando A, B, C, ... como 0, 1, 2, ...:

Nó	A	B	C	D	E	F	G	H	I	J	K
`v`	0	1	2	3	4	5	6	7	8	9	10
`pai[v]`	-1	0	0	0	1	1	2	3	3	6	6

A representação é compacta (um inteiro por nó) e torna fácil subir na árvore: a profundidade de é o número de passos até a raiz.

int profundidade(const int pai[], int v) {
    int p = 0;
    while (pai[v] != -1) {      /* sobe até a raiz */
        v = pai[v];
        p++;
    }
    return p;
}

Em compensação, descer é caro: para achar os filhos de um nó, é preciso percorrer o vetor inteiro. O primeiro exercício da página usa essa representação.

Primeiro filho, próximo irmão

A outra solução dá a cada nó exatamente dois ponteiros, qualquer que seja o grau: um para o primeiro filho e outro para o próximo irmão. Os filhos de um nó formam uma lista encadeada, que começa no primeiro filho e segue pelos irmãos.

typedef struct no {
    const char *nome;
    struct no *filho;       /* primeiro filho */
    struct no *irmao;       /* próximo irmão */
} No;

A árvore de exemplo na representação primeiro filho, próximo irmão: A aponta para B como primeiro filho; B aponta para o irmão C, que aponta para o irmão D; B aponta para E, que aponta para o irmão F; C aponta para G; G aponta para J, que aponta para K; D aponta para H, que aponta para I — Cada nó guarda só o primeiro filho e o próximo irmão.

Para percorrer os filhos de r, basta seguir a lista: for (No *f = r->filho; f != NULL; f = f->irmao). O programa abaixo monta uma pequena árvore de pastas e arquivos e a imprime em pré-ordem (cada nó antes dos seus filhos), com o recuo dado pela profundidade. A altura usa a fórmula da Proposição 3.

pastas.cC

Pergunta

Na representação primeiro filho, próximo irmão, cada nó tem exatamente dois ponteiros. Que estrutura ela lembra?

Ver respostaEsconder resposta

Uma árvore binária: cada nó tem dois ponteiros, e o desenho da figura acima, com os ponteiros filho para baixo e irmao para a direita, é uma árvore em que cada nó tem no máximo dois "filhos". Toda árvore pode, então, ser guardada como uma árvore binária. Esse é um dos motivos pelos quais as árvores binárias, assunto da próxima página, são tão importantes.

Exercícios

Implemente

Profundidades pelo vetor de pais. Dada uma árvore no formato de vetor de pais, calcule a profundidade de todos os nós e a altura da árvore em . Os nós podem estar numerados em qualquer ordem (o pai pode ter número maior que o filho). Chamar a função profundidade acima para cada nó funciona, mas custa : em uma árvore degenerada, , e os testes incluem árvores com dezenas de milhares de níveis.

Como evitar subir até a raiz para cada nó?

O que a profundidade de tem a ver com a profundidade do pai de ?

Ver dica 1Esconder dica 1

A profundidade de é a do pai mais 1. Se a profundidade do pai já foi calculada, não é preciso subir de novo.

Ver dica 2Esconder dica 2

Guarde as profundidades já calculadas no próprio vetor prof (com para "ainda não calculada"). Uma função recursiva que calcula a profundidade de , usando a do pai, calcula cada uma no máximo uma vez.

Profundidades pelo vetor de paisC

Referências

W. Celes, R. Cerqueira e J. L. Rangel. Introdução a Estruturas de Dados: com técnicas de programação em C. 2ª ed. Grupo GEN, 2016.
T. H. Cormen, C. E. Leiserson, R. L. Rivest e C. Stein. Algoritmos: teoria e prática. 3ª ed. Elsevier, 2012. Apêndice B.5 (árvores).
P. Feofiloff. Árvores binárias. Projeto de Algoritmos, IME-USP.

Nesta página