Árvores binárias — Estrutura de Dados I

Árvores em que cada nó tem no máximo dois filhos. Tipos, limites para a altura com demonstração, representação em C, percursos e operações recursivas.

Uma árvore binária é uma árvore em que cada nó tem no máximo dois filhos, e cada filho tem um lado: esquerdo ou direito. Elas aparecem em toda parte:

em expressões aritméticas, em que cada operador binário tem um operando à esquerda e outro à direita;
em processos de decisão, em que cada pergunta de sim ou não leva a um de dois caminhos;
na compressão de dados (o código de Huffman é uma árvore binária);
e, principalmente, nas árvores binárias de busca, que implementam a tabela de símbolos de forma eficiente e são o assunto das próximas páginas.

Definição

Definição 1(Árvore binária)

Uma árvore binária é:

vazia; ou
formada por um nó, a raiz, e por duas árvores binárias disjuntas: a subárvore esquerda (SAE) e a subárvore direita (SAD).

A terminologia é a mesma da página anterior: pai, filho, folha, profundidade, altura. A novidade é que a posição dos filhos importa: uma raiz com um único filho à esquerda e uma raiz com um único filho à direita são árvores binárias diferentes, embora sejam a mesma árvore no sentido geral.

Duas árvores com os nós 1 e 2: na primeira, 2 é filho esquerdo de 1; na segunda, 2 é filho direito de 1. Entre elas, o sinal de diferente — Em uma árvore binária, o lado do filho faz parte da estrutura.

Tipos de árvore binária

Definição 2(Tipos de árvore binária)

Uma árvore binária é:

estritamente binária se todo nó tem 0 ou 2 filhos (nenhum nó tem filho único);
completa se todos os níveis, exceto possivelmente o último, estão cheios, e os nós do último nível estão o mais à esquerda possível;
cheia (ou perfeita) se todo nó interno tem 2 filhos e todas as folhas estão no mesmo nível;
balanceada se, em todo nó, as alturas da SAE e da SAD diferem de no máximo 1;
degenerada se todo nó interno tem exatamente um filho.

Cinco árvores: uma estritamente binária, em que cada nó tem 0 ou 2 filhos; uma completa, com o último nível preenchido da esquerda para a direita; uma cheia, com todos os níveis cheios; uma balanceada, em que as alturas das subárvores de cada nó diferem de no máximo 1; e uma degenerada, em que cada nó interno tem um único filho — Os tipos de árvore binária.

Toda árvore cheia é, ao mesmo tempo, completa e estritamente binária. Já uma árvore degenerada é, na prática, uma lista encadeada: há um único nó por nível.

Cuidado com os nomes em inglês

A terminologia varia entre os livros, e a tradução engana. Em inglês, a nossa árvore estritamente binária costuma se chamar full binary tree, e a nossa árvore cheia se chama perfect binary tree. Ao consultar um material em inglês, confira a definição antes de usar um resultado.

Quanto pode medir a altura?

A altura é a medida mais importante de uma árvore binária: como veremos, buscar, inserir e remover em uma árvore de busca custa tempo proporcional a ela. Para um mesmo número de nós, ela pode variar muito.

Lema 1

Uma árvore binária tem no máximo nós no nível .

Demonstraçãotente antes de abrir

Por indução em . No nível 0 só existe a raiz: . Se o nível tem no máximo nós, cada um deles tem no máximo 2 filhos, e todo nó do nível é filho de um nó do nível . Logo, o nível tem no máximo nós.

Teorema 1

Uma árvore binária de altura tem no máximo nós, com igualdade se e somente se ela é cheia.

Demonstraçãotente antes de abrir

Os níveis vão de 0 a . Pelo Lema 1,

A igualdade vale se e somente se cada nível tem exatamente nós, isto é, se todos os níveis estão cheios. Nesse caso, todo nó fora do nível tem 2 filhos e todas as folhas estão no nível : a árvore é cheia. Reciprocamente, em uma árvore cheia de altura , cada nível dobra o anterior até o nível , onde estão todas as folhas, e a soma acima vale com igualdade.

Corolário 1

Uma árvore binária com nós tem altura .

Demonstraçãotente antes de abrir

Pelo Teorema 1, . Tomando o logaritmo, , e como é inteiro, .

Proposição 1

Uma árvore binária com nós tem altura , com igualdade se e somente se ela é degenerada.

Demonstraçãotente antes de abrir

Cada um dos níveis tem pelo menos um nó (o caminho da raiz até a folha mais profunda passa por todos eles). Então . A igualdade vale se e somente se cada nível tem exatamente um nó, isto é, se todo nó interno tem um único filho.

As duas pontas são atingidas. Uma árvore completa tem a menor altura possível:

Proposição 2

Uma árvore binária completa com nós tem altura exatamente .

Demonstraçãotente antes de abrir

Seja a altura. Os níveis de 0 a estão cheios e somam nós, e o nível tem pelo menos um nó; logo . Pelo Teorema 1, . Então , ou seja, , e .

A diferença entre os dois extremos é enorme:

	altura mínima,	altura máxima,
	9	999
	19	999.999
	29	999.999.999

Árvores balanceadas também têm altura , mesmo sem serem completas. A demonstração desse fato fica para a página das árvores AVL, que são justamente árvores de busca que se mantêm balanceadas.

O próximo resultado relaciona o número de folhas com o número de nós que têm dois filhos.

Teorema 2

Em uma árvore binária não vazia, sejam , e os números de nós com 0, 1 e 2 filhos. Então .

Demonstraçãotente antes de abrir

Contamos as arestas de dois jeitos. Cada aresta liga um nó ao seu pai, e todo nó exceto a raiz tem pai; com nós, há arestas (é a Proposição 1 da página anterior). Por outro lado, cada aresta sai de um pai para um filho, e os nós contribuem com 0, 1 ou 2 arestas cada: há arestas. Então

Corolário 2

Uma árvore estritamente binária com folhas tem nós internos e nós no total. Em particular, o número de nós é ímpar.

Demonstraçãotente antes de abrir

Em uma árvore estritamente binária, : os nós internos são os nós com dois filhos, e pelo Teorema 2 há deles. O total é .

Representação em C

Cada nó guarda a informação (uma chave inteira) e dois ponteiros, para a raiz da SAE e para a raiz da SAD. A árvore vazia é representada por NULL, e uma árvore inteira é acessada por um ponteiro para a sua raiz.

typedef struct no {
    int chave;
    struct no *esq;     /* subárvore esquerda (SAE) */
    struct no *dir;     /* subárvore direita (SAD) */
} No;

No *criaNo(int chave) {
    No *novo = malloc(sizeof(No));
    novo->chave = chave;
    novo->esq = NULL;   /* todo nó novo é uma folha */
    novo->dir = NULL;
    return novo;
}

Por enquanto, sem TAD e sem valor

Nesta página, as funções recebem diretamente um No *, e o nó guarda só a chave. Sem uma regra que diga onde cada chave deve ficar, não há uma inserção natural, e a árvore é montada "à mão". Nas árvores binárias de busca, a árvore ganha um TAD com inserção, busca e remoção, e cada nó passa a guardar também um valor, como na tabela de símbolos.

Com criaNo, podemos montar a árvore abaixo, que será o exemplo do resto da página, nível por nível:

Árvore binária com raiz 1; 1 tem os filhos 2 (esquerda) e 3 (direita); 2 tem os filhos 4 e 5; 3 tem só o filho direito 6; 5 tem só o filho esquerdo 7. Os níveis 0 a 3 estão marcados à esquerda — A árvore binária de exemplo.

No *raiz = criaNo(1);                   /* nível 0 */
raiz->esq = criaNo(2);                  /* nível 1 */
raiz->dir = criaNo(3);
raiz->esq->esq = criaNo(4);             /* nível 2 */
raiz->esq->dir = criaNo(5);
raiz->dir->dir = criaNo(6);
raiz->esq->dir->esq = criaNo(7);        /* nível 3 */

Vendo a árvore: `imprimeArvore`

Para conferir o que o programa montou, todas as páginas sobre árvores usam a mesma função imprimeArvore, que desenha a árvore deitada no terminal: a raiz fica na primeira coluna, a SAD aparece acima dela e a SAE abaixo, e cada nível recua quatro espaços. Para ver a árvore "em pé", incline a cabeça para a esquerda.

static void imprimeDeitada(const No *r, int nivel) {
    if (r == NULL)
        return;
    imprimeDeitada(r->dir, nivel + 1);
    printf("%*s%d\n", 4 * nivel, "", r->chave);
    imprimeDeitada(r->esq, nivel + 1);
}

void imprimeArvore(const No *raiz) {
    imprimeDeitada(raiz, 0);
}

O %*s imprime uma string vazia em um campo de largura 4 * nivel, ou seja, 4 * nivel espaços.

constroi.cC

Os ponteiros `NULL`

Na árvore de exemplo, 7 nós usam 6 ponteiros para ligar pais e filhos. Dos ponteiros dos nós, sobram 8 com NULL.

A árvore de exemplo com os ponteiros nulos desenhados como pequenos quadrados riscados: dois em cada uma das folhas 4, 7 e 6, um no lugar do filho esquerdo de 3 e um no lugar do filho direito de 5, num total de 8 — Sete nós e oito ponteiros NULL.

Proposição 3

Uma árvore binária com nós tem exatamente ponteiros NULL (contando o ponteiro para a raiz, se a árvore for vazia).

Demonstraçãotente antes de abrir

Se , há um único ponteiro, o da raiz, e ele é NULL. Se , os nós têm ponteiros ao todo. Cada aresta corresponde a um ponteiro não nulo (o do pai para o filho), e há arestas. Sobram ponteiros NULL.

Em uma função recursiva que chega até os NULL, como as desta página, isso quer dizer que há chamadas com a árvore vazia, além das chamadas com nós. O Programa 3 dos exercícios tropeça justamente aí.

Percursos

Muitas operações precisam visitar todos os nós da árvore (para imprimir, somar, contar, liberar...). Não há uma ordem natural para isso, mas três ordens recursivas são clássicas. Elas diferem apenas no momento em que a raiz é visitada:

pré-ordem: visita a raiz, percorre a SAE, percorre a SAD;
em-ordem (ou ordem simétrica): percorre a SAE, visita a raiz, percorre a SAD;
pós-ordem: percorre a SAE, percorre a SAD, visita a raiz.

Uma forma de enxergar as três ao mesmo tempo é dar a volta na árvore pelo lado de fora, começando à esquerda da raiz. Passamos três vezes por cada nó: à esquerda dele, embaixo e à direita. A pré-ordem anota o nó na primeira passagem, a em-ordem na segunda e a pós-ordem na terceira.

A árvore de exemplo contornada por uma linha tracejada que começa à esquerda da raiz e dá a volta por fora. Cada nó tem três marcas: uma vermelha à esquerda, uma azul embaixo e uma verde à direita. A pré-ordem lê as marcas vermelhas: 1 2 4 5 7 3 6; a em-ordem, as azuis: 4 2 7 5 1 3 6; a pós-ordem, as verdes: 4 7 5 2 6 3 1 — Pré-ordem, em-ordem e pós-ordem: a ordem em que o contorno passa por cada marca.

Há ainda um quarto percurso, em largura (ou por níveis): a raiz, depois os nós do nível 1, depois os do nível 2, e assim por diante, cada nível da esquerda para a direita. Ele não é recursivo: usa uma fila. A raiz entra na fila e, enquanto ela não estiver vazia, sai um nó, ele é visitado, e os seus filhos entram no fim da fila. É a mesma busca em largura do exercício do labirinto.

percursos.cC

Pergunta

Por que a fila de emLargura pode ser um vetor simples, sem dar a volta como a fila circular?

Ver respostaEsconder resposta

Cada nó entra na fila exatamente uma vez, então o total de inserções é , e um vetor de posições basta para todas elas. É a segunda tentativa da página de filas, que falhava porque as inserções não tinham limite. Aqui, elas têm.

Os quatro percursos custam : cada nó é visitado uma vez, com trabalho constante, e há chamadas com NULL (Proposição 3), também de custo constante.

Operações recursivas

A definição de árvore binária é recursiva, e as funções sobre ela seguem a mesma forma: o caso base é a árvore vazia, e o passo combina o resultado das duas subárvores na raiz.

int numeroNos(const No *r) {
    if (r == NULL)
        return 0;
    return numeroNos(r->esq) + numeroNos(r->dir) + 1;
}

/* A árvore vazia tem altura -1; uma folha, altura 0 */
int altura(const No *r) {
    if (r == NULL)
        return -1;
    int he = altura(r->esq);
    int hd = altura(r->dir);
    return (he > hd ? he : hd) + 1;
}

altura é a fórmula da página anterior: 1 mais a maior altura entre os filhos. Com a convenção de altura para a árvore vazia, uma folha não precisa de tratamento especial.

A busca de uma chave, sem nenhuma informação sobre onde ela pode estar, precisa olhar a raiz, depois a SAE inteira e, se não encontrar, a SAD inteira:

No *busca(No *r, int chave) {
    if (r == NULL)
        return NULL;
    if (r->chave == chave)
        return r;
    No *achou = busca(r->esq, chave);
    if (achou != NULL)
        return achou;
    return busca(r->dir, chave);
}

No pior caso (chave ausente), ela visita os nós. É aqui que entram as árvores binárias de busca: com uma regra para a posição das chaves, a busca passa a descer por um único caminho, em tempo proporcional à altura.

Por fim, para liberar a árvore, as subárvores precisam ser liberadas antes da raiz: depois de free(r), os campos r->esq e r->dir não podem mais ser lidos. Por isso, libera é uma pós-ordem.

void libera(No *r) {
    if (r != NULL) {
        libera(r->esq);
        libera(r->dir);
        free(r);
    }
}

operacoes.cC

Reconstruindo a árvore a partir dos percursos

Um percurso sozinho não determina a árvore: as duas árvores da primeira figura desta página (filho à esquerda ou à direita) têm a mesma pré-ordem, 1 2. Mas dois percursos podem determinar.

Teorema 3

Se as chaves são distintas, a pré-ordem e a em-ordem de uma árvore binária determinam a árvore.

Demonstraçãotente antes de abrir

Por indução no número de nós . Se , a árvore é vazia.

Se , a raiz é o primeiro nó da pré-ordem. A em-ordem lista a SAE inteira, depois a raiz, depois a SAD inteira; como as chaves são distintas, a raiz aparece em uma única posição dela, e os nós antes dessa posição são exatamente os da SAE, na em-ordem da SAE. Os nós depois dela são a SAD, na em-ordem da SAD.

A pré-ordem lista a raiz, depois a SAE inteira, depois a SAD inteira. Como já sabemos que a SAE tem nós, os nós que vêm depois da raiz na pré-ordem são a pré-ordem da SAE, e os restantes são a pré-ordem da SAD.

Temos então a pré-ordem e a em-ordem de cada subárvore, ambas com menos de nós. Pela hipótese de indução, elas determinam a SAE e a SAD, e com a raiz, a árvore inteira.

A pré-ordem 1 2 4 5 7 3 6 e a em-ordem 4 2 7 5 1 3 6. Na pré-ordem, o 1 (raiz) vem primeiro, seguido de 2 4 5 7 (SAE) e de 3 6 (SAD). Na em-ordem, 4 2 7 5 (SAE) vêm antes do 1, e 3 6 (SAD) depois — A raiz divide a em-ordem em SAE e SAD, e o tamanho da SAE divide a pré-ordem.

A demonstração é também um algoritmo recursivo para reconstruir a árvore. O mesmo vale com a pós-ordem no lugar da pré-ordem (a raiz é o último nó da pós-ordem).

Observação 1

A pré-ordem e a pós-ordem juntas não determinam a árvore: as duas árvores da primeira figura têm pré-ordem 1 2 e pós-ordem 2 1. A em-ordem é que distingue os lados: 2 1 em uma, 1 2 na outra.

Questão

Uma árvore binária com chaves distintas tem pré-ordem A B D E C F e em-ordem D B E A F C. Qual é a pós-ordem?

Exercícios

Encontre e corrija o erro

Os quatro programas usam a árvore de exemplo da página.

Programa 1

altura.cC

Resposta

A árvore vazia devolve altura 0, e não . Com isso, uma folha fica com altura , e todas as alturas saem uma unidade maiores: a árvore aparece com altura 4 em vez de 3. O caso base deve ser return -1;. (Alguns livros adotam a outra convenção, em que a folha tem altura 1; o erro é misturar as duas.)

Programa 2

libera.cC

Resposta

libera faz free(r) antes de liberar as subárvores, e em seguida lê r->esq e r->dir de um nó já liberado (heap-use-after-free). A liberação precisa ser em pós-ordem: primeiro as duas subárvores, depois o próprio nó.

libera(r->esq);
libera(r->dir);
free(r);

Programa 3

folhas.cC

Resposta

A função conta os ponteiros NULL, e não as folhas: cada árvore vazia devolve 1, e a soma dá , exatamente como prevê a Proposição 3. A árvore vazia tem 0 folhas, e uma folha é um nó com os dois filhos NULL:

if (r == NULL)
    return 0;
if (r->esq == NULL && r->dir == NULL)
    return 1;
return numeroFolhas(r->esq) + numeroFolhas(r->dir);

Programa 4

busca.cC

Resposta

O resultado de busca(r->esq, chave) é calculado e descartado: a função sempre devolve o resultado da SAD. Só são encontradas as chaves que estão no caminho mais à direita da árvore (1, 3 e 6). O resultado da SAE precisa ser guardado e devolvido quando não for NULL:

No *achou = busca(r->esq, chave);
if (achou != NULL)
    return achou;
return busca(r->dir, chave);

Implemente

Estritamente binária, completa, cheia? Implemente três funções que dizem se uma árvore binária é estritamente binária, completa e cheia, segundo a Definição 2. A árvore vazia é considerada as três coisas. Os testes incluem árvores com até 100 mil nós.

Ideias para a completa e a cheia

As definições falam de níveis, mas as funções recursivas enxergam um nó de cada vez. Como traduzir?

Ver dica 1Esconder dica 1

Para a cheia, use o Teorema 1: uma árvore de altura é cheia se e somente se tem exatamente nós.

Ver dica 2Esconder dica 2

Para a completa, numere os nós como se estivessem em um vetor, nível por nível: a raiz é 0, e os filhos do nó são e . A árvore é completa se e somente se todos os números são menores que (não há "buracos" antes do último nó). Outra saída é o percurso em largura: depois do primeiro filho ausente, não pode aparecer mais nenhum nó.

Estritamente binária, completa, cheiaC

Diâmetro. O diâmetro de uma árvore é o comprimento (em arestas) do maior caminho entre dois nós quaisquer. Na árvore de exemplo, ele é 5: o caminho 7, 5, 2, 1, 3, 6. Implemente uma função que calcula o diâmetro em . Os testes incluem árvores degeneradas com dezenas de milhares de nós.

Por onde passa o maior caminho?

Todo caminho tem um nó "mais alto" (o de menor profundidade). Se esse nó é a raiz, como é o caminho? E se não é?

Ver dica 1Esconder dica 1

Se o nó mais alto do caminho é a raiz, o caminho desce pela SAE e pela SAD, e o mais longo deles tem arestas, em que e são as alturas das subárvores (vale também quando uma delas é vazia, com altura ). Senão, o caminho está inteiro dentro de uma das subárvores.

Ver dica 2Esconder dica 2

Chamar altura em cada nó custa em uma árvore degenerada. Calcule a altura e o diâmetro na mesma recursão: uma função auxiliar pode devolver a altura e atualizar o maior caminho visto até agora por um ponteiro.

Diâmetro da árvoreC

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.
P. Feofiloff. Árvores binárias. Projeto de Algoritmos, IME-USP.
Binary tree. Wikipedia.