Á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.

Sumário:

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; // 

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.

[Binary_search_tree.svg.png]

Exercícios 1

  1. ★ Suponha que  x->esq->chave  ≤  x->chave  para cada nó x dotado de filho esquerdo  e  x->chave  ≤  x->dir->chave  para cada nó x dotado de filho direito.  Essa árvore é de busca?
  2. Importante!  Escreva uma função que decida se uma dada árvore binária é ou não é de busca.

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):

[binary-search-tree-sorted-array-animation.gif]

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

  1. Escreva uma função min que encontre uma chave mínima em uma árvore de busca. Escreva uma função max que encontre uma chave máxima.
  2. Suponha que as chaves de nossa árvore de busca são distintas duas a duas. Escreva uma função que receba um inteiro k e devolva a primeira chave maior que k na ordem crescente das chaves.
  3. Escreva uma função que transforme um vetor crescente em uma árvore binária de busca que seja balanceada.
  4. Escreva uma função que transforme uma árvore de busca em um vetor crescente.
  5. Há uma relação muito íntima entre árvores de busca e o algoritmo de busca binária num vetor crescente. Qual é, exatamente, essa relação?

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

  1. ★ Escreva uma versão não recursiva de insere.
  2. Suponha que as chaves  50 30 70 20 40 60 80 15 25 35 45 36  são inseridas, nesta ordem, numa árvore de busca inicialmente vazia. Desenhe a árvore que resulta.
  3. Suponha que os nós de uma árvore binária de busca têm um campo pai.  Escreva um função que insira um novo nó na árvore. Faça duas versões: uma recursiva e uma iterativa.

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.

[remoção: antes (p.xxx)]   [depois (p.xxx)]

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

  1. Verifique a correção da função removeraiz.
  2. Suponha que as chaves  50 30 70 20 40 60 80 15 25 35 45 36  são inseridas, nesta ordem, numa árvore de busca inicialmente vazia. Desenhe a árvore que resulta. Em seguida remova o nó que contém 30.
  3. Escreva uma versão recursiva da função que remove um nó de uma árvore de busca.
  4. Suponha que os nós de uma árvore binária de busca têm um campo pai.  Escreva um função que remova um nó da árvore. Faça duas versões: uma recursiva e uma iterativa.

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

  1. Considere árvores binárias de busca cujos nós têm a estrutura indicada abaixo.  Escreva uma função que receba a raiz de uma tal árvore e o endereço de um nó x e devolva o endereço do pai de x.
    typedef struct reg {
       int         chave, conteudo;
       struct reg *esq, *dir; 
    } noh;
    

    Se x não pertence à árvore, a função deve devolver NULL.  O consumo de tempo de sua função deve ser limitado pela profundidade de x.  (Dê uma solução melhor que as respostas à pergunta How can we find the parent of a node in a given binary tree if it does not have a pointer for the parent? no Quora.)