Estrutura de Dados - Árvore

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
Árvores
*
*
Árvores
Utilizada em muitas aplicações 
Modela uma hierarquia entre elementos
Árvore Genealógica
Diagrama Hierárquico de uma Organização 
Modelagem de Algoritmos
Estrutura de Diretórios
O conceito de árvores está diretamente ligado à recursividade
*
*
Árvores
Conjunto finito de elementos onde:
O conjunto é vazio e a árvore é dita vazia, ou
Existe um nó especial chamado de raiz, e os demais nós constituem um conjunto vazio ou são divididos em subconjuntos disjuntos chamados de subárvores
cada elemento é um nó (ou vértice) da árvore
arestas (ou ramos) conectam os vértices
todo nó é raiz de uma subárvore composta do próprio nó e dos possíveis nós abaixo dele
*
*
Representação
*
*
Terminologia e Propriedades
Cada nó (exceto o raiz) tem exatamente um antecessor imediato ou pai
Cada nó pode ou não ter nós sucessores imediatos ou filhos:
Nós SEM filhos são chamados de Externos , Terminais, ou Folhas
Nós COM filhos são chamados de Internos , Não-terminais, ou Não-folhas
*
*
Terminologia e Propriedades
Caminho em uma árvore:
Seqüência de nós distintos e sucessivos, conectados por arestas da árvore
Existe exatamente um único caminho entre o nó raiz e cada um dos outros nós da árvore (se existir mais de um caminho ou nenhum  Grafo)
Grau 
Grau de um nó: número de subárvores (ou filhos) dele
No exemplo anterior: 
			grau de A é 3; de N é 4; de J é 1
Grau de uma árvore: grau máximo atingido pelos nós
*
*
Terminologia 
Nível de um nó:
Número de nós no caminho da raiz até o nó
Altura (profundidade) de uma árvore: 
maior nível atingido por um nó
maior distância entre a raiz e qualquer nó
*
*
Terminologia 
 nível de A é zero
 nível de C é 1
 nível de K é 3
 nível de P é 5
 nível de um nó = 
 nível de seu pai + 1
 Altura da árvore: 6
*
*
Árvore Binária
As árvores podem ser classificadas de acordo com o número máximo de filhos por nó 
Árvore Binária: caso particular onde os nós só podem ter no máximo 2 filhos (de 0 a 2)
De forma recursiva, é definida como:
um conjunto finito de elementos que é ou vazio ou composto de 3 subconjuntos disjuntos: um nó raiz e duas subárvores binárias
subárvore da esquerda (SAE)
subárvore da direita (SAD)
*
*
Árvore Binária
subárvore da esquerda (SAE)
subárvore da direita (SAD)
raiz
A
B
G
F
E
D
C
H
I
raiz da
SAE
raiz da
SAD
*
*
Representando Árvores Binárias
Cada nó da árvore deve armazenar três informações:
o conteúdo a ser guardado
um ponteiro para a SAE
um ponteiro para a SAD
A estrutura da árvore será representada por um ponteiro para o nó raiz
*
*
Representando Árvores Binárias
typedef struct tp_no {
char info;
struct tp_no * esq;
struct tp_no * dir;
} tparvore;
tparvore * raiz;
A
B
C
D
B
C
A
D
raiz
*
*
Representando Árvores Binárias
(A*B) – ( (F+G)*E )
A
B
*
F
G
+
E
*
-
*
*
Representando Árvores Binárias
ÁRVORE?
(25 – (15 / 3)) + (6 * (31 + (2 * 18)))
*
*
Representando Árvores Binárias
(25 – (15 / 3)) + (6 * (31 + (2 * 18)))
+
-
*
+
*
/
25
15
3
6
31
2
18
*
*
Aplicações com Árvores Binárias
É uma estrutura útil quando uma de duas decisões devem ser tomadas no decorrer do processo
Uma operação comum é atravessar a árvore binária, visitando cada nó (Percurso)
Como visitaremos cada nó?
Operação é trivial para listas lineares 
Para árvores, existem diferentes formas de proceder 
Os métodos diferem conforme a ordem em que se visitam os nós
*
*
Percurso em Árvores Binárias
PRÉ-ORDEM: visitar a raiz, então visitar a subárvore da esquerda e depois a subárvore da direita
EM ORDEM (ou ordem simétrica): visitar a subárvore da esquerda, então visitar a raiz e depois a subárvore da direita
PÓS-ORDEM: visitar a subárvore da esquerda, então visitar a subárvore da direita e depois a raiz
*
*
D
B
G
E
F
C
A
H
I
Percurso em Árvores Binárias
*
*
D
B
G
E
F
C
A
H
I
Percurso em Árvores Binárias
PRÉ-ORDEM: raiz, SAE, SAD
A – B – D – C – E – G – F – H – I
*
*
D
B
G
E
F
C
A
H
I
Percurso em Árvores Binárias
EM ORDEM: SAE, raiz, SAD
D – B – A – E – G – C – H – F – I
*
*
D
B
G
E
F
C
A
H
I
Percurso em Árvores Binárias
PÓS-ORDEM: SAE, SAD, raiz
D – B – G – E – H – I – F – C – A
*
*
Implementação simples dos métodos: Recursividade
typedef struct tp_no {
	char info;
	struct tp_no * esq;
	struct tp_no * dir;
} tparvore;
tparvore * arv;
Percurso em Árvores Binárias
*
*
Pré-ordem
void pre_ordem (tparvore * p) { 
	 if (p != NULL) {
	visite(raiz);
	pre_ordem (p->esq);
	pre_ordem (p->dir);
}
}
*
*
Em ordem 
void em_ordem (tparvore * p) { 
	 if (p != NULL) {
	em_ordem (p->esq);
	visite(raiz);
	em_ordem (p->dir);
}
}
*
*
Pós-ordem 
void pos_ordem (tparvore * p) { 
	 if (p != NULL) {
	 pos_ordem (p->esq);
	 pos_ordem (p->dir);
	visite(raiz);
}
}
*
*
Árvore Binária onde, para cada nó:
nós com informações menores estão na subárvore esquerda
nós com informações maiores (ou iguais) estão na subárvore direita
Empregando o algoritmo de percurso Em Ordem numa ABB, obteremos os elementos impressos de forma ordenada 
A inserção dos nós da árvore deve manter essa propriedade
Árvore Binária de Busca (ABB)
*
*
Árvore Binária de Busca
Para a busca de uma informação N na árvore binária de busca:
primeiro compare N com a informação da raiz
se menor, vá para a subárvore esquerda
se maior, vá para a subárvore direita 
Aplique o método recursivamente
O procedimento pára quando:
o nó com N é encontrado 
chega-se a NULL
A cada passo, garante-se que nenhuma outra parte da árvore contém a chave sendo buscada
*
*
Árvore Binária de Busca
Busca não-recursiva
tparvore * busca (tpitem a, tparvore * p) {
	while (p != NULL) { 
		if (a < p->info) 
			p = p->esq; 
		else 
			if (a > p->info) 
				p = p->dir; 
			else 
				return (p);
	};
 	return (NULL); 
}
*
*
Árvore Binária de Busca
Busca recursiva
tparvore * buscarec (tpitem a, tparvore * p) {
	if (p != NULL) { 
		if (a < p->info) 
			return buscarec(a,p->esq); 
		else 
			if (a > p->info) 
				return buscarec(a,p->dir); 
			else 
				return (p);
	}
	else
 		return (NULL); 
}
*
*
Inserindo em Árvore Binária de Busca
Para inserir um nó na árvore:
Fazer uma busca SEM sucesso 
Comparar sucessivamente o elemento com cada nó e verificar se ele deve entrar à esquerda ou à direita deste nó até atingir uma posição nula 
Alocar um novo nó
É necessário saber por qual nó se chegou a NULL
 guardar o pai do novo nó
*
*
3
7
9
6
1
4
Onde inserir o 11?
14
Inserindo em Árvore Binária de Busca
*
*
3
7
9
6
1
4
Onde inserir o 2?
14
11
Inserindo em Árvore Binária de Busca
*
*
Inserção Árvore Binária de Busca
tparvore * insere (int valor, tparvore * r) {
	 tparvore *pai=NULL, *novo, *p=r;
	novo = aloca();
	if (novo == NULL)
		return NULL;
	else {
		novo->info = valor;
		novo->esq = NULL;
		novo->dir = NULL;
		while (p != NULL) {
			pai = p;
			if (valor < p->info)
				p = p->esq;
			else
				p = p->dir;
 		}
	if (pai != NULL) {
		if (valor < pai->info)
			pai->esq=novo;
		else
		 	pai->dir=novo;
		return r;
	}
	else
		return novo;
 }
}
*
*
A remoção de um elemento é mais complexa
Remoção de um nó folha
o ponteiro esquerdo ou direito do pai será atualizado para NULL
Se o nó possui apenas um filho
 o ponteiro apropriado do pai passa a apontar para o filho
Remoção em Árvore Binária de Busca
*
*
Se o nó possui dois filhos
se um desses dois filhos não possui filhos, usar este filho para substituir o nó removido
Senão: substituir o valor do nó a ser removido
Substituir pelo o elemento cujo valor é imediatamente maior (ou menor)
Remoção em Árvore Binária de Busca
*
*
Algoritmo?
Remoção
em Árvore Binária de Busca
*
*
Removendo 5: 
basta que o ponteiro da direita de 4 aponte para NULL
Remoção em Árvore Binária de Busca
*
*
Removendo 3: 
basta substituir o nó 3 pelo nó 2
Remoção em Árvore Binária de Busca
*
*
Removendo 4: 
basta substituir o 4 pelo 5
Remoção em Árvore Binária de Busca
*
*
Removendo 7 (raiz): 
substituir o 7 pelo imediatamente maior(8)
como determinar?
Remoção em Árvore Binária de Busca
*
*
tparvore * retira (int valor, tparvore * r) {
	tparvore *p=r, *ant=NULL, *sub, *pai, *filho;
	while (p!=NULL && p->info!=valor) {
		ant=p;
		if (valor < p->info)
			p = p->esq;
		else
			p = p->dir;
	}
	if (p==NULL) /* não encontrou */
		return r;
	/* nó tem no máximo um filho */
	if (p->esq==NULL)
		sub=p->dir;
	else
		if (p->dir==NULL)
			sub=p->esq;
		else {
		/* nó tem dois filhos */
			pai=p; sub=p->dir; filho=sub->esq;
			while (filho!=NULL) {
				pai=sub; sub=filho; filho=sub->esq;
			}
*
*
/* neste ponto, sub é o sucessor em ordem de p */
			if (pai!=p) {
				/*p não é o pai de sub e sub==pai->esq */
				pai->esq=sub->dir;
				/* remove o nó apontado por sub de sua atual 			posição e substitui pelo filho direito de rp */
				/* sub ocupa o lugar de p */
				sub->dir=p->dir;
			}
		/*define filho esq de sub para que sub ocupe o lugar de p */
			sub->esq=p->esq;
		}
		/* insere sub na posição ocupada por p */
		if (ant==NULL)
			r=sub; /* p era raiz */
		else
			if (p==ant->esq)
				ant->esq=sub;
			else
				ant->dir=sub;
		free(p);
	return r;
}
2
2
7
9
6
16
16
18
59
59
62
62
62
73
74
72
72
72
72
76
77
78
84
85
88
88
90
91
91
93
95
96
96
97
98
99
100
96
96