(Veja o verbete Binary tree na Wikipedia.)
Uma árvore binária (= binary tree) é uma estrutura de dados mais geral que uma lista encadeada. Eis uma definição recursiva do conceito: uma árvore binária sobre um conjunto de objetos é
Cada elemento — ou célula, ou nó — de uma árvore binária consiste em uma chave e três ponteiros. A chave é a informação que realmente interessa. Os três ponteiros servem apenas para dar estrutura à árvore: um aponta para o "filho esquerdo" da célula, outro para o "filho direito" e o terceiro para o "pai" da célula. (De acordo com essa definição, uma árvore é uma generalização de uma lista duplamente encadeada.)
Nos nossos exemplos, as chaves serão do tipo int, mas em geral a chave de uma célula pode ser qualquer coisa: um double, uma cadeia de caracteres (= string) etc.
typedef struct celula *arvore;
struct celula {
arvore pai;
int chave;
arvore esq;
arvore dir;
} ;
|
| ||||||||||||
Cada célula de uma árvore tem um endereço na memória do computador. Ao falar de árvores, é muito conveniente confundir cada célula com seu endereço. Assim, se x é um ponteiro para um objeto do tipo arvore, dizemos simplesmente "considere a célula x" em lugar de "considere a célula cujo endereço é x". Em particular, é muito conveniente confundir uma árvore com o endereço de sua raiz: dizemos "considere a árvore x" em lugar de "considere a árvore cuja raiz está no endereço x".
Para que uma estrutura montada a partir de tais células mereça o nome de árvore devemos ter x->esq->pai igual a x (desde que x->esq não seja NULL). Analogamente, devemos ter x->dir->pai igual a x .
Qualquer dos três ponteiros pode ter valor NULL. Se x é o endereço de uma célula e x->pai é NULL, dizemos que x é o endereço da raiz da árvore. Se x->esq e x->dir são ambos NULL então dizemos que x é uma folha (= leaf) da árvore.
Para especificar uma árvore binária, basta fornecer o endereço da raiz da árvore. Se esse endereço for NULL, dizemos que a árvore é vazia.
Digamos que x é o endereço de uma celula. Um ancestral de x é qualquer célula que possa ser alcançada pela iteração do comando x = x->pai . É claro que esse comando só pode ser iterado enquanto x for diferente de NULL. (Estamos supondo que x atingirá o valor NULL mais cedo ou mais tarde, ou seja, a árvore não tem circuitos.)
Um descendente de x é qualquer célula que possa ser alcançada pela iteração dos comandos x = x->esq e x = x->dir em qualquer ordem. É claro que esses comandos só podem ser iterados enquanto x for diferente de NULL. (Estamos supondo que NULL é de fato atingido mais cedo ou mais tarde.)
Uma célula x juntamente com todos os seus descendentes é uma árvore binária. Se x tiver um pai, essa árvore é uma subárvore de alguma árvore maior. Para qualquer célula x,
x->esq é a raiz da subárvore esquerda de x;
analogamente, x->dir a raiz da subárvore direita de x.
Ao contrário de uma lista encadeada, uma árvore binária pode ser percorrida de muitas maneiras diferentes. Uma maneira particularmente importante é a ordem esquerda-raiz-direita. Na varredura e-r-d (= inorder traversal), visitamos
Na figura abaixo, as células estão numeradas na ordem da varredura e-r-d.
5
/ \
3 8
/ \ / \
1 4 6 9
/ \ \
0 2 7
|
Eis uma função recursiva que faz a varredura e-r-d de uma árvore cuja raiz tem endereço r:
// Recebe a raiz r de uma árvore binária.
// Imprime as chaves das celulas em ordem e-r-d.
void erd (arvore r) {
if (r != NULL) {
erd (r->esq);
printf ("%d\n", r->chave);
erd (r->dir);
}
}
É um excelente exercício escrever uma versão iterativa desta função. Nossa versão usa uma pilha p[0..t-1] de endereços e mais um endereço r que é candidato a entrar na pilha; é como se a pilha fosse
p[0], p[1], . . . , p[t-1], r.
A seqüência r, p[t-1], . . . , p[0] é uma espécie de "roteiro" daquilo que ainda precisa ser feito. O endereço r representa o comando "imprima a árvore cuja raiz é r" e cada p[i] representa o comando "imprima a célula p[i] e em seguida a árvore cuja raiz é p[i]->r". Para dimensionar a pilha, suporemos que nossa árvore não tem mais que 100 células.
// Recebe a raiz r de uma árvore binária. // Imprime as chaves das celulas em ordem e-r-d. // Supõe que a árvore não tem mais que 100 células. void erd_i (arvore r) { arvore p[100]; int t = 0; while (r != NULL || t > 0) { // a pilha é p[0..t-1]; o índice do topo é t-1 if (r != NULL) { p[t++] = r; r = r->esq; } else { r = p[--t]; printf ("%d\n", r->chave); r = r->dir; } } }
Para a árvore sugerida na figura acima, a pilha p evolui como indicado na tabela abaixo. Cada linha da tabela resume o estado de coisas no início de uma iteração: à esquerda estão as células que já foram impressas; à direita está a pilha r, p[t-1], . . . , p[0]. O valor NULL está indicado por N.
5
3 5
1 3 5
0 1 3 5
N 0 1 3 5
0 N 1 3 5
0 1 2 3 5
0 1 N 2 3 5
0 1 2 N 3 5
0 1 2 3 4 5
0 1 2 3 N 4 5
0 1 2 3 4 N 5
0 1 2 3 4 5 8
0 1 2 3 4 5 6 8
0 1 2 3 4 5 N 6 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 N 7 8
0 1 2 3 4 5 6 7 N 8
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 N 9
0 1 2 3 4 5 6 7 8 9 N
No início de cada iteração, a seqüência r, p[t-1], . . . , p[0] é uma espécie de "roteiro" daquilo que ainda precisa ser feito. O roteiro deve ser interpretado assim: Primeiro, imprima, em ordem e-r-d, as chaves da subárvore que tem raiz r. Depois, para i decrescendo de t-1 até 0, faça o seguinte: (1) imprima a chave de p[i] e (2) imprima, em ordem e-r-d, as chaves da subárvore direita de p[i].
A título de curiosidade, eis uma redação ligeiramente diferente da versão iterativa da função e-r-d:
while (1) {
while (r != NULL) {
p[t++] = r;
r = r->esq;
}
if (t == 0) break;
r = p[--t];
printf ("%d\n", r->chave);
r = r->dir;
}
555
/ \
333 888
/ \ \
111 444 999
|
deve se representada assim:
555
333
111
-
-
444
-
-
888
-
999
-
-
onde os caracteres '-' representam NULL.
Considere o seguinte problema: encontrar o endereço da primeira célula na ordem e-r-d. É claro que o problema só faz sentido se a árvore não é vazia, ou seja, se r é diferente de NULL. Eis uma função que resolve o problema
// Recebe o endereço r de uma árvore binária não vazia.
// Devolve o endereço da primeira célula na ordem e-r-d.
arvore primeira (arvore r) {
while (r->esq != NULL)
r = r->esq;
return r;
}
Não é difícil fazer uma função análoga que encontre a última célula na ordem e-r-d.
Digamos que x é o endereço de uma certa célula de uma árvore binária. Nosso problema: calcular o endereço da célula seguinte na ordem e-r-d.
Eis uma função que resolve o problema. É claro que a função só deve ser chamada com x diferente de NULL. A função devolve o endereço y da célula seguinte a x ou devolve NULL se x é a última célula. (Note que a função não precisa saber onde está a raiz da árvore.)
// Recebe o endereço de uma célula x. Devolve o endereço // da célula seguinte na ordem e-r-d. arvore seguinte (arvore x) { if (x->dir != NULL) { arvore y = x->dir; while (y->esq != NULL) y = y->esq; return y; // * } while (x->pai != NULL && x->pai->dir == x) // ** x = x->pai; // ** return x->pai; }
Comentários: Na linha *, y é o endereço da primeira célula, na ordem e-r-d, da subárvore que tem raiz x->dir. As linhas ** fazem com que x suba na árvore enquanto for filho direito de alguém.
A altura de uma célula x em uma árvore binária é a "distância" entre x e o seu descendente mais afastado. Mas precisamente, a altura de x é o número de links no mais longo caminho que leva de x até uma folha. Os caminhos a que essa definição se refere são os obtido pela iteração dos comandos x = x->l e x = x->r, em qualquer ordem.
A altura de uma árvore é a altura da raiz da árvore. Uma árvore com uma única célula tem altura 0. A árvore da figura tem altura 3.
E
/ \
D I
/ / \
B G K
/ \ / \ /
A C F H J
|
Eis como a altura de uma árvore com raiz r pode ser calculada:
// Devolve a altura da árvore binária cuja raiz é r. int altura (arvore r) { if (r == NULL) return -1; // altura de árvore vazia é -1 else { int he = altura (r->esq); int hd = altura (r->dir); if (he < hd) return hd + 1; else return he + 1; } }
Qual a relação entre a altura, digamos h, e o número de células, digamos n, de uma árvore binária? Resposta:
n-1 ≥ h ≥ lg(n) ,
onde lg(n) denota o piso de log2n .
| n | lg(n) |
| 4 | 2 |
| 5 | 2 |
| 6 | 2 |
| 10 | 3 |
| 64 | 6 |
| 100 | 6 |
| 128 | 7 |
| 1000 | 9 |
| 1024 | 10 |
| 1000000 | 19 |
Que cara tem uma árvore binária com h = n-1? Uma tal árvore é um "tronco sem galhos": cada célula tem no máximo um filho. Agora considere o outro extremo: que cara tem uma árvore binária com h = lg(n)? Uma tal árvore é "quase completa": todos os "níveis" estão lotados exceto talvez o último.
H
/ \
D K
/ \ / \
B F J L
/ \ / \ /
A C E G I
|
Uma árvore binária é balanceada (ou equilibrada) se, em cada uma de suas células, as subárvores esquerda e direita tiverem aproximadamente a mesma altura. Uma árvore binária balanceada com n células tem altura próxima de lg(n). Convém trabalhar com árvores balanceadas sempre que possível. Mas isso não é fácil se a árvore aumenta e diminui ao longo da execução do seu programa.