Estrutura de dados II - conteúdo de arvore

Prévia do material em texto

Estruturas de Dados II 
Prof.: Jones F. Giacon 
1 
ÁRVORE (TREE) 
 
 Estrutura hierárquica (+ complexa) 
 
Conceito: 
 
 Uma árvore “A” é um conjunto finito de de “n” nodos talque se N > 0 então: 
 
1) Existe um nodo especial chamado raiz árvore. 
2) Os restantes N-1 nodos estão particionados em “m” conjuntos disjuntos A1, A2, ..., An cada 
um dos quais é por sua vez uma árvore. Estas árvores A1, A2, ..., An são chamadas de sub-
árvores da raiz. 
 
 
Representação: 
 
a) Diagrama de Venn 
 
 
A 
 B C D 
 
 
 
 
 
 
 
 
b) Por Grafos: 
 A {RAIZ (ROOT) } acessa todos os nodos 
 
 
 A1 B C A2 D A3 
 
 
 E F G H P 
 
 
 
 I J K L M N O 
 
Árvore Genérica (filhos de m > 0) 
 
Obs.: Se cortar a Raiz A, ficariam 3 subconjuntos: A1,A2,A3. 
 
E 
I 
J 
K 
F H 
L 
M 
N 
O 
P G 
C D 
 
Estruturas de Dados II 
Prof.: Jones F. Giacon 
2 
c) Paragrafação: 
 
 A 
 B 
 E 
 I 
 J 
 K 
 F 
 L 
 C 
 G 
 H 
 M 
 N 
 O 
 D 
P 
 
 Mais a esquerda  representam a raiz 
 Mais a direita  subconjunto 
 
Conceitos: 
 
 Um nodo raiz é dito ser um nodo pai das suas sub-árvores, cujos nodos por sua vez são os 
nodos filhos do nodo raiz. 
 
 X  nodo pai 
 
 
 K Y Z  nodo filho 
 
 3 filhos  Grau 3 
 
 Nodo Irmão: possuem o mesmo pai 
 
 Grau de 1 nodo: é o nº de sub-árvores que o nodo possui: 
 se Grau = 0  então o nodo é chamado externo terminal ou folha (nodos que 
não tem filho) 
 se Grau > 0  então o nodo é chamado interno 
 
 Nível de 1 nodo : é o nº de linhas (arestas) que ligam o nodo ao nodo raiz. 
 Nível do nodo raiz = 0 
  no desenho acima, qual o nível de k 
 
 Altura de 1 árvore : é definida pelo nível mais alto da árvore. 
 
 Floresta : conjunto (finito) de árvores disjuntas. 
 
Estruturas de Dados II 
Prof.: Jones F. Giacon 
3 
 Árvore Ordenada : aquela na qual a ordem das sub-árvores A1,A2,...,An é importante na 
definição. 
 
 Árvore Orientada : Aquela na qual a ordem é irrelevante 
 EX: 
 A1 A2 
 A A 
 
 
 X Y Z Y Z X 
 
 Se A1 e A2 são árvores ordenadas então A1 <> A2 
 Se A1 e A2 sÃo árvores orientadas então A1 = A2 (não importa a ordem) 
 
 Caminho (path) : dado um conjunto de nodos n1,n2,...,nk, será caminho de n1 até nk, se ni 
é pai de ni+1 p/ i=1,2,...,k-1. Dado um nó “S” qualquer de uma árvore existe um único 
caminho da raiz até o nodo “S”. 
 
Ex: na representação por grafo: 
  caminho até F A B C incluo a raiz e 
  caminho até MA C H M o próprio elemento 
 
Tipos: 
a) Árvore genérica  qualquer nodo pode ter m >= 0 filhos; 
b) Árvore binária de Knuth  qualquer nodo pode ter no máximo 2 filhos (0,1,2) 
c) Árvore estritamente binária  qualquer nodo deve ter 0 ou 2 filhos (0 ou 2) 
 
b) 1 
 
 
 2 3 
 
4 5 6 
 
 7 
 
Ex.: Rep. Expressão aritmética 
 
 + 
 
 
1 * 
 
 2 3 
 
 
c ) 1 
 
 
 2 3 
 
 4 5 
 
Estruturas de Dados II 
Prof.: Jones F. Giacon 
4 
REPRESENTAÇÃO (alocação) DE ÁRVORES EM MEMÓRIA 
 
Ex.: A 
 
 
 B E 
 
 
C D F G H 
 
  
 
 nodo 
 
 . . . . . 
A 2 B 2 C 0 D 0 E 3 F 0 G 0 H 0 
 
 . . . . . . 
 
 grau (nº de filhos) 
 
 Como colocar? A tem 2 filhos, então os próximos nodos sÃo filhos de A. Um deles é B, mas 
B tem 2 filhos, então os próximos nodos sÃo filhos de B, que são C e D, como eles não tem 
filhos, então o próximo nodo é o outro filho de A, que é E. 
 
A) Por Contiguidade: 
 
  dificuldade para operações de manipulação: 
 - inserção do nodo 
 - remoção do nodo 
 - localização do nodo 
  adequada para armazenamento físico permanente (em disco/fita magnéticas) de uma 
árvore representada por encadeamento. 
 
B) Por Encadeamento (lista de lista) 
 
 A 
 
 ^ 
 
 B E 
 
 ^ ^ 
 
 C ^ D ^ F ^ G ^ H ^ 
 
Estruturas de Dados II 
Prof.: Jones F. Giacon 
5 
Pascal: 
 
 Type 
Aponta_nodo = ^Nodo; 
 Aponta_Aponta = ^Aponta 
 Nodo = RECORD 
 Dado : Informação 
 Filhos : Aponta_Aponta 
 End; 
 
 Aponta = RECORD 
 Filho : Aponta_Nodo 
 Prox : Aponta_Aponta 
 End; 
 
 A ^ 
 
 
 B ^ E 
 
 
 C ^ ^ ^ D ^ ^ ^ F ^ ^ ^ G ^ ^ ^ H ^ ^ ^ 
 
8 nodos x 4 campos = 32 campos (cada campo +/- 1 byte) 
17 campos não utilizados (+ de 50% da estrutura está sendo desperdiçado) 
Não vale a pena trabalhar c/ esta forma em termos de estrutura 
Solução: - Transformar a árvore genérica em uma árvore binária representativa. 
 
 Todo nodo deve possuir um campo para a informação e tantos campos para referenciar os 
filhos, normalmente o grau máximo da árvore. 
Quanto maior o grau, maior o desperdício. 
 
Árvore Binária (nodo): 
 
 max. 2 filhos 
 
 
 filho dado filho 
 esq dir 
 
Pascal: 
 Aponta_Nodo = ^Nodo 
 Nodo = RECORD 
 Esq : Aponta_Nodo; 
 Dado : Informação; 
 Dir : Aponta_Nodo; 
 End; 
 
Estruturas de Dados II 
Prof.: Jones F. Giacon 
6 
Transformação de Árvore Genérica em Árvore Binária Representativa 
 
1) A raiz da árvore genérica será também a raiz da árvore binária 
2) Manter a ligação de cada nodo com seu filho mais à esquerda, se o nodo possuir apenas um 
nodo este é o filho a esquerda (esta ligação mostrará o filho a esquerda na árvore binária). 
3) Formar uma nova ligação de cada nodo com seu irmão à direita (esta ligação mostrará o filho 
a direita na árvore binária). 
4) As ligações restantes são desconsideradas. 
 
Ex.: A 2º PASSO 
 
 B E 3º PASSO 
 
 C D F G H 4º PASSO 
 
 A 
 
 
 B 
 
 E  Filhos: 1º a esquerda e depois 
 C a direita 
 Ex.: filhos de A:  1º esquerda (B) 
 F  2º direita (E) 
 D  irmão : a direita 
 G 
 
 H 
 
Árvore Binária em Memória 
 
 A ^ 
 
 B 
 
 
^ C E ^ Pai  nodo apontado a esquerda 
 
 Ex: pai de H  E 
 ^ D ^ ^ F 
 
 ^ G 
 
8 nodos x 3 campos = 24 campos 
 ^ H ^ 
 9 campos desperdiçados 
 
 
Estruturas de Dados II 
Prof.: Jones F. Giacon 
7 
Caminhamento em Árvores Binárias (percorre todos os elementos) 
 
 Caminhamento  ordem de processamento dos nodos de forma que não seja 
necessário passar 2 ou mais vezes pelo mesmo nodo. 
 percorrer todos os nodos da árvore numa ordem pré- determinada 
processando cada nodo apenas uma vez. 
 
A) Pré-ordem (pré-fixada) 
  Visita (processa informações) do nodo {Visita : imprime} 
  Percorre subárvore à esquerda no nodo ou pré-ordem 
  Percorre subárvore à direita do nodo ou pré-ordem 
 
B) In-Ordem (Infixada) 
  Percorre subárvore à esquerda do nodo em In-Ordem 
  Visita (processa informações) do nodo 
  Percorre subárvore à direita do nodo em In-Ordem 
 
C) Pos-Ordem (Pós-Fixada) 
  Percorre subárvore à esquerda do nodo em Pós-Ordem 
 Percorre subárvore à direita do nodo em Pós-Ordem 
  Visita (processa informação) do nodo 
 
Ex.: 1) A Pré-Ordem : A B C 
 In-Ordem : B A C 
 Pos-Ordem : B C A 
 B C 
 
Começando pela raiz : Pré-Ordem  Visita (imprime o conteúdo), percorre a esquerda, então 
encontra o nodo B, ele é diferente de A, então tenho que começar novamente, ou seja, visita o 
nodo B, percorre a esquerda (não possui nada) então percorre a direita (não possui nada 
também), assim termina no nodo B. Então volta ao nodo A e percorre a direita. Encontro o 
nodo C. Devo visitá-lo, percorrer a esquerda (nada) e a direita (nada). Assim termina a Pré-
Ordem. 
 
2) A Pré : AB C D E F G 
 
 B E In : C B D A F G E 
 
C D F Pos : C D B G F E A 
 
 G 
 
 
 
 
 
Estruturas de Dados II 
Prof.: Jones F. Giacon 
8 
Procedimento Pré_Ordem (nodo) { s/ recursividade } 
{escreve o caminhamento em Pré-Ordem a partir de um nodo da árvore raiz} 
Se (Nodo <> NIL) {raiz não vazia} 
Então Inicio 
 Cria_pilha(Pilha) 
 Empilha (Pilha,Nodo) 
 Enquanto (Não Pilha_Vazia (Pilha)) 
 Faça Inicio 
 Aux  Consulta_Pilha (Pilha) 
 Desempilha (Pilha) 
 Visita (Aux) 
 Se (Aux.Dir <> NIL) 
 Entao Empilha (Pilha, Aux.Dir) 
 Se (Aux.Esq <> NIL) 
 Entao Empilha (Pilha, Aux.Esq) 
 Fim 
 Destroi_Pilha (Pilha) 
 Fim 
 
 
 
 
 
 
 
Pré: A B C D E 
In : B C A E D 
Pos: C B E D A 
 
Procedimento Pré_Ordem (Nodo) { c/ recursividade } 
Se (Nodo <> Nil) 
Entao Inicio 
 Visita (Nodo) 
 Pre_Ordem (Nodo.Esq) 
 Pre_Ordem (Nodo.Dir) 
 Fim 
 
Procedimento In_Ordem (Nodo) { c/ recursividade } 
Se (Nodo <> NIL) 
Entao Inicio 
In_Ordem (Nodo.Esq) 
 Visita (Nodo) 
 In_Ordem (Nodo.Dir) 
 Fim 
. . . 
 
E 
C 
B 
D 
A Usando Pilha 
 A 
 
B D 
 
 C E 
 
Estruturas de Dados II 
Prof.: Jones F. Giacon 
9 
TIPOS DE ÁRVORES 
 
 1º Árvore binária de busca (ou de pesquisa) 
 Definição: Uma árvore binária é uma árvore binária de busca se para cada nó N da 
árvore for verdade que SEM <= N <= SDN , isto é, todos os nodos da sub-árvore à esquerda 
precedem a raiz e a raiz precede todos os nodos da sub-árvore à direita. 
 
SENSDN: Sub-árvore à esquerda/direita de N. 
 
 10 
 
 7 15 
 
 5 9 13 17 
 
 19 
Nº acessos : log2 N 
 
 5 7 9 10 13 15 17 19 
 
Procedimento Cria_Arvore_Binaria (Raiz) 
 Raiz  NIL 
 
Função Arvore_Vazia (Raiz) : Lógico 
 Logico  (Raiz = NIL) 
 
Procedimento Destroi_Arvore_Binaria (Raiz) 
 Se (Não_Arvore_Vazia (Raiz)) 
 Entao Inicio 
 Pos_Ordem (Raiz) visita (nodo) na Pos-Ordem seria desaloque (nodo) } 
 Raiz  NIL 
 Fim 
 
Funcao Consulta (Nodo, Valor, Aux) : Lógico 
{ Retorna verdadeiro, se “valor” existe na árvore de raiz nodo; caso contrário, retorna falso } 
Se (Arvore_vazia (Nodo)) 
Entao Logico  Falso 
Senao Inicio 
 Aux  Nodo 
 Logico  Falso 
 Enquanto (Não Lógico) E (Aux <> NIL) 
 Faça Se (Valor = Aux.Dado) 
 Entao Logico  Verdadeiro 
 Senao Se (Valor < Aux.Dado) 
 Entao Aux  Aux.Esq 
 Senao Aux  Aux.Dir 
 Fim 
 
Estruturas de Dados II 
Prof.: Jones F. Giacon 
10 
 
Funcao Encontra_Pai (Nodo, Valor) : Aux_Pai 
{ Caso valor exista na árvore de raiz “nodo”, retorna o pai do nodo; caso o nodo encontrado 
for a raiz, então retorna NIL, se não existir, retorna o possível pai do nodo} 
Se (Arvore_Vazia (Nodo)) 
Entao Aux_Pai  NIL 
Senao Inicio 
 Se (Valor = Nodo.Dado) {nodo que possui o valor é a raiz} 
 Entao Aux_Pai  NIL 
 Senao Inicio 
 Aux  Nodo 
 Achou  Falso 
 Enquanto ((Não Achou) E (Aux <> NIL)) 
 Faça Inicio 
 Aux.Pai  Aux 
 Se (Valor < Aux.Dado) 
 Entao Aux  Aux.Esq 
 Senao Aux  Aux.Dir 
 Se (Aux <> NIL) E (Aux.Dado = Valor) 
 Entao Achou  Verdadeiro 
 Fim 
 Fim 
 Fim 
 
Procedimento Insere (Nodo, Valor) 
Se (Arvore_Vazia (Nodo)) 
Entao Inicio 
 Aloque (Nodo) 
 Nodo.Esq  NIL 
 Nodo.Dado  Valor 
 Nodo.Dir  NIL 
 Fim 
Senao Se (Consulta (Nodo, Valor, Aux)) 
 Entao ERRO { valor já existe } 
 Senao Inicio 
 Aloque (Novo) 
 Novo.Esq  NIL 
 Novo.Dado  Valor 
 Novo.Dir  NIL 
 Pai  Encontra_Pai (Nodo, Valor) 
 Se (Valor < Pai.Dado) 
 Entao Pai.Esq  Novo 
 Senao Pai.Dir  Novo 
 Fim 
 
 
Estruturas de Dados II 
Prof.: Jones F. Giacon 
11 
REMOÇÃO: 
 
 Nodo Folha: - acerta subárvore do pai 
- remove a folha 
 
 Nodo com uma subárvore: - acerta o pai com a subárvore restante 
- remove o nodo 
 
 Nodo com duas subárvores: - encontrar o predecessor / sucessor 
- substituir o nodo pelo predecessor / sucessor 
- remove o predecessor / sucessor 
 
Procedimento Remove (Nodo, Valor) 
Se (Arvore_Vazia (Nodo)) 
Entao ERRO1 
Senao Inicio 
 Se (Não Consulta (Nodo, Valor, Aux)) 
 Entao ERRO2 
 Senao Inicio 
 Se ((Aux.Esq = NIL) E (Aux.Dir = NIL)) {nodo folha} 
 Entao Inicio 
 Pai  Encontra_Pai (Nodo,Valor) {achou o pai} 
 Se (Pai = NIL) {nodo a remover é a raiz} 
 Entao Nodo  NIL 
 Senao Se (Valor < Pai.Dado) 
 Entao Pai.Esq  NIL 
 Senao Pai.Dir  NIL 
 Fim 
 Senao Se (aux.Esq = NIL) {nodo c/ subárvore à direita} 
 Entao Inicio 
 Pai  Encontra_Pai (Nodo,Valor) 
 Se (Pai = NIL){nodo a remover é a raiz} 
 Entao Nodo  Aux.Dir 
 Senao Se (Valor < Pai.Dado) 
 Entao Pai.Esq  Aux.Dir 
 Senao Pai.Dir  Aux.Dir 
 Fim 
 Senao Se (Aux.Dir = NIL) {nodo c/ subárvore a esquerda} 
 Entao Inicio 
Pai  Encontra_Pai (nodo,valor) 
 Se (Pai = NIL) {nodo a remover é a raiz} 
 Entao Raiz  Aux.Esq 
 Senao Se (Valor < Pai.dado) 
 Entao Pai.EsqAux.Esq 
 Senao Pai.DirAux.Esq 
 Fim 
 
Estruturas de Dados II 
Prof.: Jones F. Giacon 
12 
 Senao Inicio 
 Pred  Predecessor (Aux) {nodo com 2 subárvores} 
 Temp  Pred.Dado 
 Remove (Aux,Temp) 
 Aux.Dado  Temp 
 Aux  NIL 
 Fim 
 Se (Aux <> NIL) 
 Entao DESALOQUE (Aux) 
 Fim 
Fim 
 
Função Predecessor (Nodo) : Aux_Pred 
 Se (Nodo = NIL) 
 Entao Aux  NIL 
 Senao Inicio 
 Aux  Nodo.Esq 
 Enquanto (Aux.Dir <> NIL) 
 Faça Aux  Aux.Dir 
 Fim 
 Aux_Pred  Aux 
 
Árvore Amarrada (ou costurada - Alinhavadas (“Threaded Trees”) 
 
Amarras  referências a outros nós da árvore. 
 
 Se subárvore da esq. De um nó é vazia, então a referência da esq. Deste nó aponta p/ o nó 
predecessor a este, com respeito a uma dada ordem de caminhamento. De forma similar, se a 
subárvore da direita de um nó é vazia, então a referência da direita do nó aponta p/ o nó que lhe 
sucede na mesma ordem de caminhamento. 
 
 F ****** V 
 
 
 
 Amarrada Ref. Estruturada 
 
 Quando a árvore não for vazia, a ref. Da esq. Do nó descritor apontará p/ a raiz da árvore. 
Se a ordem de caminhamento p/ a qual a árvore for amarrada é a ordem central, então o nó 
descritor será o predecessor e sucessor do 1º e do último nó da árvore, respectivamente. Isto 
impõem, na realidade, uma característica circular à árvore. 
 
 Muitos nodos possuem referências nulas, tais referências podem servir para indicar uma 
determinada ordem de caminhamento. 
 Para distinguir uma ligação estrutural de uma amarrada acrescentam-se 2 campos lógicos 
adicionais. 
 
 
 
Estruturas de Dados II 
Prof.: Jones F. Giacon 
13 
 
 ELIG ESQ DADO DIR DLIG 
 
 Se ‘verdadeiro’ indicam que a ligação correspondente é estrutural, senão é amarrada. 
 
 Para facilitar operações de novos nodos é criado um descritor que possui a mesma estrutura 
que os nodos da árvore. 
 
EX.: Header 
 
 / 
 
 C Árvore amarrada em 
 ordem central 
 
 B H 
 
 
 A E J 
 
 
 D 
 
 
 Esquerda de C é cheia, então a ligação é estrutural, então o ELIG é Verdadeiro. 
 A Direita de B, é pontilhada, então a ligação é amarrada e o DLIG é Falso. 
 
Procedimento Cria_Arvore_Amarrada (Header) 
 ALOQUE (Header) 
 Se ( Header = NIL ) 
 Entao ERRO 
 Senao Inicio 
 Header.Dir  Header 
 Header.DLIG  Verdadeiro { ligação estrutural} 
 Header.Esq  Header 
 Header.ELIG  Falso 
 Fim 
 
HEADER 
 
 ELIG ESQ DADO DIR DLIG 
 
 
 AmarradaEstrutural 
 
 
 
 
 
 
Estruturas de Dados II 
Prof.: Jones F. Giacon 
14 
Funcao Sucessor_Central (Nodo) : Sucessor 
 Sucessor  Nodo.Dir 
 Se (Nodo.DLIG) 
 Entao Inicio 
 Enquanto (Sucessor.ELIG) 
 Faca Sucessor  Sucessor.Esq 
 Fim 
 Se (Sucessor.Dir = Sucessor) {achou o header} 
 Entao Sucessor  NIL 
 
Funcao Predecessor_Central (Nodo) : Predecessor 
 Predecessor  Nodo.Esq 
 Se (Predecessor.Dir = Predecessor) {achou o header} 
 Entao Predecessor  NIL 
 
Procedimento Insere_Esq (Nodo, Aux) 
{ insere AUX a esquerda do nodo; se a subarvore esquerda do nodo for vazia, AUX torna-se 
sua subarvore esquerda, caso contrário AUX é inserido entre NODO e será subarvore 
esquerda} 
 Aux.Esq  Nodo.Esq 
 Aux.ELIG  Nodo.ELIG 
 Nodo.Esq  Aux 
 Nodo.ELIG  Verdadeiro 
 Aux.Dir  Nodo 
 Aux.DLIG  Falso 
 Se (Aux.ELIG) {nodo possui subarvore esquerda} 
 Então Inicio 
 Pred  Predecessor_central (Aux) 
 Pred.Dir  Aux 
 Pred.DLIG  Falso 
 Fim 
 
 Ao inserir um nodo a esquerda, ele deve ser estruturada. 
 ELIG de Aux verdadeiro  entao é estrutural e então possui nodos abaixos. 
 
Procedimento Insere_Dir (Nodo, Aux) 
 Aux.Dir  Nodo.Dir 
 Aux.DLIG  Nodo.DLIG 
 Nodo.Dir  Aux 
 Nodo.DLIG  Verdadeiro 
 Aux.Esq  Nodo 
 Aux.ELIG  Falso 
 Se (Aux.DLIG) {nodo possui Sub-direita} 
 Então Inicio 
 Suc  Aux.Dir 
 
Estruturas de Dados II 
Prof.: Jones F. Giacon 
15 
 Suc.Esq  Aux 
 Suc .ELIG  Falso 
 Fim 
 
Procedimento In_Ordem (Header) 
{caminhamento em In_Ordem s/ recursividade, sem estruturas adicionais} 
 Se (Header.Esq = Header) {árvore vazia} 
 Entao ERRO 
 Senao Aux  Sucessor_Central (Header) 
 Enquanto (Aux <> NIL) 
 Faça Inicio 
 Visita (AUX) 
 Aux  Sucessor_Central (Aux) 
 Fim 
 
Árvore Tipo-B (“B Tree”) 
 
Def.: é uma árvore que possui as seguintes características: 
a) todos os nodos folhas estão no mesmo nível 
b) um nodo que possua “k” filhos, possui “k-1” chaves 
c) todo nodo, exceto a raiz, possui no máximo k / 2 filhos 
 
Aplicação: manipulação de índices de arquivos 
 
Conj. de Indice ordem:1 
 raiz 
 1 
 50 82 
 
 2 Variação de Knuth 
 de Árvore-B 
 
 12 32 58 / ^ 89 / ^ 
 
 
 6 12 15 32 50 ^ / 52 58 82 ^ / 72 89 
 
 Ligações c/ os registros de dados 
 
 Uma arvore-B de ordem n tem no mínimo n, mas não mais do que 2n valores de dados 
(chaves) em cada nodo  se um nodo possui k valores possui k + 1 ligações (apontadores)