Projeto de Algoritmos  |  Linguagem C  |  Índice  |  English

Árvores binárias de busca

Assim como árvores binárias generalizam listas encadeadas, árvores binárias de busca (= binary search trees = BSTs) generalizam listas encadeadas crescentes.

Definição

Considere uma árvore binária cujos nós têm um campo chave de um tipo (como int, char, string, etc.) que admite comparação.  Neste capítulo, suporemos que as chaves são do tipo int. Suporemos também que os nós da árvore têm a seguinte estrutura:

typedef struct reg {
   int         chave;
   int         conteudo;
   struct reg *esq, *dir; 
} noh; // nó

Uma árvore binária deste tipo é de busca se cada nó p tem a seguinte propriedade:  ⚠ a chave de p é  (1) maior ou igual à chave de cada nó da subárvore esquerda de p  e  (2) menor ou igual à chave de cada nó da subárvore direita de p.  Em outras palavras, se p é um nó qualquer então

e->chave  ≤  p->chave  ≤  d->chave

para todo nó e na subárvore esquerda de p e todo nó d na subárvore direita de p.  Eis outra maneira, talvez mais clara, de descrever a propriedade que define árvores de busca:  a ordem e-r-d das chaves é crescente.

Exercícios 1

Busca

Considere o seguinte problema:  Dada uma árvore de busca r e um número k, encontrar um nó de r cuja chave seja k.  A seguinte função recursiva resolve o problema:

// Recebe uma árvore de busca r e
// um número k. Devolve um nó
// cuja chave é k; se tal nó não existe,
// devolve NULL.

noh *
busca (arvore r, int k) {
    if (r == NULL || r->chave == k)
       return r;
    if (r->chave > k)
       return busca (r->esq, k);
    else
       return busca (r->dir, k);
}

(O tipo-de-dados arvore é igual a um ponteiro-para-nó.)  Eis uma versão iterativa da mesma função:

    while (r != NULL && r->chave != k) {
       if (r->chave > k) 
          r = r->esq;
       else
          r = r->dir;
    }
    return r;

A animação abaixo (copiada de https://plus.google.com/+Geekboots/posts/FU9LXq9tKpE) mostra a execução de busca (r, 27):

No pior caso, a busca consome tempo proporcional à altura da árvore.  Se a árvore for balanceada, o consumo será proporcional a  log n ,  sendo n o número de nós.  Esse tempo é da mesma ordem que a busca binária num vetor ordenado.

Exercícios 2

Inserção

Considere o problema de inserir um novo nó, com chave k, em uma árvore de busca. É claro que a árvore resultante deve também ser de busca.  O novo nó será uma folha da árvore resultante:

    noh *novo;
    novo = malloc (sizeof (noh));
    novo->chave = k;
    novo->esq = novo->dir = NULL;

É claro que a função que resolve o problema deve devolver a raiz da nova árvore. A função é particularmente simples e elegante quando escrita em estilo recursivo:

// A função recebe uma árvore de busca r
// e uma folha avulsa novo e insere a folha
// na árvore de modo que a árvore continue
// sendo de busca. A função devolve a raiz 
// da árvore resultante.

arvore 
insere (arvore r, noh *novo) {  
    if (r == NULL) return novo;
    if (r->chave > novo->chave) 
       r->esq = insere (r->esq, novo);
    else 
       r->dir = insere (r->dir, novo);
    return r;
}

A raiz da árvore resultante é a mesma da árvore original a menos que a árvore original seja vazia.

Exercícios 3

Remoção

Considere o problema de remover um nó de uma árvore de busca de tal forma que a árvore continue sendo de busca. Esse problema é mais complicado que o da busca e o da inserção.

Comecemos tratando das instâncias em que o nó a ser removido é a raiz da árvore. Se a raiz não tem um dos filhos, basta que o outro filho assuma o papel de raiz. Senão, faça com que o nó anterior à raiz na ordem e-r-d assuma o papel de raiz.

A figura ilustra o antes-e-depois da remoção do nó r. O nó anterior a r na ordem e-r-d é q  (os nós estão numerados em ordem e-r-d).  O nó q é colocado no lugar de r, os filhos de r passam a ser filhos de q, e f passa a ser filho (direito) de p.

// Recebe uma árvore de busca não vazia r.
// Remove a raiz da árvore e rearranja a
// árvore de modo que ela continue sendo
// de busca. Devolve o endereço da nova
// raiz.

arvore 
removeraiz (arvore r) {  
    noh *p, *q;
    if (r->esq == NULL) {
       q = r->dir;
       free (r);
       return q;
    }
    p = r; q = r->esq;
    while (q->dir != NULL) {
       p = q; q = q->dir;
    }
    // q é nó anterior a r na ordem e-r-d
    // p é o pai de q
    if (p != r) {
       p->dir = q->esq;
       q->esq = r->esq;
    }
    q->dir = r->dir;
    free (r);
    return q;
}

Suponha agora que queremos remover um nó que não é a raiz da árvore. Para remover o filho esquerdo de um nó x faça

   x->esq = removeraiz (x->esq);

e para remover o filho direito de x faça

   x->dir = removeraiz (x->dir);

Exercícios 4

Desempenho dos algoritmos

Quanto tempo gastam os algoritmos de busca, inserção e remoção discutidos acima? É claro que esse tempo é limitado por algum múltiplo do número de nós, digamos n, da árvore (pois nenhum nó é visitado mais que 3 vezes). Mas esta é uma resposta muito grosseira. Eis uma resposta mais fina:  no pior caso, qualquer dos algoritmos acima

gasta uma quantidade de tempo proporcional à altura da árvore.

Conclusão: interessa trabalhar sempre com árvores balanceadas, ou seja, árvores que têm altura próxima a log n, isto é, árvores em que todas as folhas têm aproximadamente a mesma profundidade.

Infelizmente não é fácil fazer isso. A altura da árvore é sujeita a chuvas e trovoadas. É muito fácil construir um exemplo em que uma árvore começa com altura próxima de log n mas depois de algumas inserções azaradas fica com altura muito mais próxima de n−1 (claro que o valor de n muda ao longo desse processo).

Os algoritmos de inserção e remoção descritos acima não produzem árvores balanceadas. Se a função insere for repetidamente aplicada a uma árvore balanceada, o resultado pode ser uma árvore muito desbalanceada. Algo análogo pode acontecer depois de uma sequência de chamadas da função removeraiz.

Para enfrentar essa situação é preciso inventar algoritmos bem mais sofisticados e complexos de inserção e remoção; esses algoritmos fazem um rebalanceamento da árvore após cada inserção e cada remoção. Vou apenas citar dois termos técnicos pitorescos: há um pacote de algoritmos de inserção e remoção que produz árvores rubro-negras; há um outro pacote que produz árvores AVL.

Exercícios 5