Uma árvore de busca é uma maneira bastante popular de implementar uma tabela de símbolos. Esta página discute o conceito de árvore de busca com base nas seções 12.4, 12.5 e 12.8 do livro do Sedgewick.
Sabemos fazer uma busca binária em um vetor ordenado.
Será possível fazer uma busca binária
em uma lista ordenada?
A rigor, a resposta é não.
Mas é possível imitar uma busca binária
se transformarmos a lista em uma árvore
que esteja ordenada
num certo sentido.
Suponha que a lista está em ordem crescente em
relação a uma chave —
um número inteiro, por exemplo —
presente em cada nó da lista.
Os nós de nossa árvore
serão essencialmente iguais aos da lista,
e portanto cada nó conterá uma chave.
Diremos que a árvore está ordenada
se as chaves aparecem em ordem crescente
quando a árvore é percorrida em ordem
esquerda-raiz-direita
(= inorder).
Em outras palavras,
se a chave de cada nó da árvore é
Qualquer árvore com essa propriedade é conhecida como árvore de busca (= binary search tree = BST).
Suponha que os nós de nossa árvore de busca têm a seguinte estrutura:
typedef struct node *link;
struct node {
int chave;
link l, r;
} ;
(Portanto, a chaves são números inteiros.) A função abaixo faz uma busca na árvore. A função procura um nó cuja chave seja igual a v. (A função foi extraída do programa 12.7 de Sedgewick.)
// Recebe uma árvore de busca h e um
// inteiro v. Devolve um nó cuja chave
// é igual a v. Devolve NULL se tal nó
// não existe.
link searchR (link h, int v) {
int t;
if (h == NULL) return NULL;
t = h->chave;
if (v == t) return h;
if (v < t)
return searchR(h->l, v);
else
return searchR(h->r, v);
}
Quanto tempo searchR consome? O consumo de tempo é proporcional ao número de comparações entre v e chaves de nós. No pior caso, o número de comparações é o dobro da altura da árvore.
A altura de uma árvore com n nós fica entre lg(n) e n. Uma árvore é considerada equilibrada ou balanceada se sua altura é da ordem de lg(n). Numa árvore equilibrada, a maior parte das folhas está na mesma profundidade.
link procura(link h, int v) {
while (h != NULL && h->chave > v) h = h->l;
while (h != NULL && h->chave < v) h = h->r;
return h;
}
Como é possível inserir um novo nó em uma árvore de busca sem que ela deixe de ser uma árvore de busca? Eis uma solução extraída do programa 12.7 de Sedgewick.
// Recebe uma árvore de busca h e um
// inteiro v. Insere na árvore um novo
// nó com chave igual a v. Devolve o
// endereço da nova árvore de busca.
link insertR (link h, int v) {
int t;
if (h == NULL) {
link x = malloc(sizeof *x);
x->chave = v;
x->l = x->r = NULL;
return x;
}
t = h->chave;
if (v < t)
h->l = insertR (h->l, v);
else
h->r = insertR (h->r, v);
return h;
}
Quanto tempo insertR consome? O tempo é proporcional ao número de comparações entre chaves. E o número de comparações é, no pior caso, proporcional à altura da árvore. (Se a árvore for balanceada, sua altura é da ordem de lg(n).)
Depois de várias operações de inserção,
uma árvore de busca está, em geral,
desbalanceada
.
Para restabelecer o equilíbrio,
usa-se o truque das rotações
(program 12.11 no livro do Sedgewick):
// Recebe uma árvore binária h tal que
// h != NULL e h->l != NULL.
// Executa uma rotação para a direita
// em torno de h. Devolve o endereço da
// nova raiz da árvore.
link rotR(link h) {
link x = h->l;
h->l = x->r;
x->r = h;
return x;
}
// Recebe uma árvore binária h tal que
// h != NULL e h->r != NULL.
// Executa uma rotação para a esquerda
// em torno de h. Devolve o endereço da
// nova raiz da árvore.
link rotL(link h) {
link x = h->r;
h->r = x->l;
x->l = h;
return x;
}
A figura mostra o efeito de uma rotação esquerda em torno da raiz B:
B F
/ \ / \
A F B H
/ \ / \ / \
D H A D G I
/ \ / \ / \
C E G I C E
As operações de rotação são fundamentais para
re-balancear
árvores desbalanceadas
.
Não vamos estudar esse processo aqui,
mas vamos mostrar como
as rotações permitem inserir um novo nó
na posição da raiz de uma árvore de busca
(veja programa 12.12 de Sedgewick):
// Recebe uma árvore de busca h e um
// inteiro v. Insere novo nó com chave v
// de tal modo que (1) ele seja a raiz da
// nova árvore e (2) a árvore continue
// sendo de busca. Devolve o endereço da
// nova árvore de busca.
link insertT(link h, int v) {
if (h == NULL) {
link x = malloc(sizeof *x);
x->chave = v;
x->l = x->r = NULL;
return x;
}
if (v < h->chave) {
h->l = insertT(h->l, v);
h = rotR(h);
}
else {
h->r = insertT(h->r, v);
h = rotL(h);
}
return h;
}
Nos exemplos acima, cada nó da árvore de busca contém um número inteiro — a chave — e nada mais (sem contar os links, é claro). Amanhã posso precisar de nós que contêm caracteres (além da chave). Depois de amanhã posso precisar de nós que contêm um struct com o nome, o número e nota de um aluno. Na semana que vem posso precisar . . . Em cada um desses casos, seria preciso reescrever o código das funções de busca e inserção.
Mas os algoritmos por trás das funções são sempre os mesmos.
Gostaríamos, então,
de escrever um código genérico
que sirva para todas as aplicações.
Esta é a atitude que Sedgewick adota no capítulo 12.
As várias estruturas de dados são definidas
de tal maneira que a alteração de uns poucos #define
e typedef
adapta a estrutura a diferentes usos e aplicações.
Para começar, temos um tipo-de-dados básico Key (com K maiúsculo) para as chaves. Nos exemplos das seções anteriores tinhamos, implicitamente,
typedef int Key;
Para comparar objetos do tipo Key, Sedgewick tem duas macro-instruções (para o pré-processador), que serão aplicadas a objetos do tipo Key. Se as chaves são número inteiros, podemos ter
#define eq(A, B) (A == B) #define less(A, B) (A < B)
Em seguida, Sedgewick tem um tipo-de-dados Item
que representa o conteúdo
de cada nó.
Por exemplo,
typedef struct {
char *nome;
Key chave;
} Item;
(Nos exemplos das seções anteriores o tipo Item se confundia com Key.) Para extrair chaves, Sedgewick imagina uma macro key (com k minúsculo) que será aplicada a objetos do tipo Item. Por exemplo,
#define key(A) (A.chave)
Para fazer o papel de item nulo
ou item vazio
,
Sedgewick imagina um objeto NULLitem
que seja diferente
de qualquer Item que o usuário considere válido.
Por exemplo,
se todas as chaves válidas forem não negativas,
poderíamos definir NULLitem assim:
Item NULLitem; NULLitem.chave = -1;
Os nós das árvores serão da seguinte forma:
typedef struct STnode *link;
struct STnode {
Item item;
link l, r;
} ;
(O prefixo ST lembra search tree.) O formato das árvores será ligeiramente diferente do que usamos acima: se um nó x não tem filho esquerdo, por exemplo, então em lugar de x->l = NULL Sedgewick faz
x->l = z
sendo z um nó fixo, criado especialmente para esta finalidade:
link z = malloc(sizeof (struct STnode)); z->item = NULLitem; z->l = z->r = NULL;
A vantagem desse circo todo é que basta mudar alguns typedef e alguns #define para que as funções de manipulação das árvores possam ser aplicadas a diferentes tipos de nós. Por exemplo, podemos ter
typedef char *Key;
#define eq(A, B) (strcmp(A, B) == 0)
#define less(A, B) (strcmp(A, B) < 0)
typedef struct {
char *nome;
int *numero;
float *nota;
Key codigo;
} Item;
#define key(A) (A.codigo)
Item NULLitem;
NULLitem.codigo[0] = '\0';
Busca. Eis como fica a função de busca no programa 12.7 de Sedgewick. A variável global head
link head;
aponta para a raiz da árvore. A seguinte função (versão simplificada do programa 12.7) faz uma busca na árvore:
// Recebe um Key v e devolve um Item x
// tal que key(x) == v. Se tal Item não
// existe então a função devolve NULLitem.
// Todos os Item estão armazenados em uma
// árvore de busca cuja raiz é head.
Item STsearch (Key v) {
return searchR (head, v);
}
Item searchR(link h, Key v) {
Key t = key(h->item);
if (h == z) return NULLitem;
if eq(v, t) return h->item;
if less(v < t)
return searchR(h->l, v);
else
return searchR(h->r, v);
}
Inserção. A seguinte função (veja programa 12.7) insere um novo nó na árvore de busca:
// Insere na árvore de busca cuja raiz
// é head um novo nó com contéudo item.
// (A raiz da nova árvore pode ser
// diferente da árvore original.)
void STinsert (Item item) {
head = insertR (head, item);
}
link insertR (link h, Item item) {
Key v = key(item), t = key(h->item);
if (h == z) {
link x = malloc(sizeof *x);
x->item = item;
x->l = x->r = z;
return x;
}
if less(v, t)
h->l = insertR (h->l, item);
else
h->r = insertR (h->r, item);
return h;
}
Veja uma versão não recursiva da função STinsert (programa 12.9):
void STinsert(Item item) {
Key v = key(item);
link p = head, x = p;
if (head == NULL) {
head = NEW(item, NULL, NULL);
return;
}
while (x != NULL) {
p = x;
x = less(v < key(x->item)) ? x->l : x->r;
// agora p é pai de x
}
x = NEW(item, NULL, NULL);
if less(v < key(p->item)) p->l = x;
else p->r = x;
}
link NEW(Item item, link l, link r) {
link x = malloc(sizeof *x);
x->item = item;
x->l = l; x->r = r;
return x;
}
Exercícios
Veja minhas notas de aula sobre árvores de busca. Veja também os excelentes capítulos 13 e 14 do livro de Roberts.