32157_136386_estrutura_de_dados_-_arvores_-_binaria.pdf

7/28/2019 32157_136386_estrutura_de_dados_-_arvores_-_binaria.pdf

1/48

rvores

1

Prof. Cristhian Heck, M.Sc.


2/48

INTRODUOrvores

2


3/48

Introduo

rvores so estruturas de dados utilizadas paraarmazenar e recuperar dados de forma rpida eeficiente;

rvores no so lineares, ou seja, os elementos no sodispostos em forma sequencial;

3


4/48

Introduo

rvores so amplamente utilizadas e possuem diversasestratgias de implementao;

Cada estratgia tem um conjunto especfico dealgoritmos para armazenamento e recuperao dosdados;

rvores genealgicas so anlogas s estruturas dedados rvores.

4


5/48

COMPOSIOrvores

5


6/48

Composio

As rvores so compostas por:

Nodos/Ns: so os elementos inseridos em umarvore;

Arestas: fazem a ligao entre 2 nodos;

6


7/48

Composio

O primeiro Nodo de uma rvore chamado de Raiz;

Todos os demais nodos da rvore sero seusdescendentes;

Nodos que no tenham filhos sero chamados de folhas,ou terminais;

Os demais nodos so ditos intermedirios, ou s vezes:galhos.

7


8/48

Composio

As principais propriedades de cada nodo so:

Ordem/Grau: Indica o nmero de filhos que o nodopossui;

Nvel/Altura/Profundidade: Indica a distncia donodo em relao raiz;

A rvore tambm possu valores de ordem e de nvel.

Ambos os valores sero assumidos com base nomaior valor encontrado em qualquer nodo.

8


9/48

A

CB

D FE

G IH J

Nvel 0N A = RaizOrdem 2

Nvel 1N B = GalhoOrdem 3

N C = FolhaOrdem 0

Nvel 2N D = FolhaOrdem 0N E = GalhoOrdem 4N F = FolhaOrdem 0

Nvel 3N G = FolhaOrdem 0N H = FolhaOrdem 0N I = FolhaOrdem 0N J = FolhaOrdem 0

rvore: Nvel 3 e Ordem 4

Ns / Nodos

Arestas

Nvel

Ordem

9


10/48

OUTRAS PROPRIEDADESrvores

10


11/48

Propriedades

Qualquer nodo de uma rvore pode ser chamado de raizpara uma sub-rvore;

Um Nodo Pai um nodo conectado diretamente acimade outro nodo;

Um Nodo Filho um nodo conectado diretamente abaixo

de outro nodo;

Nodos Irmos compartilham o mesmo nodo pai;11


12/48

Propriedades

Nodos Ancestrais so todos os nodos que esto acima deum nodo, com ligao direta ou indireta;

Nodos Descendentes so todos os nodos que estoabaixo de um nodo, com ligao direta ou indireta;

12


13/48

EXERCCIOSrvores

13


14/48

A

CB D

F

E

G IH MK N

O P TSR U X

765

#

4

&

3WY Z

8 9

14


15/48

RVORES BINRIASrvores

15


16/48

rvores Binrias

rvores Binrias so rvores com todas aspropriedades vistas anteriormente, porm comalgumas regras:

A Ordem mxima da rvore 2;

Todos os nodos de uma sub-rvore, do filho direita, sero maiores do que o nodo pai;

Todos os nodos de uma sub-rvore, do filho esquerda, sero menores do que o nodo pai;

Geralmente chamadas de rvores binrias depesquisa; 16


17/48


18/48

A

CB

D FE G

IH

J

Nvel 0

N A = RaizOrdem 2

Nvel 1N B = GalhoOrdem 2N C = GalhoOrdem 2

Nvel 2N D = FolhaOrdem 0N E = GalhoOrdem 2N F = FolhaOrdem 0N G = FolhaOrdem 0

Nvel 3

N H = GalhoOrdem 1N I = FolhaOrdem 0

rvore Binria: Nvel 4 e Ordem 2

Ns / Nodos

Arestas

Nvel

Ordem

Nvel 4N J = FolhaOrdem 0

18


19/48

IMPLEMENTADO RVORES BINRIASrvores

19


20/48

Implementando

rvores so implementadas com elementos dinmicos,assim como nas listas encadeadas;

Nas listas, tnhamos apenas um prximo elemento. Nasrvores, cada elemento ter dois prximos:

Filho da Esquerda; e

Filho da Direita.

20


21/48

Implementando

public class Nodo

{

public int numero;

//outros atributos

//...

public Nodo Esquerda;

public Nodo Direita;

public Nodo Pai; //Opcional

}

21


22/48

Implementando

Construtor para classe nodo:

publicNodo(int nro)

{

this.numero = nro;

this.Esquerda = null;

this.Direita = null;this.Pai = null;

} 22


23/48


24/48

Implementando

Vale lembrar das regras mais importantes de navegaonas rvores binrias de pesquisa:

Elementos menores estaro esquerda;

Elementos maiores estaro direita.

24


25/48

Implementando

Insero:

Se a raiz estiver vazia:

Insere na raiz.

Seno: Navega pela rvore (subindo de nvel)

comparando o valor a ser inserido com os valoresdos nodos visitados;

Se Menor Esquerda; e Se Maior Direita;

Quando encontrar um nodo sem filho para o ladopor onde deveria seguir, insere o novo elemento

nesta posio.

25


26/48

public void Inserir(Nodo novo) {

novo.Direita = null;novo.Esquerda = null;

novo.Pai = null;if(raiz == null)raiz = novo;

else {Nodo aux = raiz;while (aux != null) {

if(novo.numero < aux.numero) {if(aux.Esquerda == null) {

aux.Esquerda = novo;break;

}

aux = aux.Esquerda;}

else {if(aux.Direita == null) {

aux.Direita = novo;break;}aux = aux.Direita;

}}novo.Pai = aux;

}}

26


27/48

Implementando

Pesquisa:

Se a raiz estiver vazia:

No encontrado!

Seno:

Navega pela rvore (subindo de nvel) comparandoo valor pesquisado com os valores dos nodosvisitados:

Igual Encontrado!

Menor Desloca Esquerda; Maior Desloca Direita;

Se percorrer toda a rvore sem encontrar:

No encontrado!27


28/48

ImplementandopublicNodo Pesquisar(int nro)

{

Nodo aux = raiz;

while (aux != null)

{

if(aux.numero == nro)return aux;

if(nro < aux.numero)

aux = aux.Esquerda;

elseaux = aux.Direita;

}

return null;

}

28


29/48

Implementando

Navegar por todos os Nodos:

6

82

1 4

329


30/48

Implementando

Listar Contedo da rvore:

A listagem da rvore pode ser feitas de trs formasbsicas:

Em ordem: (crescente ou decrescente)

1, 2, 3, 4, 6, 8

Pr-ordem:

Pais processados antes

6, 2, 1, 4, 3, 8 Ps-ordem:

Filhos processados antes

1, 3, 4, 2, 8, 6

6

82

1 4

3

30


31/48

Implementando

Listar Contedo da rvore:

Pode ser implementado com diversas estratgias:

Recursividade;

Pilha; Busca do subsequente.

6

82

1 4

3

31


32/48

Listar com Recursividade

public static void Listar(Nodo inicio) {

if(inicio == null) {

return;

}

Listar(inicio.Esquerda);

System.out.println(inicio.numero);

Listar(inicio.Direita);

}

32


33/48

Implementando

Remoo de Nodos:

Aux = Pesquisar(Nodo)

Se Aux == NULL no encontrado!

Seno: Se Aux for raiz:

Sem filhos

Com um filho

Com dois filhos

Seno Sem filhos

Com um filho

Com dois filhos 34


34/48

Implementando

Remoo de Nodos Raiz sem filhos:

Raiz = null;

35


35/48

Implementando

Remoo de Nodos:




Sem filhos

Com um filho

Com dois filhos

Seno Sem filhos

Com um filho

Com dois filhos 36


36/48

Implementando

Remoo de Nodos Raiz com um filho:

Raiz = Filho nico da Raiz;

37


37/48

Implementando

Remoo de Nodos:




Sem filhos

Com um filho

Com dois filhos

Seno Sem filhos

Com um filho

Com dois filhos 38


38/48

Implementando

Remoo de Nodos Raiz com dois filhos:

Substituto = Subsequente(Raiz); //Aux Substitui (Raiz pelo Substituto);

39


39/48

Implementando

Remoo de Nodos:




Sem filhos

Com um filho

Com dois filhos

Seno Sem filhos

Com um filho

Com dois filhos 40


40/48


41/48

Implementando

Remoo de Nodos:




Sem filhos

Com um filho

Com dois filhos

Seno Sem filhos

Com um filho

Com dois filhos 42


42/48

Implementando

Remoo de Nodos No Raiz / 1 filho:

PaiAux = Aux.Pai;

FilhoAux = Aux.Filho; (esquerda, ou direita) Se (PaiAux.Esquerda == Aux) ento

PaiAux.Esquerda = FilhoAux;

Seno

PaiAux.Direita = FilhoAux;

43


43/48

Implementando

Remoo de Nodos:




Sem filhos

Com um filho

Com dois filhos

Seno Sem filhos

Com um filho

Com dois filhos 44


44/48

Implementando

Remoo de Nodos No Raiz / 2 filhos:

Substituto = Subsequente(Aux);

Substitui (Aux pelo Substituto);

45


45/48

Implementando (1/3)public boolean Remover(Nodo remover)

{

if(remover == null)

return false;

//Informao paterna

Nodo pai = remover.Pai;

//Existe um substituto nico ou nenhum?Nodo subst;

if(remover.Esquerda == null || remover.Direita == null)

{

//Ambos so null? sem substituto

if(remover.Esquerda == remover.Direita)subst = null;

else

{ //Se direita vazia, substituto esta na esquerda e vice versa

if(remover.Direita == null)

subst = remover.Esquerda;

46


46/48

Implementando (2/3)else

subst = remover.Direita;

}//Se tiver um pai, atualiza vinculo dos filhos, seno atualiza a raiz.

if(pai != null)

{

if(pai.Esquerda == remover)

pai.Esquerda = subst;

else

pai.Direita = subst;

}

else

raiz = subst;

//Se tiver um filho substituto, atualiza seu vinculo paterno

if(subst != null)

subst.Pai = pai;

return true;

}

47


47/48


48/48

Implementandoprivate boolean SubstituirNodo(Nodo original, Nodo novo)

{

if(original == null || novo == null)

return false;

Nodo pai = original.Pai;

if(pai != null)

{if(pai.Esquerda == original)

pai.Esquerda = novo;

else

pai.Direita = novo;

}novo.Pai = pai;

Nodo filho = original.Esquerda;

if(filho != null)

filho.Pai = novo;

filho = original.Direita;

if(filho != null)filho.Pai = novo;

novo.Direita = filho;

return true;

Continuao...

49

Documents

32157_136386_estrutura_de_dados_-_arvores_-_binaria.pdf