| Home | Administração | Fórum | Livros | WWW | Diário | Tarefas | Alunos |
Esta página é parcialmente baseada nas seções 13.xxx e 13.xxx do capítulo 13 (Trees) do livro de Eric Roberts.
Árvores binárias generalizam a idéia de listas encadeadas. Da mesma forma, árvores (binárias) de busca (= search trees) generalizam a idéia de listas encadeadas crescentes. Pode-se dizer, informalmente, que uma árvore de busca é uma estrutura que permite fazer busca binária em uma lista ligada.
Dizemos que uma árvore binária é de busca se cada um de seus nós tem a seguinte propriedade: a chave do nó é
Em outras palavras, se t é o endereço de um nó qualquer, se x é o endereço de algum nó na subárvore esquerda de t e se y é o endereço de algum nó na subárvore direita de t então
x->key < t->key < y->key.
Há uma outra maneira, talvez mais clara, de descrever essa propriedade: a ordem e-r-d das chaves é crescente.
Vamos supor, no que segue, que cada nó da árvore tem a estrutura
typedef struct nodeT { string key; struct nodeT *left; struct nodeT *right; } nodeT; typedef struct nodeT *treeT;
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 um nó y tal que y->key é igual a k; se um tal y não existe, a função devolve NULL.
// Recebe uma string k e uma árvore de busca t. // Devolve o endereço de um nó cuja chave é k; // se tal nó não existe então devolve NULL. treeT busca( treeT t, string k) { if (t == NULL || strcmp( t->key, k) == 0) return t; if (strcmp( t->key, k) > 0) return busca( t->left, k); else return busca( t->right, k); }
Problema: Inserir um novo nó 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 o novo nó fora da função de inserção:
nodeT *new;
new = malloc( sizeof (nodeT));
new->key = k;
new->left = new->right = NULL;
A função abaixo insere o novo nó 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 um // nó new que não pertence à árvore. A função // insere new na árvore r de modo que a árvore // continue sendo de busca e devolve o endereço // da nova árvore. treeT insere( treeT r, nodeT *new) { treeT f, p; if (r == NULL) return new; f = r; do { p = f; if (strcmp( p->key, new->key) > 0) f = p->left; else f = p->right; } while (f != NULL); if (p->key > new->key) p->left = new; else p->right = new; return r; }
Problema: Remover um nó de uma árvore de busca de tal forma que a árvore continue sendo de busca.
Digamos que queremos remover um nó 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 o pai de c e b = c->left. Agora basta fazer com que b seja o filho de a e colocar o nó c no lugar de y (os filhos de y passarão a ser os filhos de c).
y / . / \ . / \ a / \ c / b