Estruturas de Árvores em Dados

Prévia do material em texto

Algoritmos e Complexidade
Árvores
Árvores
Alguns de nós já conhecemos em Estrutura de Dados, estruturas compostas por
registros de dados e ponteiros.
Estruturas de dados com capacidade otimizada de varrimento, manipulação e
utilização de memória dinâmica.
Lembram de:
Árvores
Listas Encadeadas
Árvores
Filas
Árvores
Pilhas
Árvores
Árvores são estruturas onde a relação entre seus elementos é de um para vários,
também denominada estrutura hierárquica.
Uma árvore consiste em um conjunto de nós, tal que:
Existe um nó denominado raiz.
Os demais nós formam m (m >= 0) conjuntos onde cada um deles também é uma árvore.
Podemos representar Árvores das mais variadas formas
Representando o mesmo conceito lógico:
Árvores
Árvores
Árvores
Árvores podem ser usadas em diversos tipos de aplicações
Aplicações onde é necessário recuperar informações rapidamente (SGBD)
Programas onde as informações têm que ser estruturadas de forma hierárquica.
Antes da popularização de arquivos categorizados como .xml e .json, os arquivos para troca e
manipulação de informação possuíam esta estrutura
Aplicações onde é necessário armazenar expressões matemáticas.
Vamos falar posteriormente sobre caminhamento, mas supondo que
recursivamente varremos uma árvore...
Para representar as expressões matemáticas A + B * 3 e (A + B) * 3 poderíamos
usar as árvores A e B a seguir:
Árvores
Árvores
Cada elemento de uma árvore pode ser classificado como:
Árvores
Dada a árvore acima, temos:
A, B, C, D, F e H são nós;
A é pai de B, C e F. F é pai de E
e H;
B, C e F são filhos de A. D e H
são filhos de F;
B, C e F são irmãos. D e H são
irmãos;
A é a raiz da árvores;
B, C, D e H são folhas.
Árvores
Ancestral: A é ancestral de B, C, F, D e H.
Descendente: B, C, F, D e H são descendentes de A. D e H são descendentes de F.
Arestas: são as ligações entre os nós.
Caminho: é uma seqüência de nós n1, n2, ... , ni tal que os nós sejam distintos e que
exista uma aresta entre cada par de nós.
Comprimento de um caminho: número de arestas que um caminho contém. Ex: A -
F - D tem comprimento 2.
Árvores
Nível de um nó: comprimento de um caminho que vai da raiz até o nó, sendo o nível
do no raiz igual a 0. Ex: A tem nivel 0; B nível 1 e D nivel 2.
Altura de uma árvore: é o nível mais alto de uma árvore. A árvore do exemplo tem
altura 2.
Grau de um nó: quantidade de subárvores de um nó. Ex: a tem grau 3, F tem grau 2
e B tem grau 0.
Grau da árvore: quantidade máxima de subárvores para cada nó da árvore.
Subárvore: é uma árvore formada por um dos nós filhos e seus descendentes.
Árvore Ordenada: árvore onde a ordenação de suas subárvores é importante.
Árvores
Árvores
Como nas pilhas e nas filas, apesar de existir a possibilidade de desenvolvimento
em Array (sequencial), preferencialmente utilizamos uma estrutura de
encadeamento.
Usando registros e ponteiros, lembram?
A implementação encadeada oferece:
Melhor aproveitamento de memória.
Chance de alterar dinamicamente o tamanho da árvore.
Há basicamente 2 formas de implementação encadeada:
Árvores
Com grau conhecido, neste caso 3:
Árvores
Com grau livre (desconhecido), neste caso teremos uma multilista, com uma lista
para cada nó:
Árvores
Geralmente trabalhamos com árvores de nós conhecidos
A maioria das implementações seguem este padrão e é assim que muitos dos
sistemas atuais têm sua consolidação de dados desenvolvida.
Uma das mais atualizadas e de simples desenvolvimento é a Árvore Binária
São estruturas do tipo árvore com as seguintes características:
A árvore tem grau 2 (por isso binária).
Cada subárvore é identificada como subárvores esquerda e direita.
Pode haver uma ordenação entre as subárvores.
Árvores
Árvores
A estrutura mais utilizada, é a estrutura encadeada.
Aqui se usa um estrutura dinâmica com apontadores (lista encadeada, seguindo a
lógica de dois ponteiros)
Onde cada nó contém os dados e os apontadores para as subárvores esquerda e
direita
Árvores
Esta forma de implementar é altamente dinâmica, pouco custosa em termos de
memória e eficiente em leitura.
Árvores
Caminhamento é o ato de percorrer todos os nós da árvore de uma forma
sistemática sendo cada nó "visitado" visitado uma única vez.
Um caminhamento completo sobre uma árvore produz uma sequência linear dos
nós, de modo que cada nó da árvore passa a ter um nó seguinte ou um nó anterior,
ou ambos, para uma dada forma de caminhamento.
No caso de árvores binárias existem 3 tipos de caminhamento mais
frequentemente utilizados. São eles:
Caminhamento LRN (pós-ordem)
Caminhamento NLR (pré-ordem)
Caminhamento LNR (in-ordem ou central)
Onde: L = Left, R = Rigth e N = Node
Árvores
Note que a forma de percorrer (caminhar) a árvore, tornará a leitura dos dados
distinta.
A primeira forma de percorrer a estrutura é chamado de “Caminhamento pós-
ordem) LRN.
Nesse caminhamento, partindo da raiz, visitamos todos os nós da subárvore
esquerda, depois os subnós da subárvore direita e, por último, o nó na raiz.
Esse algoritmo é repetido para cada nó.
Vamos ver uma forma prática de usar essa árvore e o caminhamento, com o uso
de uma pilha auxiliar
Seja uma árvore que representa uma expressão matemática A * (B + C) - (D + E):
Árvores
Percorrendo a árvore usando o Pós-Ordem,
teríamos a expressão na notação Pós-
Fixada:
A B C + * D E + -
Para avaliar a expressão acima, usamos o
seguinte algoritmo:
Se for operando empilha.
Senão se for operador desempilha dois
operandos da pilha, efetua a operação
indicada pelo operador e empilha o
resultado.
Ao terminar, o resultado estará na pilha.
Árvores
Árvores
Nesse caminhamento, partindo da raiz,
visitamos todos os nós da subárvore
esquerda, depois o nó raiz e finalmente os
nós da subárvore direita.
Percorrendo a árvore exemplo, teríamos a
expressão na notação infixa:
-A * (B + C) - (D + E)
Árvores
Uma ÁRVORE BINÁRIA DE BUSCA é uma árvore binária em que todos os valores na
subárvore esquerda são menores que o da raiz e todos os valores da subárvore
direita são maiores (ou iguais) que o da raiz.
Exemplos de árvores binárias de busca:
Árvores
Usando o caminhamento central, teríamos:
Sequência (1° árvore): A, B, C, D, E, F e G.
Sequência (2° árvore): 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 e 110.
Árvores
Para montar nossa árvore binária precisamos primeiro dominar o conceito de
recursividade.	
Ela será usado em vários procedimentos para a manipulação coesa da estrutura.
Vamos supor que possuímos um programa para manipulação de árvores binárias.
Conceitualmente teríamos de ter, ao menos, as seguinte funções:
CriarNo, ExisteNo, Deslocar, DisposeArvore, DelTree
Além de algumas possibilidades de caminhamento (forma de percorrer a árvore)
Árvores
O procedimento CriarNo recebe um apontador ArvoreBinaria e o dado que será
colocado no nó.
Além de alocar uma variável dinâmica para o nó, copia o dado para esta variável e faz
com que os apontadores para o pai, para o nó esquerdo e para o nó direito sejam
inicializados através do procedimento Inicializar.
A função ExisteNo retorna true se existe um nó na árvore binária passada,
seguindo pela direção especificada.
O procedimento Deslocar move o apontador do tipo ArvoreBinaria na direção
especificada.
Se a direção for nó raiz, Deslocar só encerra quando ArvoreBinaria não tiver mais um nó
pai.
Árvores
O procedimento DisposeArvore (usando o free do C) libera a árvore passada da
memória.
Dada a árvore abaixo, teríamos uma sequencia RECURSIVA determinada de
liberação de memória:
Árvores
Árvores
O procedimento Deltree elimina uma subárvore de uma árvore.
Além de desalocar da memória, faz com que o nó que apontava para a raiz da
subárvore aponte para nil.
Aqui teremos duas situações possíveis:
Removendo uma subárvore (o apontador passado para Deltreenão é a raiz)
Removendo uma árvore completamente, quando o apontador passado para Deltree é o
nó raiz.
Árvores
Primeira situação (não raiz)
Árvores
Segunda situação (raiz):
Árvores
Uma possível função EncontrarChave busca na árvore passada a chave informada.
Se encontrar, P apontará para o nó que a contém e a função retorna true. Caso não
encontre, a função retorna false e P aponta para o nó que seria o seu pai caso existisse.
A função Inserir usa EncontrarChave para verificar se a chave já existe. Caso exista,
retorna false.
Se não existir, aproveita o apontador P (aponta para o pai correto do nó a ser inserido) e
inclui na subárvore esquerda de P se a chave sendo inserida for menor ou na direita se
for maior, retornando true.
A remoção de um nó pode ser mais simples ou complexa de acordo com o número
de subárvores que possui.
Árvores
Árvores
Árvores
Como já discutimos na aula anterior, quando percorremos a altura de uma árvore
binária qual a complexidade do algoritmo?
Como explicamos esse pior caso (worst case)
Árvores
Melhor e pior caso para o percurso (inserções e remoções baseados nele)
Árvores
Existem diversas árvores, com diversos tipos de regramento para alocação e
remoção de dados.
Árvores que se balanceiam para manter os tamanhos e estruturas.
Desta forma, fugimos da possibilidade do pior caso da árvore binária
Crescimento em uma única direção
E mantemos uma estrutura mais coesa e organizada.
Este será o objeto de estudo a nossa próxima aula: ÁRVORES BALANCEADAS