Estrutura de Dados - Aula 15 - Pesquisa de Dados (Árvore de Pesquisa)

# Estrutura de Dados #Aula 15 – Pesquisa de Dados

(Árvores de Pesquisa)

Prof. Leinylson Fontinele Pereira

Na aula anterior...

Pesquisa de Dados# Sequencial e Binária

16:00Pesquisa e Ordenação: Aula 15 – Pesquisa de Dados (Árvores de Pesquisa)

O que vamos aprender?

Árvores# Conceito

# Componentes

# Tipos de árvores

# Onde são utilizadas?


Vamos começar?

16:00 4Pesquisa e Ordenação: Aula 15 – Pesquisa de Dados (Árvores de Pesquisa)

16:00

O que é uma Árvore?

Pesquisa e Ordenação: Aula 15 – Pesquisa de Dados (Árvores de Pesquisa)

16:00

Algumas Árvores...



16:00

São um tipo especial de grafo

Qualquer par de vértices (nós) estáconectado a apenas uma aresta

Grafo conexo (todos estão conectados)

Acíclico (não possui ciclos)Pesquisa e Ordenação: Aula 15 – Pesquisa de Dados (Árvores de Pesquisa)

Formas de Representação

16:00

Grafo Diagrama de Venn



16:00 Pesquisa e Ordenação: Aula 15 – Pesquisa de Dados (Árvores de Pesquisa)

Árvores

16:00

As árvores são uma das estrutura de dadosmais importantes da área da computação Utilizada em muitas aplicações do mundo real Os relacionamentos lógicos entre os dados

representam alguma dependência de hierarquiaou composição entre os nodos;


Árvores: Conceitos Básicos

16:00

As linhas que unem 2 nodos representam os relacionamentos lógicos e as dependências de subordinação existentes entre eles


Árvores: Conceitos Básicos

16:00

Relacionamentos de subordinação, formando hierarquias, podemapresentar diferentes significados


Hierarquia de Especialização


Hierarquia de Composição


Hierarquia de Dependência


Representação Gráfica de uma Árvore


Terminologia

16:00

A terminologia não é padronizada;

Existem nomes diferentes para osmesmos conceitos em diferentespublicações.


Terminologia

16:00

Raiz (root) Todos os outros nós da árvore são subordinados a ele

O acesso a todos os nós é sempre a partir dele

Nós descendentes: Relação de dependência com o nó mais acima


Terminologia

16:00

Caso o número de nós seja diferentede zero, existe sempre uma raiz;

Caso o número de nós seja zero, édenominada vazia.


Terminologia

16:00 Estrutura de Dados: Aula 13 – Árvores (conceito, elementos, tipos e utilizações)

Terminologia

16:00

Subárvore Conjunto de nós subordinados a um único nó, externo a esta subárvore


Terminologia

16:00

Grau de Um Nó

Número de subárvores que são subordinadas diretamente a esse nó.

Grau de uma Árvore

É o maior valor dentre os graus de todos os seus nós.


Terminologia


Terminologia

16:00

Folha ou Terminal (externo) São os nós de grau zero

Nó de derivação (interno)

Nós de grau maior do que zero e que apresentam uma subárvore


Terminologia


Terminologia

16:00

Nível de um Nó

Número de ligações entre este nó e a raiz da árvore mais um

Caminho

Sequência de nós consecutivos distintos entre dois nós

Comprimento do Caminho

Número de níveis entre os dois nós menos umPesquisa e Ordenação: Aula 15 – Pesquisa de Dados (Árvores de Pesquisa)

Terminologia


Terminologia


Terminologia

16:00

Floresta

Conjunto de zero ou mais árvores disjuntas

Árvore ordenada

Quando a ordem de suas subárvores é relevante para aaplicação que está sendo representada através destaestrutura de dados.


Terminologia


Árvore Binária (Binary Tree)





16:00

Usadas em situações onde, a cada passo, é precisotomar uma decisão entre duas direções



16:00

Usadas em situações onde, a cada passo, é precisotomar uma decisão entre duas direções


Árvore Estritamente Binária




Árvore Binária: Contagem dos Nós


Árvores Binárias de Busca

16:00

Considere uma árvore bináriacujos nós têm um campo chavede um tipo linearmenteordenado, ou seja, de um tipo(como números, caracteres, estrings) que admitecomparações.



16:00

Uma árvore binária é de busca (em relação ao campo chave)se cada nó X tem a seguinte propriedade: A chave de X é maior ou igual à chave de qualquer nó na subárvore

esquerda de X e menor ou igual à chave de qualquer nó na subárvoredireita de X.

Em outras palavras, se x é um nó qualquer então y->chave ≤x->chave ≤ z->chave para todo nó y na subárvore esquerdade x e todo nó z na subárvore direita de x.





Árvore Isomorfa

16:00

Quando é possível que se tornem coincidentesatravés de uma permutação na ordem dassubárvores de seus nós


Árvores Balanceadas (Equilibrada)

16:00

É aquela na qual existe umadistribuição equilibrada entreos nós da árvore

Existe uma diferença mínimaentre todas as folhas e a raiz.


Árvore Binária Quase Completa


Árvores Cheia ou Completamente Balanceada

16:00

É aquela em que todas as folhas estão a umadistância igual da raiz.


Árvores AVL


Árvores AVL


Árvores Balanceadas

16:00

Inserção dos valores {1,2,3,10,4,5,9,7,8,6}


Árvores Balanceadas


Árvores AVL: Rotação

16:00

Uma rotação simples ocorre quando um nó estádesbalanceado e seu filho estiver no mesmosentido da inclinação, formando uma linha reta.

Uma rotação-dupla ocorre quando um nó estiverdesbalanceado e seu filho estiver inclinado nosentido inverso ao pai, formando um “joelho”.


Árvores AVL: Rotação

16:00

Para garantirmos as propriedades da árvoreAVL rotações devem ser feitas conforme necessárioapós operações de remoção ou inserção.

Seja P o nó pai, FE o filho da esquerdade P e FD o filho da direita de P podemos definir 4tipos diferentes de rotação:


Árvores AVL: Rotação à Direita


Árvores AVL: Rotação à Esquerda


Árvores AVL: Rotação Dupla à Direita


Árvores AVL: Rotação Dupla à Esquerda


Árvore Rubro Negra

16:00

Nas árvores rubro-negras, os nós folhas não sãorelevantes e não contém dados.

Estas folhas não precisam ser mantidas emmemória de computador, basta apenas umponteiro para nulo para identificá-las.


Árvore Rubro Negra


Árvore Rubro Negra

16:00

Um nó é vermelho ou preto.

A raiz é preta.

Todas as folhas(nil) são pretas.

Ambos os filhos de todos os nós vermelhos são pretos.

Todo caminho de um dado nó para qualquer de seus nósfolhas descendentes contem o mesmo número de nós pretos.


Operações Básicas

16:00

Criação de uma árvoreAlocação das variáveis necessárias para a definição da árvoreAs demais operações são habilitadas depois disso

Inserção de um novo nóComo raizComo folhaComo uma posição intermediária



16:00

Exclusão de um Nó Quando não se realiza sobre uma folha, precisa reorganizar a árvore

Acesso a um Nó

Destruição de uma árvorePesquisa e Ordenação: Aula 15 – Pesquisa de Dados (Árvores de Pesquisa)


16:00

PaiDado um determinado nó, retorna o endereço do nó

imediatamente superior

TamanhoRetorna o número total de nós de uma árvore

AlturaRetorna a altura da árvore


Árvores Usando Contiguidade Física

16:00

Não é intuitiva como era no caso das Listas Lineares


Árvores Usando Contiguidade Física

16:00

A(3) B(1) C(0) D(4) E(0) F(0) G(0) H(0) I(0)

A(3) B(1) E(0) C(0) D(4) F(0) G(0) H(0) I(0)

1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6 7 8 9 10


Vantagens Usando Contiguidade Física

16:00

Eficiente em termos de espaço,principalmente quando o grau não variamuito

Implementação é mais simples se existirlimitação do número de descendentes.


Desvantagens Usando Contiguidade Física

16:00

Implementação não constitui uma boarepresentação física de árvores

Dificuldade de seguir a hierarquia implícitanestas estruturas ao manipular a árvore

Inserção e Remoção demorada


Árvore Ternária Usando Contiguidade Física

16:00

A B C D ʎ E ʎ ʎ ʎ ʎ F G ...

1 2 3 4 5 6 7 8 9 10 11 12 13


Árvores Implementadas por Encadeamento

16:00

O acesso se dá sempre pela raiz

Os demais nós são alcançados somente pelos endereços dos elos

A hierarquia de subordinação, implícita nas árvores, ficaperfeitamente representada.

Todos os nós da árvore deve apresentar a mesma estrutura.


Árvores Implementadas por Encadeamento

16:00

A

B / / C / / / D /

E / / / F / / / G / / /


Vantagens da Implementação por Encadeamento

16:00

É bastante Intuitiva

Inserção e Remoção são simples, constituindobasicamente na atualização de endereços noscampos de elo de alguns nós.


Desvantagens da Implementação por Encadeamento

16:00

Árvores cujos nós têm grau variado apresentamgeralmente muitos campos de elo ociosos

O Acesso aos nós pode ser dificultado devido ànecessidade de acessar qualquer nós sempreatravés da raiz.


Concluindo ...

16:00 71Pesquisa e Ordenação: Aula 15 – Pesquisa de Dados (Árvores de Pesquisa)

Nesta aula aprendemos... Árvores

# Conceito

# Componentes

# Tipos de árvores



Material: https://sites.google.com/site/leinylsonuespi

16:00

Aula baseada no material de:

Busca em arrays, Prof. André Backes


Nesta aula aprendemos...

16:00

Árvores# Conceito

# Componentes

# Tipos de árvores



Na próxima aula veremos...

Pesquisa de dados# Hashing


Prática

16:00 76

As aulas práticas foram baseadas no material de

Linguagem C Descomplicada , Dr. André R. Backes.

Disponível em: https://programacaodescomplicada.wordpress.com/


16:00

Considere a árvore com representação aninhada

( A ( B ) ( C ( F ( H ) ( I ) )) ( D) ( E ( G ) ) )


16:00

Quantas subárvores esta árvore contém?

Quais os nós-folha?

Qual o grau de cada nó?

Qual o grau da árvore?

Liste os ancestrais dos nós B, G e I.

Liste os nós de quem C é ancestral próprio.

Liste os nós de quem D é descendente próprio.

Dê o nível e a altura do nó F e A.

Qual a altura da árvore?


16:00 79

Árvore Binária


Árvore Binária: Implementação

16:00

Em uma Árvore Binária podemos realizar as seguintes operações Criação da árvore Inserção de um elemento Remoção de um elemento Acesso a um elemento Destruição da árvore

Essas operações dependem do tipo de alocação de memória usada Estática (heap) Dinâmica (lista encadeada)


Árvore Binária: Alocação Estática

16:00

Uso de um array

Usa duas funções para retornar a posição dos filhos à esquerda e àdireita de um pai


Árvore Binária: Alocação Dinâmica

16:00

Cada nó da árvore é tratado como um ponteiro alocado dinamicamentea medida que os dados são inseridos


TAD da Árvore Binária

16:00

Para guardar o primeiro nó da árvore utilizamos um ponteiro paraponteiro. Assim, fica fácil mudar quem é a raíz da árvore (se necessário)


Árvore Binária

16:00

ArvoreBinaria.h Os protótipos das funções O tipo de dado armazenado na árvore O ponteiro árvore

ArvoreBinaria.c

O tipo de dados árvore

Implementar as suas funçõesPesquisa e Ordenação: Aula 15 – Pesquisa de Dados (Árvores de Pesquisa)

16:00 85

Definindo a ÁrvoreBinária


Definindo a Árvore Binária


16:00 87

Criando a ÁrvoreBinária


Criando a Árvore Binária


16:00 89

Destruindo a ÁrvoreBinária


Destruindo a Árvore Binária


Destruindo a Árvore Binária


16:00 92

Árvore Vazia?


Árvore Vazia?


16:00 94

Altura da Árvore


Altura da Árvore


Altura da Árvore


16:00 97

Número de nós


Número de nós


Número de nós


Árvore Binária: Percurso na árvore

16:00

Percorrer todos os nós é uma operação muito comum em árvores binárias

Cada nó é visitado uma única vez

Isso gera uma sequência linear de nós, cuja ordem depende de como a árvore foipercorrida

Não existe uma ordem natural para se percorrer todos os nós de umaárvore binária

Isso pode ser feito para executar alguma ação em cada nó

Essa ação pode ser mostrar (imprimir) o valor do nó, modificar esse valor, etc.


Percurso pré-ordem

16:00

Ordem de visitação

Raiz

Filho esquerdo

Filho direito


Percurso pré-ordem

16:00


Raiz

Filho esquerdo

Filho direito


Percurso em-ordem

16:00


Filho esquerdo

Raiz

Filho direito


Percurso em-ordem

16:00


Filho esquerdo

Raiz

Filho direito


Percurso pós-ordem

16:00


Filho esquerdo

Filho direito

Raiz


Percurso pós-ordem

16:00


Filho esquerdo

Filho direito

Raiz


16:00 107

Árvores Binária de Busca


Árvore Binária de Busca: Inserção








Árvore Binária de Busca: Busca






Árvores Binárias de Busca: Remoção

16:00

Remover um nó de uma árvore binária de busca não é umatarefa tão simples quanto a inserção.

Isso ocorre porque precisamos procurar o nó a ser removido daárvore o qual pode ser um nó folha, nó interno (que pode ser a raiz),com um ou dois filhos.

Se for um nó interno

Reorganizar a árvore para que ela continue sendo uma árvorebinária de busca



16:00

Trabalha com 2 funções

Busca pelo nó

Tratar os 3 tipos de remoção: com 0, 1 ou 2 filhos







16:00

Exclusão de um nó folha



16:00

Exclusão de um nó com um filho



16:00

Exclusão de um nó com dois filhos


Education

Estrutura de Dados - Aula 15 - Pesquisa de Dados (Árvore de Pesquisa)