Home | Administração | Fórum | Livros | WWW | Diário | Tarefas | Alunos |
Esta página é parcialmente baseada nas seções 13.1 e 13.2 do capítulo 13 (Trees) do livro de Eric Roberts.
Eis uma definição recursiva do conceito: uma árvore binária sobre um conjunto de objetos é
No item 2 da definição, a primeira árvore binária do par é conhecida como subárvore esquerda e a segunda é conhecida como subárvore direita.
Uma árvore binária (= binary tree) é uma estrutura de dados mais geral que uma lista encadeada. Cada uma de seus nós consiste em uma chave e dois ponteiros. Um dos ponteiros contém o endereço do "filho esquerdo" do nó, e o outro contém o endereço do "filho direito". Uma folha de uma árvore é um nó sem filhos.
Nos nossos exemplos, as chaves serão do tipo string, mas em geral a chave de um nó pode ser qualquer coisa: um int, um float etc. Nos exemplos que se seguem, cada nó da árvore binária será um objeto do tipo nodeT:
typedef struct nodeT { string key; struct nodeT *left; struct nodeT *right; } nodeT;
Uma árvore binária é, então, um objeto do tipo treeT:
typedef struct nodeT *treeT;
Ao contrário de uma lista encadeada, uma árvore binária pode ser percorrida de muitas maneiras diferentes. Uma maneira particularmente importante é a ordem raiz-esquerda-direita (= preorder traversal) ou r-e-d. Nessa maneira de percorrer a árvore, visitamos
Na figura abaixo, os nós estão numerados na ordem da varredura r-e-d.
0 / \ 1 6 / \ / \ 2 5 7 9 / \ \ 3 4 8 |
Eis uma função (recursiva) que imprime as chaves da árvore em ordem r-e-d:
// Recebe uma árvore binária t. // Imprime as chaves dos nós em ordem r-e-d. ivoid PreorderPrint( treeT t) { if (t != NULL) { printf( "%d\n", t->key); PreorderPrint( t->left); PreorderPrint( t->right); } }
Eis uma função (recursiva) que procura encontrar um nó com uma dada chave. A função percorre a árvore em ordem r-e-d:
// Recebe uma árvore binária t e uma string k. // Devolve o endereço de um nó que contém a chave k. treeT FindNode( treeT t, string k) { treeT s; if (t == NULL || strcmp( k, t->key) == 0) return t; s = FindNode( t->left, k); if (s == NULL) s = FindNode( t->right, k) return s; }
555 / \ 333 888 / \ \ 111 444 999 |
555 333 111 - - 444 - - 888 - 999 - -
onde os caracteres '-' representam NULL.
A altura de um nó x em uma árvore binária é a "distância" entre x e o seu descendente mais afastado. Por exemplo, a altura de uma folha é 0.
A altura de uma árvore é a altura da raiz da árvore. Uma árvore com um único nó tem altura 0. Por convenção, a altura de uma árvore vazia é -1. 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:
// Esta função devolve a altura da árvore // binária cuja raiz é r. int Height( treeT t) { if (t == NULL) return -1; else { int lH, rH; lH = Height( t->left); rH = Height( t->right); if (lH < rH) return rH + 1; else return lH + 1; } }
Qual a relação entre o número de nós, digamos n, de uma árvore binária e a altura, digamos h, da árvore? Resposta:
n-1 > h > lg(n) .
Para ser mais exato, h > chão(lg(n)). É claro que lg é o logaritmo na base 2.
n | chão(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 nó tem no máximo um filho. Agora considere o outro extremo: que cara tem uma árvore binária com h = chão(lg(n))? Numa tal árvore a maioria dos nós que não são folhas têm ambos os filhos:
H / \ D K / \ / \ B F J L / \ / \ / A C E G I |
Uma árvore binária é balanceada (ou equilibrada) se, em cada um de seus nós, as subárvores esquerda e direita tiverem aproximadamente a mesma altura. Uma árvore binária balanceada com n nós 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.