Árvores binárias de busca — Estrutura de Dados I

A árvore binária em que a posição de cada chave é dada pela ordem. Busca, inserção e remoção em tempo proporcional à altura, com o TAD Arvore guardando pares chave-valor.

Na tabela de símbolos, a lista encadeada insere sem deslocar nada, mas só consegue buscar percorrendo tudo; o vetor ordenado faz busca binária, mas paga caro para manter a ordem. Uma árvore binária de busca (ABB) junta as duas coisas: é uma estrutura encadeada, em que inserir é só pendurar um nó novo, e as chaves ficam organizadas de forma que a busca descarta uma parte inteira da árvore a cada comparação, como na busca binária.

Definição

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

Uma árvore binária de busca é uma árvore binária em que cada nó tem uma chave e, para todo nó :

todas as chaves da SAE de são menores que a chave de ;
todas as chaves da SAD de são maiores que a chave de .

Como a ABB vai implementar uma tabela de símbolos, as chaves são únicas: inserir uma chave que já existe apenas atualiza o valor associado a ela.

Árvore binária de busca com raiz 45; à esquerda 23, com os filhos 12 e 34, e 34 com os filhos 30 e 40; à direita 70, com os filhos 56 e 88; 56 tem o filho direito 61, e 88 tem o filho direito 95 — Uma árvore binária de busca, o exemplo desta página.

A propriedade vale para todas as chaves das subárvores, e não só para os filhos. Comparar cada nó apenas com os seus filhos não basta:

Árvore com raiz 45, filhos 23 e 70, e 23 com os filhos 12 e 50. Cada nó é maior que o filho esquerdo e menor que o direito, mas 50 está na SAE de 45 e é maior que 45, então a árvore não é de busca — Cada nó respeita os seus filhos, e mesmo assim a árvore não é uma ABB.

Observação 1

Alguns livros admitem chaves repetidas, com na SAE ou na SAD, e a inserção manda as chaves iguais sempre para o mesmo lado. Isso serve, por exemplo, para guardar um conjunto com repetições. Nesta página, as chaves são únicas, como em uma tabela de símbolos.

A ordem simétrica

O percurso em ordem simétrica (SAE, raiz, SAD) visita as chaves de uma ABB em ordem crescente. Mais do que isso, essa é uma caracterização das ABB.

Teorema 1

Uma árvore binária com chaves distintas é uma ABB se e somente se a sequência de chaves do seu percurso em ordem simétrica é estritamente crescente.

Demonstraçãotente antes de abrir

Por indução no número de nós. A árvore vazia e a árvore com um nó satisfazem as duas condições. Seja então uma árvore com raiz , SAE e SAD . A em-ordem dela é a em-ordem de , seguida de , seguida da em-ordem de .

() Se a árvore é uma ABB, e também são (a propriedade vale para todos os nós delas), e, pela hipótese de indução, as suas em-ordens são crescentes. Todas as chaves de são menores que e todas as de são maiores; logo, a sequência inteira é crescente.

() Se a sequência inteira é crescente, os seus trechos também são: pela hipótese de indução, e são ABB. Além disso, toda chave de aparece antes de e toda chave de aparece depois, então são, respectivamente, menores e maiores que . A propriedade vale na raiz e em todos os nós de e : a árvore é uma ABB.

O teorema dá, de graça, um algoritmo para imprimir as chaves em ordem em e um algoritmo para verificar se uma árvore binária é ABB (o primeiro exercício da página).

O TAD Arvore

A ABB será um TAD, como as estruturas das páginas anteriores. O cliente enxerga apenas as operações de Arvore.h; o nó e os campos da árvore ficam escondidos em Arvore.c. Cada nó guarda um par chave-valor, como na tabela de símbolos, e a struct da árvore guarda o ponteiro para a raiz e a quantidade de nós.

/* Arvore.h */
#ifndef ARVORE_H
#define ARVORE_H

#include <stdbool.h>

/* TAD Árvore Binária de Busca: pares (chave, valor) com chaves únicas */
typedef int Chave;
typedef int Valor;
typedef struct arvore Arvore;

Arvore *criaArvore(void);
void liberaArvore(Arvore *arvore);

/* Se a chave já existe, troca o valor; senão, insere o par */
void insereArvore(Arvore *arvore, Chave chave, Valor valor);

/* Ponteiro para o valor associado à chave, ou NULL se ela não existe */
Valor *buscaArvore(const Arvore *arvore, Chave chave);

/* Remove o par com essa chave (se não existe, nada acontece) */
void removeArvore(Arvore *arvore, Chave chave);

int tamanhoArvore(const Arvore *arvore);
int alturaArvore(const Arvore *arvore);
bool arvoreVazia(const Arvore *arvore);

void imprimeEmOrdem(const Arvore *arvore);     /* pares em ordem de chave */
void imprimeArvore(const Arvore *arvore);      /* desenho deitado (só chaves) */

#endif

/* Em Arvore.c */
typedef struct no {
    Chave chave;
    Valor valor;
    struct no *esq;
    struct no *dir;
} No;

struct arvore {
    No *raiz;
    int tamanho;
};

As operações seguem um padrão: cada função pública chama uma função auxiliar recursiva, declarada como static (visível só dentro de Arvore.c), que recebe um No *. A função pública só faz a ponte entre a struct arvore e a raiz.

O valor só viaja junto

Nas figuras e no imprimeArvore, aparecem só as chaves, para não poluir o desenho. Mas cada nó guarda também o seu valor, e é só a chave que decide onde o nó fica. Nenhuma operação da árvore compara valores: eles apenas acompanham as chaves.

Busca

Para procurar uma chave, compara-se com a chave da raiz:

se for igual, achamos;
se for menor, ela só pode estar na SAE;
se for maior, ela só pode estar na SAD.

A cada passo, a busca desce um nível e descarta a outra subárvore inteira. Ela termina ao encontrar a chave ou ao chegar a NULL (a chave não está na árvore).

A árvore de exemplo com o caminho 45, 23, 34, 40 destacado: 40 é menor que 45, maior que 23, maior que 34 e igual a 40 — A busca pela chave 40 visita apenas quatro nós.

static No *buscaNo(No *r, Chave chave) {
    if (r == NULL || r->chave == chave)
        return r;
    if (chave < r->chave)
        return buscaNo(r->esq, chave);
    else
        return buscaNo(r->dir, chave);
}

Valor *buscaArvore(const Arvore *arvore, Chave chave) {
    No *p = buscaNo(arvore->raiz, chave);
    return p == NULL ? NULL : &p->valor;
}

A condição r == NULL || r->chave == chave trata os dois casos base de uma vez: em ambos, a resposta é o próprio r. Como na tabela de símbolos, buscaArvore devolve um ponteiro para o valor, ou NULL.

A recursão da busca é de cauda (a chamada recursiva é a última coisa que a função faz), e por isso ela vira um laço sem esforço:

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

Inserção

Uma chave nova entra exatamente onde a busca por ela terminaria sem sucesso: desce-se pela árvore comparando com cada nó e, ao chegar a NULL, pendura-se ali um nó novo. Todo nó inserido entra como folha, e o resto da árvore não muda.

A árvore de exemplo com o caminho 45, 23, 34, 40 destacado e o novo nó 38 pendurado como filho esquerdo de 40 — Inserir 38: a busca por 38 cai no filho esquerdo de 40, e o novo nó entra ali.

Na versão recursiva, a função devolve a raiz da subárvore depois da inserção. Quando a subárvore é vazia, essa raiz é o nó novo; nos outros casos, é a mesma de antes, e o retorno é atribuído de volta ao ponteiro do pai (r->esq = ...). É assim que o nó novo fica ligado à árvore.

/* Devolve a raiz da subárvore depois da inserção. *novo vira true se um
   nó foi criado (false se a chave já existia e só o valor mudou). */
static No *insereNo(No *r, Chave chave, Valor valor, bool *novo) {
    if (r == NULL) {
        *novo = true;
        return criaNo(chave, valor);
    }
    if (chave < r->chave)
        r->esq = insereNo(r->esq, chave, valor, novo);
    else if (chave > r->chave)
        r->dir = insereNo(r->dir, chave, valor, novo);
    else
        r->valor = valor;               /* chave já existe: atualiza */
    return r;
}

void insereArvore(Arvore *arvore, Chave chave, Valor valor) {
    bool novo = false;
    arvore->raiz = insereNo(arvore->raiz, chave, valor, &novo);
    if (novo)
        arvore->tamanho++;
}

O parâmetro novo existe por causa do campo tamanho: ele só deve aumentar quando um nó é de fato criado, e não quando a chave já existia.

Pergunta

Por que insereArvore faz arvore->raiz = insereNo(...), se na maioria das vezes a raiz não muda?

Ver respostaEsconder resposta

Porque na primeira inserção, com a árvore vazia, ela muda: de NULL para o nó novo. A mesma ideia vale em cada nível: atribuir o retorno a r->esq ou r->dir é o que liga o nó novo ao pai quando a subárvore era vazia. Nos outros casos, a atribuição grava o mesmo ponteiro que já estava lá, sem efeito. O Programa 1 dos exercícios mostra o que acontece quando o retorno é ignorado.

A inserção também pode ser feita sem recursão. A diferença é que, ao chegar a NULL, é preciso saber quem é o pai, que vai receber o nó novo:

No *insere(No *raiz, int chave, int valor) {
    No *pai = NULL, *atual = raiz;
    while (atual != NULL) {
        if (chave == atual->chave) {    /* chave já existe: atualiza */
            atual->valor = valor;
            return raiz;
        }
        pai = atual;
        atual = chave < atual->chave ? atual->esq : atual->dir;
    }
    No *novo = criaNo(chave, valor);
    if (pai == NULL)
        return novo;                    /* a árvore estava vazia */
    if (chave < pai->chave)
        pai->esq = novo;
    else
        pai->dir = novo;
    return raiz;
}

iterativo.cC

A ordem de inserção define a forma

As mesmas chaves, inseridas em ordens diferentes, produzem árvores diferentes. E a diferença pode ser enorme:

À esquerda, as chaves inseridas na ordem 40 20 60 10 30 50 70 formam uma árvore cheia de altura 2. À direita, as mesmas chaves inseridas em ordem crescente formam uma árvore degenerada de altura 6, em que cada nó só tem filho direito — As mesmas sete chaves, em duas ordens de inserção.

Inserir as chaves já ordenadas é o pior caso: cada chave nova é maior que todas as anteriores e vai sempre para a direita, e a árvore degenera em uma lista encadeada.

Remoção

Para remover uma chave, primeiro é preciso achá-la, descendo como na busca. Quando o nó com a chave é encontrado, há três casos.

Caso 1: é uma folha. Basta liberar o nó; o pai passa a apontar para NULL.

Caso 2: tem um único filho. O filho (com toda a sua subárvore) sobe para o lugar de . Isso preserva a ordem: a subárvore do filho estava inteira de um lado de e, portanto, do mesmo lado de todos os ancestrais de .

Caso 1: na subárvore com raiz 70, a folha 95 é removida e 88 fica sem filhos. Caso 2: o nó 56, que tem só o filho 61, é removido, e 61 sobe para o lugar dele como filho esquerdo de 70 — Remoção de uma folha e de um nó com um único filho.

Caso 3: tem dois filhos. Não dá para simplesmente subir um filho: o outro ficaria sem pai. A solução é trocar a chave de por outra que possa ocupar aquele lugar sem quebrar a ordem: o seu antecessor, a maior chave da SAE, que é a chave imediatamente anterior a na ordem crescente. O par chave-valor do antecessor é copiado para , e o nó antigo do antecessor é removido da SAE.

Remoção da raiz 45, que tem dois filhos. O antecessor 40, o nó mais à direita da SAE, tem a sua chave e o seu valor copiados para a raiz, e o nó antigo do 40 é removido da SAE. Depois da remoção, a raiz é 40 — Remover um nó com dois filhos: o antecessor toma o seu lugar.

O próximo resultado garante que essa troca funciona.

Lema 1

Seja um nó com dois filhos em uma ABB, e seja o nó obtido partindo do filho esquerdo de e descendo sempre para a direita enquanto possível. Então:

tem a maior chave da SAE de (o antecessor de );
não tem filho direito;
trocando a chave de pela de e removendo , a árvore continua sendo uma ABB.

Demonstraçãotente antes de abrir

(1) A cada passo para a direita, todas as chaves que ficam para trás (o nó atual e a sua SAE) são menores que as da SAD em que entramos. Quando não há mais filho direito, nenhuma chave da SAE de é maior que a de .

(2) Por construção, a descida para quando não tem filho direito.

(3) A chave de é maior que todas as outras chaves da SAE de (por 1) e menor que todas as da SAD de (porque está na SAE de ). Então, no lugar de , ela respeita a propriedade em relação às duas subárvores. Ela também respeita os ancestrais de : estava na subárvore de , do mesmo lado de cada ancestral que a chave de . Por fim, remover da SAE é um caso 1 ou 2 (por 2), que preserva a propriedade.

Por simetria, o sucessor (a menor chave da SAD) também serviria. Usar sempre o mesmo lado é uma escolha arbitrária.

/* Devolve a raiz da subárvore depois da remoção. *removeu vira true se
   a chave foi encontrada. */
static No *removeNo(No *r, Chave chave, bool *removeu) {
    if (r == NULL)
        return NULL;                    /* a chave não está na árvore */
    if (chave < r->chave) {
        r->esq = removeNo(r->esq, chave, removeu);
    } else if (chave > r->chave) {
        r->dir = removeNo(r->dir, chave, removeu);
    } else if (r->esq == NULL || r->dir == NULL) {
        /* casos 1 e 2: nenhum ou um filho; o filho (ou NULL) sobe */
        No *filho = r->esq != NULL ? r->esq : r->dir;
        free(r);
        *removeu = true;
        return filho;
    } else {
        /* caso 3: dois filhos; o antecessor (máximo da SAE) toma o lugar */
        No *ant = r->esq;
        while (ant->dir != NULL)
            ant = ant->dir;
        r->chave = ant->chave;          /* copia o par inteiro */
        r->valor = ant->valor;
        r->esq = removeNo(r->esq, ant->chave, removeu);
    }
    return r;
}

Os casos 1 e 2 são tratados juntos: se é uma folha, os dois filhos são NULL, e o "filho que sobe" é NULL. Repare também que o filho é guardado antes do free(r): depois dele, r->esq e r->dir não podem mais ser lidos.

Questão

Na árvore de exemplo, o nó 23 tem dois filhos (12 e 34). Com a remoção pelo antecessor, que chave ocupa o lugar do 23 depois de removeArvore(a, 23)?

O programa completo

O programa abaixo usa o TAD para inserir as onze chaves do exemplo, buscar, atualizar um valor e remover nós dos três casos, imprimindo a árvore depois de cada remoção. Repare no par (40, 999): na remoção da raiz, ele é copiado inteiro, chave e valor, para o lugar do 45.

TAD ArvoreC

Quanto custa?

Busca, inserção e remoção descem por um único caminho a partir da raiz: cada chamada recursiva desce um nível. Na remoção do caso 3, a descida até o antecessor e a remoção dele continuam no mesmo caminho, mais para baixo.

Proposição 1

Em uma ABB de altura , a busca, a inserção e a remoção custam .

Demonstraçãotente antes de abrir

Cada uma faz um trabalho constante por nó visitado, e os nós visitados estão em um caminho que desce da raiz, com no máximo um nó por nível: são no máximo nós. Na remoção com dois filhos, a busca pelo antecessor e a remoção dele seguem descendo a partir de , e o total continua sendo um caminho só.

Tudo depende, então, da altura. Pela página de árvores binárias, ela fica entre e . Com as chaves inseridas em ordem crescente, atingimos o pior caso, como na figura da seção anterior. E com as chaves em ordem aleatória?

Teorema 2(sem demonstração)

Se chaves distintas são inseridas em uma ABB vazia em uma ordem escolhida ao acaso (todas as ordens igualmente prováveis), a altura esperada da árvore é .

A demonstração está no livro do Cormen et al. (Teorema 12.4) e usa ferramentas de probabilidade que fogem do escopo desta disciplina. O programa abaixo mede a altura na prática: insere chaves em ordem aleatória (média de três ordens) e em ordem crescente.

altura.cC

Em ordem aleatória, a altura fica em torno de duas a três vezes : para cem mil chaves, por volta de 40 níveis, contra 99.999 da árvore degenerada. Mas "em ordem aleatória" é uma suposição forte: dados reais muitas vezes chegam ordenados ou quase ordenados (matrículas, datas, códigos sequenciais). As árvores AVL e as rubro-negras, das próximas páginas, eliminam o pior caso: elas se reequilibram a cada inserção e remoção e garantem altura para qualquer ordem.

Com isso, a tabela de custos da tabela de símbolos ganha uma linha:

Implementação	Buscar	Inserir	Remover	Listar em ordem de chave
Lista encadeada
Vetor não ordenado
Vetor ordenado
ABB

com : no melhor caso, a ABB é melhor que as duas outras em tudo; no pior, ela é uma lista.

Exercícios

Encontre e corrija o erro

Os programas usam a árvore de exemplo da página, com valor igual a dez vezes a chave.

Programa 1

insere.cC

Resposta

As chamadas recursivas ignoram o retorno: insere(r->esq, chave, valor) cria o nó novo e o devolve, mas ninguém liga esse nó ao pai. Só a raiz (que é atribuída no main) fica na árvore; os outros nós ficam perdidos na memória, e o AddressSanitizer acusa o vazamento. O retorno precisa ser guardado no ponteiro do pai:

if (chave < r->chave)
    r->esq = insere(r->esq, chave, valor);
else if (chave > r->chave)
    r->dir = insere(r->dir, chave, valor);

Programa 2

busca.cC

Resposta

A comparação está invertida: quando a chave procurada é maior que a do nó, a busca desce para a esquerda, onde só há chaves menores. Só a raiz é encontrada. O certo é if (chave < r->chave) para descer à esquerda.

Programa 3

remove.cC

Resposta

Nos casos de um filho, a função faz free(r) e só depois lê r->dir (ou r->esq) para devolver o filho: a leitura acontece em memória liberada (heap-use-after-free). O filho precisa ser guardado antes:

No *filho = r->esq != NULL ? r->esq : r->dir;
free(r);
return filho;

Programa 4

remove2.cC

Resposta

No caso de dois filhos, a função copia para o nó só a chave do antecessor (30), mas não o valor. O nó passa a ter a chave 30 com o valor 340, que era da chave 34, removida. A árvore continua correta como ABB (as chaves estão em ordem), e por isso o erro passa despercebido em testes que olham só as chaves. Falta r->valor = ant->valor;.

Programa 5

cadastro.cC

Resposta

A listagem sai fora de ordem (1920 aparece depois de 2031), e a Carla não é encontrada nem pela matrícula nova nem pela antiga. O busca devolve um ponteiro para o aluno dentro do nó, e o main usa esse ponteiro para trocar a matrícula, que é a chave. O nó continua no lugar que a chave antiga determinou (à direita de 2031), e a árvore deixa de ser de busca. A busca por 1920 desce para a esquerda de 2031 e não o encontra. A busca por 2104 vai para a direita, chega ao nó, mas a chave dele agora é 1920.

Alterar a chave exige tirar o aluno da árvore e inseri-lo de novo, para que ele vá para a posição certa. Com uma remoção como a desta página (que este programa não tem), seria assim:

Aluno corrigido = *busca(raiz, 2104);
raiz = removeNo(raiz, 2104);
corrigido.matricula = 1920;
raiz = insere(raiz, corrigido);

Para evitar o erro, o próprio TAD pode impedir a alteração: se a busca devolve const Aluno *, o aluno pode ser lido, mas a linha carla->matricula = 1920 não compila. É o que faz o exercício a seguir. Os campos que não são chave, como a nota, podem ser alterados por uma função do TAD (alteraNota).

Implemente

Cadastro de alunos. Até aqui, cada nó guardava um par de inteiros. Em aplicações reais, o nó costuma guardar um registro inteiro, e a chave é um dos seus campos. Implemente o TAD Cadastro, uma árvore de busca em que cada nó guarda um Aluno (matrícula, nome e nota), com a matrícula como chave. O nome é alocado pelo cadastro, com o tamanho certo. Algumas funções (criaCadastro, tamanhoCadastro e listaAlunos) já estão prontas, e CadastroInterno.h dá acesso ao nó. Faltam a inserção, a busca, a alteração da nota, a remoção e a liberação. Os testes conferem a ordem da árvore depois de cada operação e que toda a memória é liberada no fim.

O que muda quando o nó guarda um registro?

A estrutura da árvore é a mesma desta página. O que é novo é o nome, que está em uma área alocada à parte. Em que operações ele exige cuidado?

Ver dica 1Esconder dica 1

Na inserção, o cadastro guarda uma cópia do nome (malloc e strcpy), e não o ponteiro recebido: quem chamou pode reaproveitar o vetor do nome logo depois. A atribuição novo->aluno = *aluno copia os campos, mas o campo nome copiado é só o endereço.

Ver dica 2Esconder dica 2

Na remoção de um nó com dois filhos, o aluno do antecessor sobe para o nó removido. O nome do aluno removido precisa ser liberado, e o nome do antecessor passa a pertencer a este nó. Se a remoção recursiva do nó antigo do antecessor liberar o nome dele, o nó de cima fica com um nome já liberado. Uma saída simples: depois de copiar, faça ant->aluno.nome = NULL (e free(NULL) não faz nada).

Ver dica 3Esconder dica 3

Na liberação, cada nó libera o nome e depois o próprio nó.

Cadastro de alunos em uma árvore de buscaC

É árvore binária de busca? Dada uma árvore binária qualquer, verifique se ela é uma ABB (com chaves únicas), em . Os testes incluem árvores como a da segunda figura desta página, em que cada nó respeita os seus filhos, e árvores com as chaves INT_MIN e INT_MAX.

Como enxergar os ancestrais?

Uma função recursiva que recebe só o nó não sabe nada sobre os ancestrais dele. Que informação sobre eles bastaria?

Ver dica 1Esconder dica 1

Ao descer para a SAE de um nó com chave , todas as chaves lá embaixo precisam ser menores que ; ao descer para a SAD, maiores. Passe para a recursão o intervalo de chaves permitido.

Ver dica 2Esconder dica 2

Usar INT_MIN e INT_MAX como "sem limite" falha justamente quando a árvore tem essas chaves. Um ponteiro NULL para o limite resolve. Outra saída é o Teorema 1: percorrer em ordem simétrica e conferir que cada chave é maior que a anterior.

É árvore binária de busca?C

Mínimo, máximo, piso e teto. No TAD Arvore, implemente a menor e a maior chave e o piso (a maior chave menor ou igual a uma chave dada) e o teto (a menor chave maior ou igual), todos em . É o mesmo exercício das operações ordenadas da tabela de símbolos, agora em uma árvore: o arquivo ArvoreInterno.h dá acesso aos campos do nó. Os testes fazem centenas de milhares de consultas em uma árvore grande, e percorrer a árvore inteira em cada uma não termina a tempo.

Mínimo, máximo, piso e tetoC

Chaves em um intervalo. Grave, em ordem crescente, todas as chaves que estão em um intervalo , em , em que é o número de chaves gravadas. Um percurso em ordem simétrica completo resolve, mas visita a árvore inteira; os testes fazem 200 mil consultas de intervalos curtos.

Onde não vale a pena descer?

Se a chave de um nó é menor que , alguma chave da SAE dele pode estar no intervalo?

Ver dicaEsconder dica

Não: todas as chaves da SAE são menores que a do nó, e portanto menores que . Do mesmo jeito, se a chave do nó é maior que , a SAD pode ser ignorada. Faça o percurso em ordem simétrica, mas desça para cada lado só quando ele puder ter chaves no intervalo.

Chaves em um intervaloC

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. Capítulo 12.
R. Sedgewick e K. Wayne. Algorithms. 4ª ed. Addison-Wesley, 2011. Seção 3.2.
P. Feofiloff. Árvores binárias de busca. Projeto de Algoritmos, IME-USP.
VisuAlgo: árvores binárias de busca. Visualização interativa.