Este é um resumo de parte das seções 5.4 (Trees), 5.6 (Tree traversal), 5.7 (Recursive binary-tree algorithms) e 12.5 (Binary Search Trees) do livro do Sedgewick.
Uma árvore binária (= binary tree) é um conjunto de nós; cada nó tem (a) um certo conteúdo (por exemplo, um número inteiro) e (b) os endereços das raízes de duas subárvores, uma esquerda e uma direita. Veja um exemplo típico de estrutura de nó:
typedef struct node *link;
struct node {
int item; // conteúdo do nó
link l, r; // 'l' de "left" e 'r' de "right"
} ;
(Cuidado: não confunda a letra l
com o dígito 1
.)
Em alguns contextos, convém trocar a palavra item
por chave
.
Termos técnicos importantes: raiz de uma árvore, filho de um nó, pai de um nó, folha de uma árvore, nó interno de uma árvore, nível de um nó.
Em geral, quando dizemos um nó x
devemos entender que x é
o endereço de um nó.
Nesses termos, o filho esquerdo de um nó x
é x->l
e o filho direito é x->r.
Um nó x é uma folha se não tem filhos, ou seja,
se x->l
e x->r valem NULL.
Para ilustrar o conceito de árvore, eis uma pequena função que calcula o número de nós de uma árvore binária (veja programa 5.17 do Sedgewick).
// Esta função devolve o número de nós
// da árvore binária cuja raiz é h.
int count(link h) {
if (h == NULL) return 0;
return count(h->l) + count(h->r) + 1;
}
(O h
é a inicial de here
.)
A altura (= height)
de um nó h
em uma árvore binária
é a distância
entre h e o seu descendente mais afastado.
Mas precisamente,
a altura de h
é o número de links no mais longo caminho que leva de h
até uma folha.
Os caminhos a que essa definição se refere
são os obtidos pela iteração dos comandos
x = x->l e
x = x->r,
em qualquer ordem.
Exemplo:
a altura de uma folha é 0.
A função abaixo calcula a altura de um nó h (veja programa 5.17 do Sedgewick). Ela dá a resposta correta até mesmo quando h é NULL.
// Devolve a altura de um nó h em uma
// árvore binária.
int height(link h) {
int u, v;
if (h == NULL) return -1;
u = height(h->l);
v = height(h->r);
if (u > v) return u+1;
else return v+1;
}
A altura de uma árvore é a altura de sua raiz. A altura de uma árvore com N nós pode variar de lg(N) até N-1. (Como de hábito, lg é uma abreviatura de ⌊log2⌋.)
distânciax e h. Mais precisamente, a profundidade de x é o comprimento do (único) caminho que vai de h até x. Por exemplo, a profundidade de h é 0 e a profundidade de h->l é 1. Escreva uma função que determine a profundidade de um nó dado em relação à raiz da árvore.
desce para a esquerdatemos um 0; toda vez que
desce para a direitatemos um 1. Diremos que essa sequência de 0s e 1s é o código do nó. Suponha agora que todo nó de nossa árvore tem um campo adicional cod capaz de armazenar uma cadeia de caracteres. Escreva uma função que preencha o campo cod de cada nó com o código do nó.
O seguinte exemplo é uma versão simplificada do programa 5.14 do Sedgewick. Ele imprime o conteúdo de cada nó da árvore binária cuja raiz é h.
// Imprime o item de cada nó de uma árvore
// binária h que tem nós do tipo node.
void imprime (link h) {
if (h == NULL) return;
printf("%d\n", h->item);
imprime(h->l);
imprime(h->r);
}
Esta função percorre a árvore em ordem raiz-esquerda-direita (= preorder). Se as três últimas instruções forem trocadas por
imprime(h->l);
printf("%d\n", h->item);
imprime(h->r);
a árvore será percorrida na ordem esquerda-raiz-direita (= inorder). Se as três últimas instruções forem trocadas por
imprime(h->l);
imprime(h->r);
printf("%d\n", h->item);
a árvore será percorrida na ordem esquerda-direita-raiz (= postorder).
Abaixo temos uma versão simplificada do programa 5.15 de Sedgewick. Ela recebe uma árvore h e imprime o conteúdo de cada nó. Nossa solução usa as funções de manipulação de pilha que discutimos em outro capítulo. Ela supõe que a árvore não é vazia (ou seja, que h != NULL) e tem 100 nós ou menos (na verdade, basta apenas que a altura da árvore não passe de 100).
// Imprime o item de cada nó de uma árvore
// binária h. A função supõe que h != NULL
// e que a altura da árvore não passa de 100.
void imprimeB (link h) {
STACKinit(100);
STACKpush(h);
while (!STACKempty()) {
h = STACKpop();
printf("%d\n", h->item);
if (h->r != NULL) STACKpush(h->r);
if (h->l != NULL) STACKpush(h->l);
}
}
Esta função percorre a árvore em ordem
raiz-esquerda-direita, ou seja, em preorder.
Ela usa uma pilha de nós (todos diferentes de NULL)
para gerenciar o andamento do algoritmo.
Todo nó x na pilha representa a instrução
imprima os nós da árvore cuja raiz é x
.
No código abaixo, a pilha é implementada em um vetor pilha[0..t], sendo t o índice do topo da pilha:
// Imprime o item de cada nó de uma árvore
// binária h. A função supõe que h != NULL.
void imprimeB (link h) {
link *pilha;
int t;
pilha = malloc((1+height(h)) * sizeof (link))
pilha[t=0] = h;
while (t >= 0) {
h = pilha[t--];
printf("%d\n", h->item);
if (h->r != NULL) pilha[++t] = h->r;
if (h->l != NULL) pilha[++t] = h->l;
}
free(pilha);
}
Note que pilha[i] != NULL para todo i entre 0 e t.
por níveis
Os nós de uma árvore podem ser percorridos em uma quarta ordem, diferente da raiz-esquerda-direita, da esquerda-raiz-direita e da esquerda-direita-raiz. Para fazer isso, basta usar uma fila no lugar de uma pilha. (Veja programa 5.16 de Sedgewick.)
// Imprime o item de cada nó de uma árvore
// binária h. A função supõe que h != NULL.
void imprime (link h) {
link *fila;
int i, f;
fila = malloc(count(h) * sizeof (link));
fila[0] = h;
i = 0; f = 1;
while (f > i) {
h = fila[i++];
printf("%d\n", h->item);
if (h->l != NULL) fila[f++] = h->l;
if (h->r != NULL) fila[f++] = h->r;
}
free(fila);
}
A função usa uma fila implementada em um vetor fila[i..f-1]: o índice do primeiro da fila é i e o índice do último é f-1. Todos os elementos da fila são diferentes de NULL.
O programa 5.18 de Sedgewick faz um desenho de uma árvore binária. A função show supõe que o item de cada nó é do tipo char e não do tipo int como acima.
// A função show faz um desenho esquerda- // direita-raiz da árvore x. O desenho // terá uma margem esquerda de 3b espaços. void show (link x, int b) { if (x == NULL) { printnode('*', b); return; } show(x->r, b+1); printnode(x->item, b); show(x->l, b+1); } // A função auxiliar printnode imprime o // caracter c precedido de 3b espaços e // seguido de uma mudança de linha. void printnode(char c, int b) { int i; for (i = 0; i < b; i++) printf(" "); printf("%c\n", c); }
Eis uma amostra do resultado de show(x,0).
Troquei os espaços em branco por -
para facilitar a leitura.
------* ---H ------------* ---------G ------------* ------F ---------* E ------* ---D ------------* ---------C ------------* ------B ------------* ---------A ------------*
Eis o resultado da impressão da mesma árvore
em ordem raiz-esquerda-direita.
Troquei os espaços em branco por -
para facilitar a leitura.
E ---D ------B ---------A ------------* ------------* ---------C ------------* ------------* ------* ---H ------F ---------* ---------G ------------* ------------* ------*
Para obter isso, troquei os três últimos comandos de show por
printnode(x->item, b); show(x->r, b+1); show(x->l, b+1);
Diremos que uma árvore binária é um torneio se cada nó que não seja uma folha tem dois filhos e contém uma cópia do maior dos items de seus dois filhos. O programa 5.19 de Sedgewick ilustra a construção de um torneio:
// A função max recebe um vetor não vazio
// a[p..q] (portanto p <= q) e constrói
// um torneio cujas folhas são a[p],..,a[q].
// A função devolve a raiz do torneio.
link max (int a[], int p, int q) {
int m, u, v;
link x;
m = (p + q) / 2;
x = malloc(sizeof *x);
if (p == q) {
x->l = x->r = NULL;
x->item = a[m];
return x;
}
x->l = max(a, p, m);
x->r = max(a, m+1, q);
u = x->l->item;
v = x->r->item;
if (u > v) x->item = u;
else x->item = v;
return x;
}
Compare com o programa 5.6 de Sedgewick.
Considere agora mais um exemplo de construção de árvore binária. Desta vez, a árvore representará uma expressão aritmética.
Suponha que temos uma expressão aritmética cujos operadores são todos binários. Mais concretamente, suponha que os operadores são soma (+) e multiplicação (*). Suponha também, para simplificar, que os operandos são nomes de variáveis e cada um consiste em uma única letra do alfabeto ASCII. Uma expressão aritmética pode ser muito bem representada por uma árvore binária: as folhas da árvore são os operandos e os nós internos são os operadores.
*
/ \
+ f
/ \
a *
/ \
* +
/ \ / \
b c d e
Se a árvore for lida em ordem esquerda-raiz-direita, teremos a expressão em notação infixa. Se for lida em ordem esquerda-direita-raiz, teremos a expressão em notação posfixa. Se for lida em ordem raiz-esquerda-direita-raiz, teremos a expressão em notação prefixa.
infixa (a+(b*c)*(d+e))*f posfixa abc*de+*+f* prefixa *+a**bc+def
O programa 5.20 de Sedgewick, faz o serviço inverso: transforma a expressão prefixa (não vazia, é claro) em uma árvore binária. Se a expressão consiste em uma única letra, a árvore terá um único nó; se a expressão for algo como *ab , a árvore terá uma raiz e duas folhas.
Suponha que a expressão prefixa está armazenada em um vetor global de caracteres a[i..] , sendo i uma variável global.
typedef struct Tnode *link;
struct Tnode {
char token;
link l, r;
} ;
char *a;
int i;
// A função parse atua sobre a expressão
// prefixa a[i..]. Os operadores são '+'
// e '*', cada variável tem um só caracter,
// e não há espaços entre os caracteres.
// A função transforma a expressão em uma
// árvore binária e devolve a raiz da árvore.
link parse () {
char t;
link x;
t = a[i++];
x = malloc(sizeof *x);
x->token = t;
if (t == '+' || t == '*') {
x->l = parse();
x->r = parse();
}
else x->l = x->r = NULL;
return x;
}
Compare com o programa 5.4 de Sedgewick.
O capítulo 14 do livro de Roberts discute a implementação de um processador de expressões aritméticas. Vamos extrair daquele capítulo apenas
Nossas expressões aritméticas admitem os operadores =, +, -, *, / e admitem operandos que podem ser números inteiros, nomes de variáveis e, é claro, sub-expressões. Exemplo:
=
/ \
y *
/ \
3 +
/ \
- abc
/ \
6 de
Eis a declaração do tipo de uma expressão:
typedef char *string; // Type: expression // ---------------- // This type is used to represent the abstract notion // of an expression, such as one you might encounter // in a C program. An expression is defined recursively // to be one of the following: // 1. A constant // 2. A string representing the name of a variable // in the ASCII alphabet. // 3. Two expressions combined by an operator // typedef struct node *expression // Type: exptype // ------------- // This enumeration type is used to differentiate the // three expression types: constants, variables, and // subexpressions. // typedef enum {Constant, Variable, Subexpression} exptype;
Para representar os nós da árvore vamos usar uma estrutura que envolve um union (da linguagem C):
// Type: node // ---------- // An expression is represented as tree. The contents // of each node consists of a tagged union that allows // the node to have multiple interpretations. // struct node { exptype type; union { int constRep; // a constant string varRep; // name of a variable struct { char op; // '=' or '+' or '-' or '*' or '/' expression lhs; // left subexpression expression rhs; // right subexpression } subexpRep; } contents; } ;
Finalmente, eis as funções que calculam o valor de uma expressão:
// Function: EvalExp // Usage: value = EvalExp(exp); // --------------------------- // Returns the value of the expression exp. (The // function assumes that the values of all variables // have been already loaded into the appropriate table.) // int EvalExp (expression exp) { switch (exp->type) { case Constant: return exp->contents.constRep; case Variable: return GetVariableValue(exp->contents.varRep); case Subexpression: return EvalSubExp(exp); } } // Returns the value of the subexpression exp. (The // values of all variables must have been already // loaded into the appropriate table.) // static int EvalSubExp (expression exp) { char op; expression leftexp, rightexp; int leftval, rightval; op = exp->contents.subexpRep.op; leftexp = exp->contents.subexpRep.lhs; rightexp = exp->contents.subexpRep.rhs; if (op == '=') { rightval = EvalExp(rightexp); SetVariableValue(leftexp->contents.varRep, rightval); return rightval; } leftval = EvalExp(leftexp); rightval = EvalExp(rightexp); switch (op) { case '+': return leftval + rightval; case '-': return leftval - rightval; case '*': return leftval * rightval; case '/': return leftval / rightval; } } // Prototypes of auxiliary functions: // Returns the value of variable var. int GetVariableValue(string var) ; // Sets the value of variable var to val. int SetVariableValue(string var, int val) ;
(O par de funções (EvalExp, EvalSubExp)
é mutuamente recursivo
.)
paralelos, item[1..N], l[1..N] e r[1..N]; para cada índice i, armazene em l[i] o índice do filho esquerdo de i e em r[i] o índice do filho direito.
Reescreva todas as funções deste capítulo para a implementação que acabamos de sugerir. (Essa implementação tem certas vantagens porque reduz o tempo consumido pelas sucessivas chamadas de malloc durante a construção da árvore. Mas exige que o número total de nós seja conhecido antes que a árvore comece a ser construída.)
Um arquivo de texto nada mais é que uma cadeia de caracteres (= string). Para simplificar, vamos nos restringir ao conjunto ASCII de caracteres. Suponha dada uma cadeia de caracteres, digamos
bafeabacaadefa
Cada caracter dessa cadeia é representado por 8 bits na tabela ASCII:
| caracter | código ASCII | bits |
| a | 97 | 01100001 |
| b | 98 | 01100010 |
| c | 99 | 01100011 |
| d | 100 | 01100100 |
| e | 101 | 01100101 |
| f | 102 | 01100110 |
Portanto, a cadeia como um todo é representada pela seguinte sequência de 112 bits (a sequência foi dividida em três linhas para que coubesse na tela):
0110001001100001011001100110010101100001011 0001001100001011000110110000101100001011001 00011001010110011001100001
Agora adote uma codificação com número variável de bits — poucos bits para as letras mais frequentes e muitos bits para as letras raras:
| caracter | bits |
| a | 0 |
| b | 101 |
| c | 100 |
| d | 111 |
| e | 1101 |
| f | 1100 |
Com isso, podemos representar nossa cadeia de caracteres por uma sequência de apenas 34 bits:
1010110011010101010000111110111000
Note que não temos separadores entre as subsequências que representam os caracteres. Apesar disso, a sequência de bits pode ser decodificada sem ambiguidade. Essa é uma propriedade valiosa de nossa tabela de códigos. A propriedade decorre do seguinte fato: o código pode ser representado por uma árvore cujas folhas são os caracteres da cadeia:
.
/ \
a .
/ \
. .
/ \ / \
c b . d
/ \
f e
Para determinar o código de um caracter x, comece na raiz e caminhe até x; toda vez que descer para a esquerda, acrescente um 0 ao código de x; toda vez que descer para a direita, acrescente um 1. (Veja exercício sobre códigos de nós.)
Problema: Dada uma cadeia de caracteres, construir uma tabela de codificação que represente a cadeia usando o menor número possível de bits.
Eis um algoritmo que resolve o problema. Seja X o conjunto dos caracteres e digamos que cada caracter x de X ocorre n(x) vezes na cadeia de caracteres. Construa, como especificarei a seguir, uma árvore binária em que os items dos nós são números inteiros. Comece com um nó para cada caracter x e atribua n(x) ao item do nó. Coloque os nós em ordem crescente de item. Sejam x e y os dois primeiros nós da lista. Faça com que x e y sejam os filhos de um novo nó z. O item do novo nó será a soma dos items de x e y. Retire x e y de X e acrescente o nó z a X. Repita o processo até que tenhamos uma árvore. Essa é a árvore de Huffman da cadeia de caracteres dada.
Exemplo: Suponha que nossa cadeia só contém os caracteres a, b, c, d, e, f e que o número de ocorrências de cada caracter é dado pela tabela a seguir. Se aplicarmos o algoritmo a essa tabela, teremos a árvore da figura acima.
x a b c d e f n(x) 45 13 12 16 9 5
Exercício: Escreva uma função que receba uma cadeia de caracteres e construa uma árvore de Huffman para essa cadeia.
Veja também o exercício sobre reconstrução da árvore de códigos.
(O material sobre codificação e compressão de arquivos pode ser encontrado no capítulo 22 da 2-a edição do livro do Sedgewick. Também pode ser encontrado no livro Introduction to Algorithms de Cormen, Leiserson, Rivest e Stein.)