Estrutura de dados III

Prévia do material em texto

Estrutura de Dados
Listas Ordenadas, Árvores e Árvores Binárias 
Material Teórico
Responsável pelo Conteúdo:
Prof. Ms. Amilton Souza Martha
Revisão Textual:
Profa. Esp.Vera Lídia de Sá Cicarone
5
• Listas Ordenadas
• Aplicação de Listas Ordenadas
• Variáveis Polinômios
Mais uma vez o núcleo principal dos códigos está pronto no material, mas devemos entendê-lo 
para que possamos manipulá-lo da maneira que for necessária.
Os livros indicados na bibliografia possuem vários exercícios complementares. Pegue um dos 
livros e faça os exercícios práticos e teóricos.
 · Vamos conhecer a última estrutura de dados linear (listas 
ordenadas) e vamos começar a estudar as árvores.
 · A lista linear, diferente de pilhas e filas, que só permitem a 
inserção e remoção nas extremidades, possibilita inserir e 
remover elementos do meio da estrutura. Isso faz com que a 
solução de implementação sequencial seja inviável. Portanto, 
vamos trabalhar apenas com alocação dinâmica.
 · As árvores não são estruturas lineares, portanto também 
vamos implementar usando alocação dinâmica, mas essa 
implementação só será estudada na próxima unidade.
Listas Ordenadas, Árvores e Árvores 
Binárias
• Árvores
• Árvores Binárias
• Atravessamento em Árvores Binárias
6
Unidade: Listas Ordenadas, Árvores e Árvores Binárias
Além de Pilhas e Filas, que já estudamos, às vezes é necessário criar uma estrutura de dados 
que permaneça sempre ordenada, como, por exemplo, um catálogo telefônico ou o ranking 
de pontos de um jogo. Veja que isso é diferente de métodos de ordenação, que já estudamos. 
Na lista ordenada, os elementos já serão inseridos na ordem, o que difere dos métodos de 
ordenação, que possuem um vetor desordenado que, posteriormente, é ordenado.
Nem todos os problemas computacionais podem ser resolvidos utilizando listas lineares. Para 
simular um atendimento ou a caixa de saída de e-mail, podemos usar Filas; para simular um 
menu suspenso, podemos usar pilhas; para representar a estrutura de diretórios de um sistema 
ou o organograma de uma empresa ou mesmo fazer uma árvore genealógica de sua família, 
não é possível usar estruturas lineares.
Por isso, vamos entender melhor as características de uma estrutura de dados hierárquica 
chamada árvore. Veremos suas características e verificaremos que as árvores binárias resolvem 
muitos problemas computacionais. Na próxima unidade, estudaremos uma árvore binária mais 
especializada ainda: a árvore de busca binária.
Contextualização
7
Lista Ordenada é uma estrutura de dados linear e autoajustável no sentido de sempre se 
manter ordenada após cada inserção ou remoção. Devido a esse comportamento altamente 
dinâmico, esta estrutura será melhor implementada como alocação dinâmica encadeada, pois a 
inserção e a remoção de nós no meio das Listas será inevitável.
Diferente das pilhas e filas, cuja inserção e remoção de elementos se fazem apenas pelas 
extremidades da estrutura, as listas ordenadas necessitam inserir e remover no meio da estrutura.
Note que, embora seja possível a implementação de Listas ordenadas com alocação estática 
sequencial, ela é inviável, já que a inserção e a remoção no meio da estrutura fazem com que 
seja necessário deslocar todos os elementos à direita.
Uma Lista Ordenada L: [a1, a2, a3, ..., an] é uma lista linear, tal que, sendo n>1, temos:
• a1 <= ak, para qualquer 1<k<=n;
• ak <= an, para qualquer 1<=k<n;
• ak-1 <= ak <=ak+1, para qualquer 1<k<n.
Se L é uma lista ordenada, podemos garantir que nenhum elemento em L é inferior ao 
primeiro elemento(a1) ou superior ao último elemento (an). Além disso, tomando um elemento 
qualquer no meio da lista, nenhum elemento à sua esquerda o supera e nenhum elemento 
à direita é inferior a ele. Entre as diversas operações que podem ser realizadas com Listas 
Ordenadas, vamos considerar:
• Ins: insere um novo elemento na lista ordenada;
• Rem: remove um elemento específico da Lista Ordenada; 
• Find: procura um elemento na Lista e retorna sua posição;
Observe, na Tabela 01, a seguir, o funcionamento de uma lista L inicialmente vazia 
após as operações.
Tabela 01 – Exemplo de Operações em Listas Ordenadas
Operação Estado da Lista Resultado
-------- L:[ ] --------
L.ins(e) L:[ e ] --------
L.ins(x) L:[ e, x ] --------
L.ins(e) L:[ e, e, x ] --------
L.ins(m) L:[ e, e, m, x ] --------
L.ins(p) L:[ e, e, m, p, x ] --------
L.ins(l) L:[ e, e, l, m, p, x ] --------
L.ins(o) L:[ e, e, l, m, o, p, x ] --------
L.rem(x) L:[ e, e, l, m, o, p ] True
L.rem(m) L:[ e, e, l, o, p ] True
Listas Ordenadas
8
Unidade: Listas Ordenadas, Árvores e Árvores Binárias
L.find(o) L:[ e, e, l, o, p ] 4
L.find(e) L:[ e, e, l, o, p ] 1
L.rem(q) L:[ e, e, l, o, p ] False
L.rem(e) L:[ e, l, o, p ] True
Assim como Pilhas Dinâmicas e Filas Dinâmicas, a lista ordenada dinâmica encadeada usa 
a estrutura de listas simplesmente encadeadas. Veja, na Figura 01, a implementação da Lista 
Ordenada Dinâmica Encadeada.
Figura 01 – Implementação da Lista Ordenada Dinâmica
9
Um mapeamento m: A→B é uma relação que faz corresponder a cada elemento de A um 
único elemento em B ou nenhum. Funções geralmente são representadas por fórmulas através 
das quais podemos calcular o valor y associado a um dado valor x, como f(x) = y.
Mapeamentos, entretanto, na maioria das vezes, não podem ser representados por expressões 
aritméticas; por exemplo, um mapeamento que associa números de RGM a alunos não pode 
ser calculado. Os mapeamentos são representados por uma enumeração explícita de pares cuja 
formação não se baseia em nenhum princípio matemático. Assim, uma lista ordenada aparece 
como uma boa alternativa para implementar mapeamentos. Exemplo:
L:[(Ana,32),(Beth,17),(Caio,32),(Denis,15),(Elis,28),(Zélia,51)]
Dado um mapeamento m: A→B, a operação set(M,x,y) insere, no mapeamento, os pares 
(x,y). Como o par não pode se repetir, uma inserção com valor de x repetido simplesmente altera 
o valor de y. Por exemplo, para o mapeamento M:[(Gal,41),(Gil,52)], a operação set(M,Gal,45) 
resulta em M:[(Gal,45),(Gil,52)]. Outra operação importante é get(L,x), que retorna o valor 
correspondente de y referente a x dado.
No caso acima, uma instrução set(Caio,28) apenas alteraria o conteúdo do valor de y do par, 
ficando assim:
L:[(Ana,32), (Beth,17), (Caio,28),(Denis,15),(Elis,28),(Zélia,51)]
Outra função usada em Mapeamento é a get(M,x), que retorna o correspondente Y do valor 
X no mapeamento M. Esta função é muito semelhante à função Find da Lista Ordenada.
Desejamos aplicar os conceitos de listas ordenadas para implementar um tipo de dados que 
nos possibilitará a criação de variáveis capazes de armazenar polinômios na forma.
Analisando a forma de P(x), concluímos, facilmente, que o polinômio pode ser representado por 
um conjunto de pares (ak,k) em que cada par associa o coeficiente e a potência correspondente de x.
Para representar cada monômio do polinômio, vamos criar um TAD que representará 
esse nó do polinômio. Veja, na Figura 02, a representação de um nó de um polinômio e sua 
implementação em Java.
Aplicação de Listas Ordenadas
Variáveis Polinômios
P(x) = anx
n + an-1x
n-1 + ... + akx
k + a3x
3 + a2x
2 + a1x
1 + a0
10
Unidade: Listas Ordenadas, Árvores e Árvores Binárias
Figura 02 – Nó de um Polinômio
A implementação do Polinômio é muito parecida com a lista ordenada, porém, ao se criar 
um polinômio, não vai existir uma lista vazia; o menor valor vai ser P(X) = 0x0
Veja, na Figura 03, a implementação de um tipo abstrato para um Polinômio.
Figura 03 – Implementação de um Polinômio com Listas Ordenadas
11
Em diversas aplicações, necessitamos de estruturas mais complexas do que as puramente 
sequenciais vistas até agora (Pilhas, Filas e Listas Ordenadas). Entre essas, destacam-se as 
árvores, por existirem inúmeros problemas práticos que podem ser modelados por meio delas. 
Além disso, as árvores, em geral, admitem um tratamento computacional mais simples do que 
outras estruturas não lineares,como os grafos. As árvore são estruturas de dados consideradas 
hierárquicas.
Uma árvore é um conjunto finito de n > = 0 nós. Se n = 0, temos uma árvore nula. Se n > 
0, temos uma árvore com as seguintes características:
1) existe um nó especial chamado raiz;
2) os demais são particionados em T1, T2, . . ., Tk estruturas disjuntas de árvores (garantindo 
que um nó não aparecerá em mais de uma subárvore);
3) as estruturas T1, T2, . . ., Tk denominam-se árvores.
Árvores
12
Unidade: Listas Ordenadas, Árvores e Árvores Binárias
O termo “disjuntas” quer dizer que cada subárvore pode ser extraída da árvore principal sem 
que nenhum nó faça parte de duas subárvores. Vamos ver alguns conceitos que podem definir 
árvores em geral:
a) Grau: representa o número de subárvores de um nó.
b) Folha ou terminal: é o nó que possui grau 0, ou seja, não possui subárvores.
c) Grau de uma árvore (n-aridade): é definido como sendo igual ao máximo dos graus 
de todos os seus nós.
d) Nós filhos: são as raízes das subárvores de um nó. Este nó é o pai delas.
e) Nós irmãos: são os nós filhos que apresentam o mesmo pai (existem ainda nó ancestral, 
nó descendente, nó descendente esquerdo ou direito).
f) Nível: a raiz da árvore tem nível 0 (em alguns livros, é considerado igual a 1). Qualquer 
outro nó apresenta um nível a mais que seu nó pai.
g) Altura (ou profundidade): é o máximo dos níveis de todos os nós da árvore. Isso 
equivale ao tamanho do percurso mais distante da raiz até qualquer folha.
h) Percurso: é o caminho percorrido a partir da raiz para chegar a um nó.
i) Floresta: é um conjunto de zero ou mais árvores.
Veja, na Figura 04, a seguir, um exemplo de árvore e os conceitos vistos anteriormente 
extraídos dela. 
Figura 04 – Exemplo de Árvore e seus Conceitos
A forma mais comum de representar árvores graficamente é através de sua representação 
hierárquica (Figura 05), semelhante à utilizada para descrever organogramas de uma empresa.
13
Figura 05 – Representação Hierárquica de uma Árvore
Outra forma gráfica de representação de árvores é o chamado Diagrama de Inclusão (Figura 
06). Essa forma é a maneira tradicional de representação de conjuntos. Veja a representação da 
árvore anterior em um Diagrama de Inclusão.
Figura 06 – Representação com Diagrama de Inclusão de uma Árvore
Outro tipo de representação é a representação por parênteses aninhados. A sequência de 
parênteses representa as relações entre os nós da estrutura. As árvores representadas nas Figuras 
05 e 06 podem ser representadas da seguinte forma:
( A (B) ( C (D (G) (H)) (E) (F (I)) ) )
 Toda expressão aritmética pode ser colocada sob a forma de uma sequência de parênteses 
aninhados, como visto na parentetização para a Notação Polonesa Reversa, portanto também 
pode ser representada na forma de árvores. Veja, na Figura 07, o exemplo de representação da 
expressão (a + (b * (c / d) - e)) na forma de árvore hierárquica.
14
Unidade: Listas Ordenadas, Árvores e Árvores Binárias
Figura 07 – Representação de Expressão Numérica em forma de Árvore
 
Podemos montar uma árvore genérica em Java, implementando como seria um nó dessa 
árvore. Sabendo que a árvore é uma coleção de nós semelhantes, a classe em Java que 
implementaria um nó genérico poderia ser a mostrada na Figura 08 a seguir.
Figura 08 – Implementação do Nó de uma Árvore Genérica em Java
15
Como já mencionado, as árvores constituem as estruturas de dados não lineares com maior 
aplicação em computação e, dentre elas, destacam-se as árvores binárias. A maioria dos proble-
mas computacionais podem ser resolvidos com árvores binárias, portanto vamos nos concentrar 
nesse tipo específico de árvore. Uma árvore binária é uma árvore que pode ser nula ou, então, 
apresentar as seguintes características:
• um nó especial chamado raiz;
• os demais nós são particionados em T1, T2 - estruturas disjuntas de árvores binárias;
• A estrutura T1 é chamada subárvore esquerda e T2 subárvore direita da raiz.
Ou seja, as árvores binárias possuem grau menor ou igual a 2. Temos algumas árvores 
binárias especiais: as árvores estritamente binárias e as árvores binárias completas.
Árvore estritamente binária ocorre quando todo nó que não for folha tiver subárvores 
esquerda e direita não vazias. Uma árvore estritamente binária com n folhas contém sempre 
2n - 1 nós. Podemos ver um exemplo de árvore estritamente binária na Figura 09 a seguir.
Figura 09 – Árvore Estritamente Binária
Já as árvore binárias completas são, também, árvores estritamente binárias de profundidade 
d, cujas folhas estão no nível d, ou seja, possuem todas as folhas no mesmo nível. Podemos ver 
um exemplo na Figura 10 a seguir. Considerando tn como o número total de nós numa árvore 
binária completa de profundidade d, observamos a seguinte relação: tn = 2(d+1) – 1
Figura 10 – Árvore Binária Completa
Árvores Binárias
16
Unidade: Listas Ordenadas, Árvores e Árvores Binárias
Observamos que uma árvore binária é um caso especial de árvore cujos nós não têm grau 
superior a dois, ou seja, nenhum nó tem mais do que dois filhos. Também, existe um forte senso 
de posição pela existência de uma subárvore direita e esquerda.
Um ponto muito importante nas árvores é que cada subárvore caracteriza uma definição 
recursiva. Por exemplo, as árvores binárias apresentadas na Figura 11, a seguir, são distintas 
porque uma apresenta subárvore direita nula e a outra subárvore esquerda nula.
Figura 11 – Exemplos de Árvores Binárias Distintas
Atravessar uma árvore binária significa passar, de forma sistemática, por cada um de seus 
nós, realizando um certo processamento. Existem quatro tipos básicos de atravessamento:
• em-ordem;
• pré-ordem;
• pós-ordem;
• em nível.
Os três primeiros tipos são facilmente compreendidos se fizermos uma analogia entre eles e 
as notações segundo as quais uma expressão aritmética pode ser escrita. Vamos considerar, por 
exemplo, a seguinte árvore binária, mostrada na Figura 12, para os casos de estudo.
Figura 12 – Árvore Binária para mostrar os atravessamentos
Atravessamento em Árvores Binárias
17
a) Forma Infixa - Atravessamento em-ordem
1. Imprimir Folha Esquerda (E) 
2. Imprimir Raiz (R) 
3. Imprimir Folha Direita (D) 
Resultado: Carlos, Diogo, Feliciana, Luís, Paulo, Raí, Ronaldo. 
Obs.: A raiz está sempre no meio das subárvores esquerda e direita. 
Veja a implementação, em Java, do atravessamento Em-Ordem na Figura 13
Figura 13 – Atravessamento em Ordem
Se o atravessamento em-ordem for aplicado sobre uma árvore de busca binária, então 
conseguimos acessar (processar) os nós em ordem crescente. Isto é muito interessante quando 
desejamos armazenar sequências ordenadas através do uso de árvores binárias.
b) Forma Pré-fixa - Atravessamento pré-ordem
1. Imprimir Raiz (R) 
2. Imprimir Folha Esquerda (E) 
3. Imprimir Folha Direita (D) 
Resultado: Luís, Diogo, Carlos, Feliciana, Raí, Paulo, Ronaldo . 
Obs.: A raiz está sempre à esquerda das subárvores direita e esquerda. Veja a implementação 
em Java na Figura 14 a seguir.
Figura 14 – Atravessamento pré-ordem
18
Unidade: Listas Ordenadas, Árvores e Árvores Binárias
c) Forma Pós-fixa - Atravessamento pós-ordem
1. Imprimir Folha Esquerda (E) 
2. Imprimir Folha Direita (D) 
3. Imprimir Raiz (R) 
Resultado: Carlos, Feliciana, Diogo, Paulo, Ronaldo, Raí, Luís.
Obs.: A raiz está depois das subárvores esquerda e direita. Veja, na Figura 15, a implementação 
em Java
Figura 15 – Atravessamento pós-ordem
d) Atravessamento Em Nível
Esse atravessamento, apesar de ser o mais facilmente compreendido, é aquele que apresenta 
maior dificuldade de programação. Para realizar esse atravessamento, precisamos de uma fila 
contendo, inicialmente, apenas o nó raiz. A partir daí, enquanto a fila não se tornar vazia, 
retiramos dela um nó cujos filhos serão colocados na fila, então, o nó retirado da fila pode ser 
impresso. Veja a implementação na Figura 16.
Resultado: Luís, Diogo, Raí, Carlos, Feliciana, Paulo, Ronaldo.Figura 16 – Atravessamento em Nível
Podemos notar que o atravessamento em nível é o único que não é recursivo, ou seja, ele 
possui uma repetição interna para realizar a varredura.
19
1) Simuladores:
• http://www.cs.jhu.edu/~goodrich/dsa/trees/btree.html
2) YouTube
• http://youtu.be/MiUDxjVMeow
• http://youtu.be/WB8HDGcgiyY
3) Wikipedia:
• http://pt.wikipedia.org/wiki/Estrutura_de_dados
• http://pt.wikipedia.org/wiki/%C3%81rvore_(estrutura_de_dados)
• http://pt.wikibooks.org/wiki/Algoritmos_e_Estruturas_de_Dados/%C3%81rvores_
Bin%C3%A1rias
4) Livros Disponíveis na Biblioteca 
• DROZDEK, A. Estrutura de Dados e Algoritmos em C++. São Paulo: 
Pioneira Thomson Learning, 2005.
• FORBELLONE, A. L. V.; EBERSPACHER, H. F. Lógica de Programação: A Construção 
de Algoritmos e Estrutura de Dados. 3. ed. São Paulo: Makron Books do Brasil, 2005.
• MORAES, C. R. Estruturas de Dados e Algoritmos: Uma Abordagem Didática. 
São Paulo: Berkeley, 2001.
• PREISS, B. R. Estruturas de Dados e Algoritmos: Padrões de Projetos Orientados a 
Objetivos Com. Rio de Janeiro: Campus, 2001.
• TENENBAUM, A. M.; LANGSAM, Y. Estruturas de Dados Usando C. São Paulo: 
Makron Books do Brasil, 2005.
• VELOSO, P.; FURTADO, A.; SANTOS, C. S. Estruturas de Dados. 26. ed. Rio de 
Janeiro: Campus, 2003.
• WIRTH, N. Algoritmos e Estruturas de Dados. Rio de Janeiro: Ltc-Livros Técnicos 
e Científicos, 1999.
5) Livros Disponíveis na Biblioteca Virtual 
• ASCENCIO, Ana F.G. Aplicações das Estruturas de Dados em Delphi. São Paulo: 
Pearson Prendice Hall, 2005
• ______. Estruturas de Dados: algoritmos, análise da complexidade e 
implementações em Java e C/C++. São Paulo: Pearson Prendice Hall, 2010
• DEITEL, Harvey M. Java Como Programar. 8.a edição, São Paulo: Pearson Prentice Hall, 2010.
Material Complementar
20
Unidade: Listas Ordenadas, Árvores e Árvores Binárias
ASCENCIO, Ana F.G. Aplicações das Estruturas de Dados em Delphi. São Paulo: Pearson 
Prendice Hall, 2005.
GOODRICH, M. T.; TAMASSIA, R. Estruturas de Dados e Algoritmos em Java. 2. ed. 
Porto Alegre: Bookman, 2002.
LAFORE, R. Estruturas de Dados & Algoritmos em Java. Rio de Janeiro: Ciência Moderna, 2004.
PEREIRA, S. L. Estruturas de Dados Fundamentais: Conceitos e Aplicações. 9. ed. São 
Paulo: Erica, 2001.
WEISS, M. A. Data Structures And Algorithm Analysis In Java. 2. ed. Massachusetts: 
Addison-Wesley, 2007.
Referências
21
Anotações
www.cruzeirodosulvirtual.com.br
Campus Liberdade
Rua Galvão Bueno, 868
CEP 01506-000
São Paulo SP Brasil 
Tel: (55 11) 3385-3000