(Veja o verbete Binary search tree na Wikipedia.)
Árvores binárias generalizam a idéia de listas encadeadas. Da mesma forma, árvores binárias de busca generalizam a idéia de listas encadeadas crescentes. Em inglês, essas árvores são conhecidas como search trees. Dizemos que uma árvore binária é de busca (ou de pesquisa) se cada uma de suas células tem a seguinte propriedade: a chave da célula é
Em outras palavras, se r é o endereço de uma célula qualquer, se q é o endereço de alguma célula na subárvore esquerda de r e se s é o endereço de alguma célula na subárvore direita de r então
q->chave ≤ r->chave ≤ s->chave.
Há uma outra maneira, talvez mais clara, de descrever essa propriedade: a ordem e-r-d das chaves é crescente.
Vamos examinar abaixo os problemas de busca, remoção e inserção em uma árvore de busca. Suporemos que cada célula da árvore tem a estrutura
typedef struct celula *arvore;
struct celula {
arvore pai;
int chave;
arvore esq;
arvore dir;
} ;
Considere o seguinte problema: Dada uma árvore de busca, encontrar uma célula da árvore cuja chave tenha um certo valor k.
Eis uma função recursiva que devolve uma célula y tal que y->chave == k; se um tal y não existe, a função devolve NULL.
// Recebe um inteiro k e uma árvore de busca r.
// Devolve o endereço de uma célula cuja chave é k;
// se tal célula não existe então devolve NULL.
arvore 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;
Considere o seguinte problema: Inserir uma nova célula em uma dada árvore de busca. É claro que a nova árvore deve também ser de busca; é aí que está a dificuldade do problema.
Vamos adotar a política de criar a nova célula fora da função de inserção:
arvore ins;
ins = mallocX (sizeof (struct celula));
ins->chave = k;
ins->esq = ins->dir = NULL;
A função abaixo insere a nova célula na árvore de busca r. 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 // celula ins que não pertence à árvore. A função // insere ins na árvore r de modo que a árvore // continue sendo de busca e devolve o endereço // da nova árvore. arvore insere (arvore r, arvore ins) { arvore f, p; if (r == NULL) { ins->pai = NULL; return ins; } // agora r != NULL f = r; do { p = f; if (p->chave > ins->chave) f = p->esq; else f = p->dir; } while (f != NULL); ins->pai = p; if (p->chave > ins->chave) p->esq = ins; else p->dir = ins; return r; }
Há uma maneira mais sofisticada de fazer o serviço, usando um ponteiro-para-ponteiro:
// Recebe o endereço rr do endereço de uma
// árvore de busca e uma célula avulsa ins.
// Insere ins no lugar correto da árvore e
// atualiza rr de modo que *rr seja o endereço do
// endereço da raiz da nova árvore.
void insere (arvore *rr, arvore ins) {
arvore p, r;
r = *rr;
p = NULL;
while (*rr != NULL) {
p = *rr;
if (p->chave > ins->chave) rr = &(p->esq);
else rr = &(p->dir);
}
*rr = ins;
ins->pai = p;
if (p == NULL) *rr = r;
}
Considere o seguinte problema: Remover uma célula de uma árvore de busca de tal forma que a árvore continue sendo de busca.
Digamos que queremos remover uma célula y cujo pai é x. Se y tem um só filho então basta dizer que o filho de y passa a ser filho de x. Suponha agora que y tem dois filhos. Nesse caso, será preciso fazer um serviço mais complexo.
Seja c o predecessor de y na ordem e-r-d; seja a = c->pai e b = c->esq. Agora basta fazer com que b seja o filho de a e colocar a célula c no lugar de y (os filhos de y passarão a ser os filhos de c).
y / . / \ . / \ a / \ c / b
A função básica de remoção trata do caso em que y é a raiz da árvore:
// Recebe uma árvore não-vazia y. Remove a raiz // da árvore, rearranja a árvore de modo que ela // continue sendo de busca e devolve o endereço // da nova raiz. arvore removeraiz (arvore y) { arvore a, b, c; if (y->esq == NULL) c = y->dir; else { c = y->esq; while (c->dir != NULL) c = c->dir; // c é a celula anterior a y na ordem e-r-d a = c->pai; if (a != y) { b = c->esq; a->dir = b; b->pai = a; c->esq = y->esq; y->esq->pai = c; } c->dir = y->dir; y->dir->pai = c; } c->pai = NULL; free (y); return c; }
Para remover o filho esquerdo de uma célula x faça
x->esq = removeraiz (x->esq);
Para remover o filho direito de x faça
x->dir = removeraiz (x->dir);
Há uma maneira mais sofisticada de fazer o serviço: ela usa um ponteiro-para-ponteiro, ou seja, um ponteiro para o endereço da raiz da árvore.
// Recebe o endereço py do endereço da raiz de uma árvore // não-vazia. Remove a raiz da árvore, rearranja a árvore // de modo que ela continue sendo de busca e atualiza py // de modo que *py seja o endereço da nova raiz da árvore. void removeRaiz (arvore *py) { arvore c, y; y = *py; if (y->esq == NULL) c = y->dir; else { arvore *pc; pc = &y->esq; c = *pc; while (c->dir != NULL) { pc = &c->dir; c = *pc; } // c é a celula anterior a y na ordem e-r-d if (c->pai != y) { *pc = c->esq; c->esq->pai = c->pai; c->esq = y->esq; } c->dir = y->dir; } c->pai = NULL; *py = c; free (y); }
Para remover uma célula que não seja a raiz da árvore basta usar a função removeRaiz de maneira apropriada: se queremos remover o filho esquerdo da célula x, devemos fazer
removeRaiz (&x->esq);
se queremos remover o filho direito da célula x, devemos dizer
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 células, digamos n, da árvore (pois nenhuma célula é 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 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. Ou, por outra, a altura da árvore depende de sorte. É 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).
Infelizmente, 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 seqüência de chamadas da função remove.
Para corrigir essa situação é preciso inventar algoritmos bem mais sofisticados e complexos de inserção e remoção; esses algoritmos fazem um "re-balanceamento" da árvore após cada inserção e cada remoção. Vou apenas citar alguns 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".