Aula 13 - Árvores - parte 1

Prévia do material em texto

Árvores 
SCC 202/502 – Algoritmos e Estruturas 
de Dados I 
Prof. Robson L. F. Cordeiro 
Material original editado: Prof. Thiago A. S. Pardo 
Listas e árvores 
n  Listas lineares 
n  Um nó após o outro, adjacentes 
n  Sem relações hierárquicas entre os nós, em 
geral 
n  Diversas aplicações necessitam de estruturas 
mais complexas do que as listas estudadas 
até agora 
n  Listas não lineares: árvores, grafos, etc. 
2 
Árvores 
n  Exemplo 
3 
Árvores 
n  Motivações para usá-las 
n  Inúmeros problemas podem ser representados e 
tratados por árvores 
n  Árvores admitem tratamento computacional eficiente 
quando comparadas a estruturas mais genéricas como 
os grafos (os quais, por sua vez, são mais flexíveis e, 
portanto, de mais complexa manipulação) 
n  Ótimas para busca! 
4 
Árvores 
n  Definição 
n  Uma árvore T, ou simplesmente uma árvore, é 
um conjunto finito de elementos denominados 
nós ou vértices tais que 
n  T = { } é a árvore dita vazia ou 
n  Existe um nó especial R, chamado raiz de T; os 
nós restantes constituem um único conjunto 
vazio ou são divididos em m (>=1) conjuntos não 
vazios que são as subárvores de R, sendo que 
cada subárvore é, por sua vez, uma árvore 
5 
Árvores 
B 
F G E 
C 
I 
D 
N L M 
A 
Raiz 
subárvore 
subárvore 
subárvore 
T = {A, {B, {E, {}}, {F, {L, {}}, {M, {}}}, {G, {}} }, {C, {I, {N, {}}}}, {D, {}}} 6 
Árvores 
n  Nós filhos, pais, tios, irmãos e avô 
n  Seja V o nó raiz de uma subárvore de T 
n  Os nós raízes w1, w2, ... wj das subárvores de V 
são chamados filhos de V 
n  V é chamado pai de w1, w2, ... wj 
n  Os nós w1, w2, ...wj são irmãos 
n  Se Z é filho de w1, então w2 é tio de Z e V é avô 
de Z 
7 
Árvores 
B 
F G E 
C 
I J H 
D 
K 
N L M 
A 
n  Filhos de A? Pai de F? Irmãos de H? Tios de J? Avô 
de K? Primos de G? 
8 
Árvores 
n  Grau de saída, descendente e ancestral 
n  O número de filhos de um nó é chamado grau 
(de saída) desse nó 
n  Obs.: o grau de entrada é sempre 1, exceto para o raiz, em 
que é 0. Por isso, ignora-se este tipo de grau. 
n  Se X pertence à subárvore V de T, então X é 
descendente de T e T é ancestral, ou 
antecessor, de X 
n  Válido também para quando X é a raiz de V 
9 
Árvores 
n  Nó folha e nó interior 
n  Um nó que não possui descendentes é 
chamado de nó folha, ou seja, um nó folha é 
aquele com grau de saída nulo ou zero 
n  Um nó que não é folha (isto é, possui grau de 
saída diferente de zero) é chamado nó 
interior, nó interno ou, ainda, nó intermediário 
10 
Árvores 
n  Grau de uma árvore 
n  O grau de uma árvore é o máximo entre os 
graus de seus nós 
11 
Árvores 
n  Floresta 
n  Uma floresta é um conjunto de zero ou mais 
árvores 
12 
Árvores 
n  Caminho, comprimento do caminho e caminho 
mínimo 
n  Uma sequência de nós distintos v1, v2, ..., vk, tal que 
existe sempre entre nós consecutivos (isto é, entre v1 
e v2, entre v2 e v3, ... , v(k-1) e vk) a relação "é filho 
de" ou "é pai de" é denominada um caminho na 
árvore; 
n  Caminho mínimo v1, v2, ..., vk aceita apenas um tipo de 
relação, entre “é filho de” e “é pai de”; diz-se que v1 alcança 
vk e que vk é alcançado por v1 
 
n  Um caminho de k vértices é obtido pela sequência de 
k-1 pares de vértices; o valor k-1 é o comprimento do 
caminho 13 
Árvores 
B 
F G E 
C 
I J H 
D 
K 
N L M 
A 
n  Caminhos entre A e J? 
n  Caminho mínimo? Comprimento desse caminho? 
14 
Árvores 
n  Nível (ou profundidade) e altura de um nó 
n  O nível de um nó é o número de nós (não o 
comprimento) do caminho mínimo da raiz até 
o nó 
n  O nível da raiz é 1 (alguns consideram zero) 
n  A altura de um nó V é o número de nós no 
maior caminho mínimo de V até um de seus 
descendentes 
n  As folhas têm altura 1 (alguns consideram zero) 
15 
Árvores 
n  Altura de uma árvore 
n  A altura de uma árvore T é igual ao máximo 
nível de seus nós, i.e., altura da raiz 
n  Em geral, representa-se a altura de T por h(T) 
e a altura da subárvore de raiz V por h(V) 
16 
Árvores 
B 
F G E 
C 
I J H 
D 
K 
N L M 
A 
n  Qual a altura dessa árvore? Qual o nível do nó C? 
17 
Árvores 
n  Árvore ordenada 
n  Uma árvore ordenada é aquela na qual os 
filhos de cada nó estão ordenados 
n  Assume-se ordenação da esquerda para a 
direita 
18 
Árvores 
n  Árvore ordenada 
19 
Árvores 
n  Árvore não ordenada 
20 
Árvores 
n  Árvore cheia 
n  Uma árvore de grau d é uma árvore cheia se 
possui o número máximo de nós, isto é, todos 
os nós têm número máximo de filhos (exceto 
as folhas, logicamente) e todas as folhas 
estão no mesmo nível 
21 
Árvores 
n  Exemplo de árvore cheia de grau 2 
22 
Árvores 
B 
F G E 
C 
I J H 
D 
K 
N L M 
A 
n  Considere a árvore abaixo 
n  Quantas subárvores A tem? 
23 
Árvores 
B 
F G E 
C 
I J H 
D 
K 
N L M 
A 
n  Considere a árvore abaixo 
n  Quem são os filhos de A? E os descendentes de A? 
24 
Árvores 
B 
F G E 
C 
I J H 
D 
K 
N L M 
A 
n  Considere a árvore abaixo 
n  Quais são os nós folha dessa árvore? 
25 
Árvores 
B 
F G E 
C 
I J H 
D 
K 
N L M 
A 
n  Considere a árvore abaixo 
n  Qual o grau dessa árvore? 
26 
Árvores binárias 
n  Árvores com grau 2, ou seja, cada nó pode 
ter 2 filhos, no máximo 
A 
B C 
D E 
Raiz 
F 
Terminologia: 
•  filho esquerdo 
•  filho direito 
•  informação 
27 
Árvores binárias 
n  Exercício 
n  Considerando a implementação dinâmica e 
encadeada, declare a estrutura de cada nó de 
uma árvore binária 
28 
Árvores binárias 
n  Exercício 
 
typedef char elem; 
 
typedef struct bloco { 
 elem info; 
 struct bloco *esq, *dir; 
} no; 
 
typedef struct { 
 no *raiz; 
} Arvore; 
29 
Árvores binárias 
n  Representação dinâmica e encadeada de 
uma árvore binária 
D 
A 
F B 
C G 
Raiz 
Raiz 
AB vazia 
30 
Árvores binárias 
n  Perguntas 
n  Quantos ponteiros são necessários para se 
percorrer uma árvore binária completamente? 
n  Quantos são necessários para percorrer 
qualquer tipo de árvore? 
31 
Árvores binárias 
n  Representação estática e sequencial de árvores binárias 
n  Vetor 
n  Como colocar a árvore abaixo nesse vetor? 
0 6 
32 
Árvores binárias 
n  Representação estática e sequencial de árvores binárias 
n  Vetor 
n  Como colocar a árvore abaixo nesse vetor? 
C B A 
0 6 
33 
Árvores binárias 
n  Representação estática e sequencial de árvores binárias 
n  Vetor 
n  Como colocar a árvore abaixo nesse vetor? 
C B A G D 
0 6 
34 
Árvores binárias 
n  Representação estática e sequencial de árvores binárias 
n  Vetor 
n  Como colocar a árvore abaixo nesse vetor? 
C B A G D F E 
0 6 
35 
Árvores binárias 
n  Representação estática e sequencial de árvores binárias 
n  Como saber quem é filho de quem? 
C B A G D F E 
0 6 
36 
1 2 3 4 5 
Árvores binárias 
n  Representação estática e sequencial de árvores binárias 
n  Como saber quem é filho de quem? 
n  Filhos de i são 2i+1 e 2i+2 
37 
C B A G D F E 
0 6 1 2 3 4 5 
Árvores binárias 
n  Representação estática e sequencial de árvores binárias 
n  Como saber quem é filho de quem? 
n  Filhos de i são 2i+1 e 2i+2 
n  E o pai? 38 
C B A G D F E 
0 6 1 2 3 4 5 
Árvores binárias 
n  Representação estática e sequencialde árvores binárias 
n  Como saber quem é filho de quem? 
n  Filhos de i são 2i+1 e 2i+2 
n  E o pai? (i-1) div 2 
n  div: divisão de inteiros 
39 
C B A G D F E 
0 6 1 2 3 4 5 
Árvores binárias 
n  Exercício: represente a árvore abaixo em um vetor 
n  O que essa árvore representa? 
40 
Árvores binárias 
n  Questões: considerando a representação estática e 
sequencial de árvores binárias 
n  Como fazer a inserção e remoção de elementos nessa 
representação? 
n  É mais fácil ou difícil do que na implementação 
encadeada e dinâmica? 
n  E em termos de uso da memória? 
41 
Operações em árvores binárias 
n  Algumas operações do TAD 
n  Criar árvore 
n  Verificar se a árvore está vazia 
n  Buscar um elemento 
n  Exercício para entregar na próxima aula 
§  Buscar pai de um elemento 
42