Conceitos e
PESQUISA DE DADOS
PROF. MATEUS FILIPE DOMINGOS
Definições Básicas
Árvores são estruturas de dados extremamente úteis em muitas aplicações.
Uma árvore é formada por um conjunto finito T de elementos denominados
vértices ou nós de tal modo que se T = 0 a árvore é vazia, caso contrário temos um
nó especial chamado raiz da árvore (r), e cujos elementos restantes são particionados
em m>=1 conjuntos distintos não vazios, as sub-árvores de r, sendo cada um destes
conjuntos por sua vez uma árvore.
A forma convencional de representar uma árvore está indicado na figura abaixo.
Esta árvore tem nove nós sendo A o nó raiz.
Figura (1): Uma árvore
Os conjuntos das sub-árvores tem de ser disjuntos tem de ser disjuntos portanto a
estrutura indicada na Figura 2 não é uma árvore.
Se n é um nó da árvore T então Tn indica uma sub-árvore de T com raiz no nó n. Os nós n1, n2, ...,
nk das sub-árvores de Tn são chamados de filhos de n e n é o pai destes nós, que são nós irmãos.
Os nós B e C são filhos de A e nós irmãos. Nós sem filhos como os nós D, H, I, F e G são
chamados de folhas. A sub-árvore da esquerda do nó A tem raiz em B e a sub-árvore da direita
tem raiz em C, isto está indicado pelos dois ramos saindo de A. A ausência de um ramo na árvore
indica uma sub-árvore vazia, como a sub-árvore da direita do nó B. O número de de filhos de um
nó é chamado de grau de saída deste nó. Por exemplo, o nó C tem grau de saída 3 e o nó E grau 2.
Se o nó n é a raiz de uma sub-árvore Tn e n1 pertence a Tn então n1 é descendente
de n e n ancestral de n1. Portanto nós sem descendentes próprios é uma folha. Por exemplo, o
nó H é ancestral do nó C e o nó D é descendente do nó A.
Um caminho da árvore é composto por uma sequência de nós consecutivos (n1, n2,
..., nk-1, nk) tal que existe sempre a relação ni é pai de ni+1. Os k vértices formam k1 pares e um caminho de comprimento igual a k-1. O comprimento do caminho
entre o nó A e o nó H é 3.
O nível de um nó n pode ser definido do seguinte modo: o nó raiz tem nível 0, os
outros nós tem um nível que é maior uma unidade que o nível de seu pai. Na árvore
da figura anterior temos nós nos seguintes níveis:
•nível 0 = A
•nível 1 = B, C
•nível 2 = D, E, F, G
•nível 3 = H, I
A altura de um nó n é o número de nós do maior caminho de n até um de seus descendentes.
As folhas tem altura 1.
Existem diversas maneiras de representar árvores. Uma representação que reflete a idéia de
árvores como conjuntos aninhados é mostrado na figura 3 abaixo. A figura mostra o mesmo
conjunto da figura 1.
figura 3
Uma outra forma interessante de representar uma árvore é a representação por parênteses
aninhados. Da mesma forma que a figura 1 representa uma árvore no plano a representação
por parênteses representa uma árvore em uma linha. A sequência de parênteses representa a
relação entre os nós da estrutura.
O rótulo do nó é inserido à esquerda do abre parênteses
correspondente.
A árvore representada plenamente pela figura 1 pode ser representada
em uma linha por
(A (B(D))(C(E(H)(I))(F)(G)))
Esta representação tem importância, por exemplo, no tratamento de
expressões aritméticas, já que toda expressão aritmética pode ser colocada nesta forma.
Se colocarmos uma expressão nesta forma podemos então representá-la como uma árvore,
mostrando como ela seria calculada. Para colocarmos uma expressão em forma de
árvore devemos considerar cada operador como um nó da árvore e os seus operandos como as
duas sub-árvores.
Considere a expressão C seguinte que após receber todos os parênteses fica da seguinte maneira
(A + ((B-C)*(D%(E*F))))
Exercicio 1
Partindo da expressão acima, represente-as em uma arvore.
Removendo Nós de Árvores Binárias
1.Para remover um nó de uma árvore binária devemos considerar três casos: nó sem filhos;
2.nó com um único filho;
3.nó com dois filhos.
O caso de um nó sem filhos é o mais simples e significa apenas ajustar o ponteiro de seu pai. A
Figura remov0 ilustra este caso, onde o nó com o valor 8 é removido. No caso do nó ter um único
filho a mudança na árvore também é simples significa mover o nó filho daquele será removido
uma posição para cima como está ilustrado na Figura remove1, onde o nó com o valor 6 é
removido.
O caso mais complexo é o do nó com dois filhos. Neste caso devemos procurar o sucessor s (ou
antecessor) do nó deverá ocupar este lugar. Este nó (sucessor) é um descendente que está na sub
árvore da direita do nó e corresponde ao nó mais à esquerda desta árvore. Ele não tem filhos à
esquerda e a sua árvore à direita pode ser movida para o lugar de s. A Figura remove2 ilustra o
caso de remoção do nó com o valor 12. Observe que o nó 13 (sucessor) assumiu o lugar do nó 12.
Figura remove0: Removendo nó (8) sem filhos.
Figura remov1: Removendo nó (6) com um
filho.
Figura remov2: Removendo nó (12) com dois
filhos.