Ar Vores

UFGD / FACET — Prof. Wellington Lima dos Santos — Algoritmos e Estruturas de Dados II

ÁRVORES 1 Definição

Uma árvore T (do inglês tree) é um conjunto finito de N estruturas elementares, chamados

nodos, tal que se N > 0, então:

1. Existe um nodo especial, chamado raiz da árvore;

2. Os restantes N-1 nodos estão particionados em M conjuntos disjuntos: S1, S2, ......, SM, onde

cada um destes conjuntos é também uma árvore. As árvores S1, S2, ......, SM são chamadas

sub-árvores de T.

Árvores são estruturas de dados extremamente úteis em muitas aplicações. Assim como as

listas lineares, árvores são estruturas de dados que caracterizam uma relação entre os dados que a

compõem. No caso de árvores, a relação existente entre os nodos é uma relação de hierarquia, onde

um conjunto de nodos é hierarquicamente subordinado a outro.

2 Formas de Representação Gráfica 2.1 Grafo (representação mais utilizada)

2.2 Diagrama de Venn (ou digrama de inclusão ou conjuntos aninhados)

2.3 Identação

A B D E F C G 2.4 Parênteses Aninhados

(A (B(D, E, F), C(G)))


3 Terminologia

• A raiz de uma árvore é chamada de pai de suas sub-árvores.

• Nodos com o mesmo pai são denominados irmãos.

• O grau de um nodo é por definição o número de sub-árvores do nodo.

• O grau da árvore é grau máximo entre todos os nodos.

• Um nodo folha ou terminal tem grau zero, ou seja, não tem sub-árvores.

• O nodo raiz tem nível um, os nodos filhos da raiz têm nível 2 e, assim, sucessivamente.

• A altura ou profundidade de uma árvore é igual ao número de níveis desta árvore. Um

nodo folha tem altura unitária.

• Um conjunto de árvores disjuntas forma uma floresta. Assim, se o nodo raiz de uma

árvore for eliminado, suas sub-árvores formarão uma floresta. Inversamente, se raízes

das árvores que formam uma floresta forem unidas através um nodo adicional, uma

árvore será formada.

4 Árvores Binárias Árvores Binárias são estruturas do tipo árvore, onde cada nodo pode ter no máximo duas

sub-árvores, ou seja, o grau de cada nodo pode ser 0, 1 ou 2. Convencionou-se denominar as sub-

árvores de um nodo em sub-árvore esquerda (E) e sub-árvore direita (D). As árvores binárias

combinam as vantagens de duas outras estruturas de dados: vetor ordenado e lista encadeada.

Assim, permitem pesquisas binárias (como os vetores ordenados) e as mesmas facilidades de

inserção e de remoção de itens que as listas encadeadas proporcionam.

4.1 Árvore Estritamente Binária

Uma árvore estritamente binária é aquela em que cada nó tem 0 ou 2 sub-árvores, ou seja,

nenhum nodo tem “filho único”.

4.2 Árvore Binária Cheia

Uma árvore binária cheia é aquela cujos nodos, exceto os do último nível, tem exatamente

duas sub-árvores. O número de nodos de uma árvore binária cheia é 2h-1, em que h é a sua altura.

4.3 Árvore Binária Completa

Uma árvore completa é uma árvore estritamente binária (grau 0 ou 2), na qual seus nodos

folhas podem estar apenas no último e no penúltimo níveis. Das definições anteriores, tem-se que

toda árvore cheia é também completa e estritamente binária.


4.4 Árvore Binária de Pesquisa (ou Árvore Binária Ordenada)

É aquela em que todo nodo tem chave maior que a chave dos seus descendentes à esquerda

e menor que a chave dos seus descendentes à direita. Conseqüentemente, uma árvore binária de

pesquisa só admite uma ocorrência de cada chave.

4

2

1 3

8

65 7

9

C

B

A

E

D GF �

4.5 Árvore Binária Balanceada (ou Árvore AVL)

Uma árvore binária é considerada balanceada quando, para cada nó, as alturas de suas sub-

árvores esquerda e direita diferem de no máximo uma unidade. Essa diferença é chamada fator de

balanceamento do nodo. Cada nodo de uma árvore balanceada pode ter fator de balanceamento

entre -1 e 1. Idealmente, uma árvore binária é perfeitamente balanceada quando todos os seus nodos

têm fatores de balanceamento nulos, como acontece nas árvores binárias cheias. A denominação

AVL é uma homenagem aos dois matemáticos russos Adelson-Velskii e Landis, que em 1962

sugeriram este conceito e propuseram algoritmos para manter o balanceamento de uma árvore

binária. A altura de uma árvore AVL é no máximo 45% maior que a altura de uma árvore binária

perfeitamente balanceada, considerando o mesmo número de nodos.

4.6 Percurso (ou travessia) em Árvores Binárias

Percorrer uma árvore binária “visitando” cada nodo uma única vez gera uma seqüência linear

de nodos, cuja ordem depende de como a árvore foi percorrida. As três formas ou ordens de percurso

mais importantes são: pré-ordem, in-ordem e pós-ordem. O que define o prefixo do nome do

percurso é ordem em que a raiz é visitada, sendo que a sub-árvore esquerda é sempre visitada antes

da sub-árvore direita. Um quarto percurso importante, porém menos usual é o percurso em nível.


4.6.1 Percurso em Pré-Ordem (R, E, D)

Nesta ordem de percurso, visita-se:

• a raiz;

• a sub-árvore esquerda, em pré-ordem; e

• a sub-árvore direita, em pré-ordem.

4.6.2 Percurso In-Ordem (E, R, D)


• a sub-árvore esquerda, in-ordem;

• a raiz; e

• sub-árvore direita, em in-ordem.

4.6.3 Percurso em Pós-Ordem (E, D, R)


• a sub-árvore esquerda, em pós-ordem;

• a sub-árvore direita, em pós-ordem; e

• a raiz.

4.6.4 Percurso em Nível

No percurso em nível, a árvore é percorrida no sentido de cima para baixo e da esquerda

para direita, ou seja, no sentido da escrita ocidental. É o percurso mais fácil de ser compreendido,

porém o mais difícil de ser programado, porque é necessário utilizar uma fila em um algoritmo

iterativo.

4.6.5 Exemplos dos Percursos

Árvore Percurso Sequência de Nodos

pré-ordem 4 2 1 3 6 5 7

in-ordem 1 2 3 4 5 6 7

pós-ordem 1 3 2 5 7 6 4

4

2

1 3

6

5 7 em nível 4 2 6 1 3 5 7

pré-ordem + / - A B C * D ^ E F

in-ordem (A - B) / C + D * E ^ F

pós-ordem A B - C / D E F ^ * +

+

/

-A B

C

*

D ^E F em nível + / * - C D ^ A B E F

(matematicamente inconsistente!)


Observação: Note que, em se tratando de árvores binárias representando expressões matemáticas,

foi necessário acrescentar parênteses na expressão com notação in-fixa (que é a usual

e corresponde ao percurso in-ordem). Já as notações pré-fixa e pós-fixa não

necessitam de parênteses, qualquer que seja a complexidade da expressão. A notação

pós-fixa, também chamada de notação polonesa reversa ou RPN, é utilizada em

muitas calculadoras científicas como aquelas da Hewlett Packard™.

4.7 Estrutura de Dados e Algoritmos Básicos para Árvores Binárias

A estrutura de dados para uma árvore binária é uma estrutura dinâmica, assim como as listas

encadeadas, onde cada nodo é representado por um registro contendo: 1) um campo chave do tipo

inteiro, string, etc. 2) um ponteiro para as sub-árvores esquerda e direita; e 3) outros campos de

dados, de acordo com o problema de aplicação.

ArvBin = ^TNodo

TNodo = ponteiro para registro Chave : inteiro {caracter, string, etc.} E : ArvBin {Ponteiro para a sub-árvore esquerda} D : ArvBin {Ponteiro para a sub-árvore direita} {outros campos} fim

4.7.1 Percursos (ou travessia) em Árvores Binárias

Nos algoritmos abaixo, o procedimento “Processa” executa qualquer ação sobre o nodo,

como por exemplo: imprimir o valor da sua chave, recuperar o conteúdo de um dado campo, etc.

• Algoritmo para percurso em pré-ordem

procedimento Pre_ordem(T : ArvBin) inicio se T ≠ nulo então inicio Processa(T) {imprime o valor da chave, por exemplo} Pre_ordem(T^.E) Pre_ordem(T^.D) fim fim

• Algoritmo para percurso in-ordem procedimento In_ordem(T : ArvBin) inicio se T ≠ nulo então inicio In_ordem(T^.E) Processa(T) In_ordem(T^.D) fim

fim


• Algoritmo para percurso em pós-ordem procedimento Pos_ordem(T : ArvBin) inicio se T ≠ nulo então inicio Pos_ordem(T^.E) Pos_ordem(T^.D) Processa(T) fim fim

• Algoritmo para percurso em nível procedimento EmNível(T: ArvBin) declare F : Fila início se T ≠ nulo então início InicializaFila(F) {cria uma fila fazia} InsereNaFila(F, T) {insere a raiz na fila} enquanto FilaNãoVazia(F) faça {enquanto houver um nodo na fila} início T ← RetiraDaFila(F) {T ← o primeiro da fila} Processa(T) se T^.E ≠ nulo então InsereNaFila(F, T^.E) {insere T^.E no final da fila} se T^.D ≠ nulo então InsereNaFila(F, T^.D) {insere T^.D no final da fila} fim FinalizaFila(F) {“destroi” a fila} fim fim

4.7.1 Algoritmo para Gerar uma Árvore Binária de Altura Mínima

Para gerar uma árvore binária de altura h mínima, a partir de N entradas, basta “criar” o maior

número possível de nodos em cada nível, exceto no último, caso N < 2h-1 (árvore incompleta). Isto

pode ser conseguido distribuindo-se eqüitativamente os registros entre as sub-bárvores esquerda e

direita de cada nodo criado.

função ArvBin_AltMin(N: integer): ArvBin variáveis Ne, Nd : inteiro Nodo : ArbVin início se N = 0 então retorne nulo senão início Ne ← N div 2 {metade para a sub-árvore esquerda} Nd ← N - Ne – 1 Nodo ← CriaNodo {aloca memória para um novo nodo} Nodo.Chave ← LeiaChave {lê a próxima chave} Nodo^.E ← ArvBin_AltMin(Ne) Nodo^.D ← ArvBin_AltMin(Nd) retorne Nodo fim fim


4.7.2 “Destruição” (liberação dos recursos alocados) de uma Árvore Binária

procedimento DestroiArvBin(PorRef T: ArvBin) início se T ≠ nil então início DestroiArvBin(T^.L) DestroiArvBin(T^.R) Dispose(T) T ← nil fim fim

4.7.3 Altura de uma Árvore Binária

função AltArvBin(T: ArvBin): inteiro declare hL, hR: inteiro início se T ≠ nulo então início hL ← AltArvBin(T^.L) hR ← AltArvBin(T^.R) se hL > hR então result ← 1 + hL senão result ← 1 + hR fim senão result ← 0 fim

4.8 Operações Básicas em Árvores Binárias de Pesquisa

4.8.1 Inserção

A inserção de um registro com chave K em uma árvore binária de pesquisa é uma operação

simples, cujo maior trabalho consiste em determinar a posição em que o novo nodo ocupará na

árvore, cuja raiz é apontada pelo ponteiro T. Se T for nulo, então a árvore está vazia e o novo nodo se

tornará a raiz da árvore, ou seja, o ponteiro T passará apontar para esse nodo. Se T não for nulo

então três situações podem ocorrer:

1 A chave K é menor que a chave da raiz T, logo o novo nodo só poderá ser inserido na sub-árvore

esquerda de T. Compara-se novamente K com a raiz da sub-árvore esquerda e as mesmas três

situações podem ocorrer.

2. A chave K é igual à chave da raiz T e, consequentemente, um novo nodo não poderá ser inserido,

já que uma árvore binária de pesquisa só admite uma ocorrência de cada chave.

3. A chave K é maior do que a chave da raiz T, então o novo nodo terá que ser inserido na sub-

árvore direita de T. Neste caso, K é comparada com a raiz da sub-árvore direita, sendo possíveis

as três situações descritas.

A não ser que ocorra a situação 2 (chave já existente), o processo é repetido recursivamente

até que se encontre uma sub-árvore vazia (ponteiro nulo). O novo nodo será a raiz desta sub-árvore

vazia, ou seja, os nodos sempre são inseridos como nodos folhas. Eis o algoritmo:


função Ins_ArvBinPesq(PorRef T : ArvBin; K : Inteiro) : lógico início se T ≠ nulo então início se K < T^.Chave então retorne Ins_ArvBinPesq(T^.E, K) senão se K = T^.Chave então retorne falso senão retorne Ins_ArvBinPesq(T^.D, K) fim senão início T ← CriaNodo {aloca memória para um novo nodo} T^.Chave ← K retorne verdadeiro fim fim

4.8.2 Pesquisa

Pesquisar uma chave K em uma árvore binária de pesquisa apontada por T é uma operação

ainda mais simples, se comparada à operação de inserção. Existem quatro casos possíveis:

1. T é nulo e a pesquisa é encerrada sem sucesso, pois não há como continuar a pesquisa

em uma árvore vazia.

2. A chave K coincide com a chave de T, então a pesquisa é concluída com sucesso.

3. A chave K é menor que a chave de T, portanto a pesquisa deve prosseguir na sub-árvore

esquerda de T.

4. A chave K é maior que a chave de T, logo a chave deve ser pesquisada na sub-árvore

direita de T.

No algoritmo abaixo, a função retorna um ponteiro para nodo que contém a chave pesquisada

K, caso seja encontrada; caso contrário, a função retorna um ponteiro nulo.

função Pesq_ArvBinPesq(T : ArvBin; K : inteiro) : ArvBin início se T ≠ nulo então início se K = T^.Chave então {pesquisa com sucesso} retorne T senão se K < T^.Chave então {pesquisa na sub-árv esquerda} retorne Pesq_ArvBinPesq(T^.E, K) senão {pesquisa na sub-árv. direita} retorne Pesq_ArvBinPesq(T^.D, K) fim senão {pesquisa sem sucesso} retorne nulo fim


Como a cada comparação desce-se um nível na estrutura da árvore, o número máximo de

comparações é igual à altura (número de níveis) da árvore. Assim, é interessante que a árvore binária

de pesquisa tenha altura mínima: 1 + Piso(Log2N), em que Piso retorna o maior inteiro menor ou igual

ao seu argumento. Portanto, a eficiência da pesquisa em uma árvore binária de pesquisa balanceada

tem ordem de complexidade O(Log N).

4.8.3 Exclusão

A exclusão de um registro de chave K em uma árvore binária de pesquisa é uma operação

um pouco mais trabalhosa que as operações de inserção e de pesquisa. Esta operação

aparentemente complexa torna-se mais simples quando os possíveis casos são analisados. Suponha

que o nodo a ser removido seja a raiz, apontada por T. Existem três casos possíveis:

1. T é um nodo folha (não tem filhos): basta "destruir" T e fazê-lo apontar para nulo.

2. T possui apenas um filho: basta "destruir" T e fazê-lo apontar para o seu nodo filho.

3. T possui dois nodos filhos: para manter a árvore ordenada, há duas alternativas:

• substituir o conteúdo de T pelo conteúdo do nodo mais à direita (maior chave) da sub-

árvore esquerda de T. Este conteúdo inclui a chave e todos os demais campos, exceto

os ponteiros para as sub-árvores esquerda e direita.

• substituir o conteúdo de T pelo conteúdo do nodo mais à esquerda (menor chave) da

sub-árvore direita de T.

No terceiro caso, o nodo efetivamente removido (memória ou outros recursos liberados) é o

nodo mais à direita da sub-árvore esquerda ou o nodo mais à esquerda da sub-árvore direita. Ambos

têm no máximo um descendente, pois se tivessem dois não poderiam ser considerados como

extremos. A seguir, é apresentado um algoritmo que utiliza a primeira alternativa. Ele faz uso da

função Antecessor, a qual percorre o extremo direito da sub-árvore esquerda de T, em busca do nodo

mais à direita, ou de maior chave. Ao encontrar o ponteiro X para este nodo, esta função modifica

(por referência) o valor de X, fazendo-o apontar para a sua sub-ávore esquerda, a qual pode existir ou

não.

função Antecessor(PorRef X : ArvBin) : ArvBin declare r : ArvBin início se X^.D = nulo então {X é o nodo mais extremo, à direita} início r ← X X ← X^.E retorne r fim senão {desce mais um nível, pela direita} retorne Antecessor(X^.D) fim


função ExcluiNodo_ArvBinPesq(PorRef T: ArvBin; K: inteiro) : lógico declare N: ArvBin início se T = nulo então {Abandona sem fazer nada} retorne falso se K = T^.Chave então {chave encontrada!} início N ← T se T^.E = nulo então {T tem apenas a sub-árvore direita} T ← T^.D senão se T^.D = nulo então {T tem apenas a sub-árvore esquerda} T ← T^.E senão {T tem as duas sub-árvores} início N ← Antecessor(T^.E) {acha o nodo mais à direita em T^.E} T^.K ← N^.K {substitui o conteúdo de T pelo de N} fim destroi(N) {libera os recursos alocados para N} retorne verdadeiro fim senão se K < T^.Chave então retorne ExcluiNodo_ArvBinPesq(T^.E, K) senão retorne ExcluiNodo_ArvBinPesq(T^.D, K) fim


EXERCÍCIOS

1) Dada uma árvore binária, apontada por T, implemente em Portugol funções para retornar:

a) A soma dos valores de todas as chaves.

b) Um ponteiro para nodo que possui a maior chave.

c) A altura da ávore.

d) O número de nodos folhas.

e) O nível de um nodo N.

f) O nodo pai de um nodo N.

g) Verdadeiro se T for uma árvore binária de pesquisa, ou falso, caso contraio.

2) Implemente em Portugol três algoritmos para percorrer uma árvore binária em: pré-ordem (R, E,

D); in-ordem (E, R, D); e pós-ordem (E, D, R).

3) Considere a árvore binária abaixo:

A

B

D

H

E

I

L

C

F G

J K

a) Qual a altura da árvore?

b) Quantos nodos folhas a árvore possui?

c) A árvore é do tipo AVL? Justifique.

d) Como seriam listadas as chaves nos percursos em pré-ordem, in-ordem e pós-ordem?

e) Represente a árvore utilizando parênteses aninhados e Diagrama de Venn.

4) Uma árvore binária é denominada estritamente binária quando nenhum dos seus nodos possui

apenas uma sub-árvore. Em outras palavras, cada nodo possui duas sub-árvores ou é um nodo

folha. Implemente em Portugol uma função que receba um ponteiro T para uma árvore binária e

retorne verdadeiro ou falso conforme uma árvore binária seja ou não seja estritamente binária.

5) Em uma árvore binária de pesquisa (ou árvore ordenada), todo nodo tem chave maior que a

chave da sua sub-árvore esquerda e menor que a chave da sua sub-árvore direita. Implemente em

Portugol uma função que retorne verdadeiro ou falso caso uma árvore seja ou não seja uma

árvore de pesquisa.


6) Uma árvore binária de pesquisa é denominada AVL ou balanceada quando as alturas das sub-

árvores esquerda e direita de qualquer nodo diferem de no máximo uma unidade. Implemente em

Portugol uma função que retorne verdadeiro ou falso caso uma árvore binária seja ou não seja

uma árvore balanceada.

7) Porque o desbalanceamento de uma árvore binária de pesquisa afeta negativamente a eficiência

da pesquisa de dados nesta estrutura? Complemente sua resposta através de um esquema.

8) Construa uma árvore de pesquisa, inserindo um a um cada letra do seu nome completo, até que a

árvore tenha exatamente 8 nodos; lembre-se que só permitida uma ocorrência de cada letra. Com

base nesta árvore, pergunta-se:

a) Qual é a sua altura?

b) Quantos nodos internos (aqueles que não são folhas ou terminais)?

c) Quantos e quais são os nodos desbalanceados?

d) Exclua da árvore o nodo que possui a terceira consoante do seu nome.

9) Em uma árvore binária de pesquisa, a inserção de N registros cujas chaves estão em ordem

crescente ou decrescente conduzem a uma árvore degenerada de altura N, na qual a pesquisa

tem a mesma eficiência de uma lista encadeada, O(n). Implemente um algoritmo para gerar uma

árvore balanceada, a partir de um vetor de N registros ordenados segundo suas chaves.

Sugestão: Insira o registro central do vetor; agora considere uma partição (subvetor) anterior e

outra posterior a esse registro; repita recursivamente os procedimentos anteriores até que todos

os registros sejam inseridos.

10) Implemente uma função em Portugol que retorne verdadeiro se duas árvores binárias T1 e T2 têm

a mesma representação gráfica, ou falso, caso contrário.

Documents

Ar Vores