Estrutura de dados em Java - Aula 10 - Árvores Binárias

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

Estrutura de Dados
Árvores Binárias
Prof. Adriano Teixeira de Souza
Árvores
São estruturas de dados adequadas para a representação de hierarquias.
Uma árvore é composta por um conjunto de nós.
Existe um nó r, denominado raiz, que contém zero ou mais subárvores, cujas raízes são ligadas diretamente a r.
A raiz se liga a um ou mais elementos, e cada um destes forma uma nova subárvore. Esses elementos são seus galhos ou filhos.
Árvores
Fundamentos básicos
GRAU – número de subárvores de um nó.
FOLHA – um nó que possui grau zero, ou seja, não possui subárvores.
FILHOS – são as raízes das subárvores de um nó.
Nó não terminal é um nó que não é uma folha e é diferente da raiz.
Árvores
Fundamentos básicos
A altura de uma árvore é o comprimento do caminho mais longo da raiz até uma das folhas.
Uma árvore nula tem altura 0.
Todos os nós são acessíveis a partir da raiz.
Existe um único caminho entre a raiz e qualquer outro nó.
Árvores
Formas de representação gráfica
Árvores Binárias
Árvore Binária: Uma árvore binária é uma árvore que pode ser nula, ou então tem as seguintes características:
Existe um nó especial denominado raiz;
Nenhum nó tem grau superior a 2 (dois), isto é, nenhum nó tem mais de dois filhos;
Existe um “senso de posição”, ou seja, distingue-se entre uma subárvore esquerda e uma subárvore direita. 
Árvores Binárias
Atravessamento (ou caminhamento) de árvore é a passagem de forma sistemática por cada um de seus nós;
Diferentes formas de percorrer os nós de uma árvore:
Pré-ordem ou prefixa (busca em profundidade)
Em ordem ou infixa (ordem central)
Pós-ordem ou posfixa
Em nível
Árvores Binárias
Pré-ordem (prefixa)
visitar a raiz;
caminhar na subárvore à esquerda, segundo este caminhamento;
caminhar na subárvore à direita, segundo este caminhamento.
Árvores Binárias
Atravessamento em ordem (infixa)
caminhar na subárvore à esquerda, segundo este caminhamento;
visitar a raiz;
caminhar na subárvore à direita, segundo este caminhamento.
Árvores Binárias
Atravessamento pós-ordem (posfixa)
a) caminhar na subárvore à esquerda, segundo este caminhamento;
b) caminhar na subárvore à direita, segundo este caminhamento;
c) visitar a raiz.
Árvores Binárias
Atravessamento em nível 
Percorre-se a árvore de cima para baixo e da direita para a esquerda.
Árvores Binárias
Árvore Estritamente Binária:
É uma árvore binária na qual todo nó tem 0 ou 2 subárvores, ou seja, nenhum nó tem “filho único”.
Árvores Binárias
Árvore Binária Cheia
Todos os nós, exceto os do último nível, possuem exatamente duas subárvores.
Uma árvore binária cheia de altura h tem 2h – 1 nós.
Árvores Binárias
Árvore Degenerada
Cada nó possui exatamente um filho, e a árvore tem o mesmo número de níveis que de nós
Árvore Binária de Busca
Uma árvore é denominada árvore binária de busca se:
Todo elemento da subárvore esquerda é menor que o elemento raiz;
Nenhum elemento da subárvore direita é menor que o elemento raiz;
As subárvores direita e esquerda também são árvores de busca binária.
Árvore Binária de Busca
Busca
Se o valor for igual à raiz, o valor existe na árvore.
Se o valor for menor do que a raiz, então deve buscar-se na subárvore da esquerda, e assim recursivamente, em todos os nós da subárvore.
Se o valor for maior que a raiz, deve-se buscar na subárvore da direita, até alcançar-se o nó folha da árvore, encontrando ou não o valor requerido.
Árvore Binária de Busca
Inserção
Se a árvore estiver vazia, cria um novo no e insere as informações do novo nó.
Compara a chave a ser inserida com a chave do nó analisado:
Se menor, insere a chave na subárvore esquerda;
Se maior, insere a chave na subárvore direita.
Árvore Binária de Busca
Inserção
Exemplo:
Inserir os seguintes elementos: 7, 13, 20, 4, 1, 18, 5, 11 .
Árvore Binária de Busca
Remoção
A remoção de um nó é um processo mais complexo. Para excluir um nó de uma árvore binária de busca, há de se considerar três casos distintos:
Remoção na folha
Remoção de um nó com um filho
Remoção de um nó com dois filhos
Árvore Binária de Busca
Remoção na folha
A exclusão na folha é a mais simples, basta removê-lo da árvore.
Árvore Binária de Busca
Remoção de um nó com um filho
Excluindo-o, o filho sobe para a posição do pai.
Árvore Binária de Busca
Remoção de um nó com dois filhos
Neste caso, pode-se operar de duas maneiras diferentes:
Substitui-se o valor do nó a ser retirado pelo valor sucessor (o nó mais à esquerda da subárvore direita);
Substitui-se o valor do nó a ser retirado pelo valor antecessor (o nó mais à direita da subárvore esquerda)
Árvore Binária de Busca
Remoção de um nó com dois filhos
Exemplo de remoção substituindo o nó pelo seu antecessor.
Árvore Binária de Busca
Remoção de um nó com dois filhos
Exemplo de remoção substituindo o nó pelo seu sucessor.
Tipo Árvore Binária de Busca
Árvore é representada pelo ponteiro para o nó raiz
public class NoArvore {
	int info;
	NoArvore direita;
	NoArvore esquerda;
}
ABB: Impressão
Imprime os valores da árvore em ordem crescente, percorrendo os nós em ordem simétrica
void abb_imprime (NoArvore a)
{
 if (a != null) {
 abb_imprime(a.esquerda);
 System.out.println(a.info+"\n");
 abb_imprime(a.direita);
 }
}
ABB: Busca
Explora a propriedade de ordenação da árvore
Possui desempenho computacional proporcional à altura
NoArvore abb_busca (NoArvore r, int v)
{
 if (r == null)
 return null;
 else if (r.info > v)
 return abb_busca (r.esquerda, v);
 else if (r.info < v)
 return abb_busca (r.direita, v);
 else return r;
}
ABB: Inserção
recebe um valor v a ser inserido
retorna o eventual novo nó raiz da (sub-)árvore
para adicionar v na posição correta, faça:
se a (sub-)árvore for vazia
crie uma árvore cuja raiz contém v
se a (sub-)árvore não for vazia
compare v com o valor na raiz
insira v na sae ou na sad, conforme o resultado da comparação
ABB: Insere - exemplo
NoArvore abb_insere (NoArvore a, int v)
{
 if (a==null) {
 a = new NoArvore();
 a.info = v;
 a.esquerda = a.direita = null;
 }
 else if (v < a.info)
 a.esquerda = abb_insere(a.esquerda,v);
 else /* v >= a->info */
 a.direita = abb_insere(a.direita,v);
 return a;
}
é necessário atualizar os ponteiros para
as sub-árvores à esquerda ou à direita
quando da chamada recursiva da função,
pois a função de inserção pode alterar
o valor do ponteiro para a raiz da (sub-)árvore.
ABB: Inserção
Cria
insere 6
insere 8
insere 4
insere 5
insere 2
insere 3
insere 1
insere 9
insere 7
ABB: Remoção
recebe um valor v a ser inserido
retorna a eventual nova raiz da árvore
para remover v, faça:
se a árvore for vazia
nada tem que ser feito
se a árvore não for vazia
compare o valor armazenado no nó raiz com v
se for maior que v, retire o elemento da sub-árvore à esquerda
se for menor do que v, retire o elemento da sub-árvore à direita
se for igual a v, retire a raiz da árvore
ABB: Remoção
para retirar a raiz da árvore, há 3 casos:
caso 1: a raiz que é folha
caso 2: a raiz a ser retirada possui um único filho
caso 3: a raiz a ser retirada tem dois filhos
ABB: Remoção de folha
Caso 1: a raiz da sub-árvore é folha da árvore original
libere a memória alocada pela raiz
retorne a raiz atualizada, que passa a ser NULL
ABB: Remoção de pai de filho único
Caso 2: a raiz a ser retirada possui um único filho
libere a memória alocada pela raiz
a raiz da árvore passa a ser o único filho da raiz
ABB: remoção de pai de dois filhos
Caso 3: a raiz a ser retirada tem dois filhos
encontre o nó N que precede a raiz na ordenação
(o elemento mais à direita da sub-árvore à esquerda)
troque o dado da raiz com o dado de
N
retire N da sub-árvore à esquerda
(que agora contém o dado da raiz que se deseja retirar)
retirar o nó N mais à direita é trivial, pois N é um nó folha ou
N é um nó com um único filho (no caso, o filho da direita nunca existe)
NoArvore abb_retira (NoArvore r, int v)
{
	if (r == null)
		return null;
	else if (r.info > v)
		r.esquerda = abb_retira(r.esquerda, v);
	else if (r.info < v)
		r.direita = abb_retira(r.direita, v);
	else { 	/* achou o nó a remover */
		/* nó sem filhos */
		if (r.esquerda == null && r.direita == null) {
			//free (r);
			r = null;
		}
		/* nó só tem filho à direita */
		else if (r.esquerda == null) {
			NoArvore t = r;
			r = r.direita;
			//free (t);
		}
			/* só tem filho à esquerda */
			else if (r.direita == null) {
			NoArvore t = r;
			r = r.esquerda;
			//free (t);
		}
		/* nó tem os dois filhos */
		else {
			NoArvore f = r.esquerda;
			while (f.direita != null) {
				f = f.direita;
			}
			r.info = f.info; /* troca as informações */
			f.info = v;
			r.esquerda = abb_retira(r.esquerda,v);
		}
	}
	return r;
}