(Veja o verbete Binary search tree na Wikipedia.)
Assim como árvores binárias generalizam a ideia de listas encadeadas, árvores binárias de busca (= search trees) generalizam a ideia de listas encadeadas crescentes.
Considere uma árvore binária cujos nós têm um campo chave de um tipo linearmente ordenado, ou seja, de um tipo (como int ou string, por exemplo) que admite comparações. Podemos supor que os nós da árvore têm a seguinte estrutura:
struct cel {
int chave;
int conteudo;
struct cel *esq;
struct cel *dir;
};
typedef struct cel no; /* nó */
Uma árvore binária deste tipo é de busca (em relação ao campo chave) se cada nó X tem a seguinte propriedade: a chave de X é
Em outras palavras, se x é (o endereço de) um nó qualquer então
y->chave ≤ x->chave ≤ z->chave.
para todo nó y na subárvore esquerda de x e todo nó z na subárvore direita de x.
Há uma outra maneira, talvez mais clara, de descrever esta propriedade: a ordem e-r-d das chaves é crescente.
Vamos examinar abaixo os problemas de busca, remoção e inserção em árvores de busca. Convém introduzir o tipo-de-dados arvore:
typedef no *arvore; /* árvore */
Considere o seguinte problema: Dada uma árvore de busca, encontrar um nó da árvore cuja chave tenha um certo valor k.
Eis uma função recursiva que devolve (o endereço de) um nó x tal que x->chave == k; se um tal x não existe, a função devolve NULL.
// Recebe um inteiro k e uma árvore de busca r.
// Devolve um nó cuja chave é k;
// se tal nó não existe, devolve NULL.
no *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);
}
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;
No pior caso, a busca consome tempo proporcional à altura da árvore. Se a árvore for balanceada. o consumo será proporcional a lg(n), sendo n o número de nós. Compare isso com a busca binária num vetor ordenado.
Considere o seguinte problema: Inserir um novo nó em uma árvore de busca. É claro que a árvore resultante deve também ser de busca; é aí que está a dificuldade do problema.
Vamos adotar a política de criar o novo nó fora da função de inserção:
no *novo;
novo = mallocc (sizeof (no));
novo->chave = k;
novo->esq = novo->dir = NULL;
A função abaixo insere o novo nó na árvore de busca r. O novo nó será uma folha da árvore e o endereço da nova árvore será igual a r a menos que r seja NULL.
// A função recebe uma árvore de busca r e uma
// folha nova que não pertence à árvore.
// A função insere o nó novo na árvore
// de modo que a árvore continue sendo de busca
// e devolve o endereço da nova árvore.
arvore insere (arvore r, no *novo) {
no *f, *p;
if (r == NULL) return novo;
f = r;
while (f != NULL) {
p = f;
if (f->chave > novo->chave) f = f->esq;
else f = f->dir;
}
if (p->chave > novo->chave) p->esq = novo;
else p->dir = novo;
return r;
}
O código da função insere é um tanto feio e deselegante. (Trata em separado do caso r == NULL e a comparação das chaves na última iteração do while é repetida depois do while.) Para melhorar isso, podemos usar um ponteiro-para-ponteiro (veja o livro de Masters):
// Recebe o endereço eer do endereço de uma
// árvore de busca e uma folha avulsa novo.
// Insere novo no lugar correto da árvore e
// atualiza *eer de modo que esse seja
// o endereço da nova árvore.
void insere (arvore *eer, no *novo) {
no *p, *r;
r = *eer;
p = NULL;
while (*eer != NULL) {
p = *eer;
if (p->chave > novo->chave) eer = &(p->esq);
else eer = &(p->dir);
}
*eer = novo;
if (p != NULL) *eer = r;
}
Considere o seguinte problema: Remover um nó de uma árvore de busca de tal forma que a árvore continue sendo de busca.
Comecemos tratando do caso 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 a nó anterior à raiz na ordem e-r-d assuma o papel de raiz.
.r
/
.
/ \
.
/ \
. p
/ \
. q
/
.
/ \
|
// Recebe uma árvore não vazia r. Remove a raiz // da árvore, rearranja a árvore de modo que ela // continue sendo de busca. // Devolve o endereço da nova raiz. arvore removeraiz (arvore r) { no *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 é o 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);
Quanto tempo gastam os algoritmos de busca, inserção e remoção discutidos acima? É claro que esse tempo é limitado pelo número de nós, digamos n, da árvore (pois nenhum nó é visitada mais que 3 vezes). Mas esta é uma resposta muito grosseira. Eis uma resposta mais fina: qualquer dos algoritmos acima
gasta uma quantidade de tempo que, no pior caso, é 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 dessa brincadeira).
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 bastante "desbalanceada". Algo análogo pode acontecer depois de uma sequência de chamadas da função remove.
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 produzem "árvores AVL"; há um outro pacote que produz "árvores rubro-negras".