Algoritmos e estrutura de dados Árvores

Prévia do material em texto

AED 
Algoritmos e Estruturas de Dados
LEEC - 2005/2006
Árvores
AED (IST/DEEC) 2
Árvores - Introdução (1)
• As árvores são estruturas de dados usadas em diversas 
aplicações na vida comum:
– Bases de dados de grande dimensão.
– Reconhecimento de frases geradas por linguagens (ex: programas, 
expressões aritméticas,...).
– Modelação de sistemas organizacionais (ex: famílias, directórios de um 
computador, hierarquia de comando de uma empresa,...).
– Determinação do caminho mais curto entre dois computadores de uma 
rede.
AED (IST/DEEC) 3
Árvores - Introdução (2)
• Def: Uma árvore é um caso especial de um grafo, i.e., um par 
(V,E) de dois conjuntos não vazios V-nós (vertex) e E Í V2
arestas (edges) que satisfazem duas condições:
– Entre dois nós existe um único caminho (um caminho (path) é uma 
sequência de arestas entre dois nós),
– Um único nó, denominado raíz (root), só existe como primeiro elemento 
nos pares de E: os restantes nós são um segundo elemento dos pares de E 
(podendo também ser primeiro elemento de alguns pares).
Nota: a existência de uma raíz é útil em muitas aplicações mas não é essencial 
para a definição anterior. Este tipo de árvores é também denominada árvores 
com raíz (rooted tree).
AED (IST/DEEC) 4
Árvores - Introdução (3)
• Def: se (v1,v2) Î E, v1 é nó ascendente (parent) e v2 é nó filho
(child).
– A raíz é o único nó sem ascendente.
– Nós sem filhos são designados por folhas (leaves).
– Nós com filhos são designados não-terminais. Nós não-terminais, distintos da 
raiz, são designados intermédios.
• Def: A árvore é de tipo K, sse todos os nós intermédios tiverem K
filhos. Quando K=2, a árvore diz-se binária.
• Def: O nível (level) de um nó é o número de arestas entre a raíz e o 
nó (a raíz tem nível 0). A altura (heigth) de uma árvore é o máximo 
número de nós encontrados nos caminhos até às folhas (uma árvore 
só com a raiz tem altura 1).
AED (IST/DEEC) 5
Árvores - Introdução (4)
Representação gráfica das árvores adopta a convenção:
– raíz no topo,
– nós representados por círculos,
– arestas representadas por linhas (ou setas no sentido da raíz para a folha).
Exemplo A1: directórios do sistema operativo Linux
/
bin dev etc home
cfb lmv rgc
usr var
AED (IST/DEEC) 6
Árvores - Introdução (5)
2+3*5
V={n1,n2,n3,n4,n5}
E={(n1, n2),(n1,n3),(n3,n4),(n3,n5)}
(2+3)*5
• A árvore é avaliada de forma ascendente (bottom-up): 2+3*5 = 2+15 = 17
• Parêntesis, usados nas expressões aritméticas para ultrapassar as prioridades dos 
operadores, são indicados na árvore através da posição dos nós.
Exemplo A2: expressões aritméticas
+
2 *
3 5
n1
n2 n3
n4 n5
*
5+
2 3
raiz
folha
AED (IST/DEEC) 7
Árvores - Introdução (6)
• Exemplo A3: árvore (ordenada) de pesquisa binária1
•Subárvore direita (esquerda) armazena números maiores (menores) 
que o nó. Se os dados forem cadeias de caracteres, usa-se a ordem 
lexicográfica (cf>cb e cf>az ).
– Vantagens: pesquisa mais rápida-O(log N)
– Inconvenientes: pode degenerar lista com pesquisa-O(N), a resolução deste 
problema torna inserção mais complicada
1 BST - Binary Search Tree
n
<n >n2
17
31
5
12
8
AED (IST/DEEC) 8
Árvores - Introdução (7)
Uma árvore de tipo K pode ser transformada numa árvore binária, com
– referências esquerdas contêm sucessivamente as sub-árvores da árvore K
– referências direitas contém referência para a parte restante da árvore K
Exemplo A4: transformação de uma árvore ternária numa árvore 
binária
a b c
Þ
a
b
c
AED (IST/DEEC) 9
Árvores - Introdução (8)
As árvores BB possuem, em cada nó, uma tabela para as sub-
árvores. São usadas em Bases de Dados.
a b c
A B C D
A < a < B < b < C < c < D
Todos os caminhos da raiz para as folhas possuem o mesmo comprimento
AED (IST/DEEC) 10
Árvores - Introdução (9)
Em AED/LEEC são estudadas apenas árvores BST(binary search tree):
– Representação de uma árvore binária em C
– Propriedades
– Operações:
• Inserção de um elemento numa árvore
– Directa
– Balanceada
• AVL
• RB
• Combinação de duas árvores
• Retirada de um elemento
• Percurso de uma árvore
AED (IST/DEEC) 11
Árvores - Representação em C
Seja a definição em C de uma árvore binária, contendo cada nó um 
dado de tipo Item.
typedef … data;
typedef struct _s1 {
Item data; /* dados */
struct _s1 *left, *right; /* referência filhos */
} node;
node *root = NULL; /* raíz (árvore inicial é vazia) */
AED (IST/DEEC) 12
••••••
Árvores - Propriedades (1)
Teorema A1: Uma árvore binária com N nós não-terminais possui N+1 folhas.
Estratégia de prova: indução, com base na construção da árvore a partir de duas 
subárvores.
– Se N=0, a árvore possui um único nó (que é raiz e folha em simultâneo).
– Seja N>0 o número de nós não-terminais: a subárvore esquerda
tem k nós, a subárvore direita tem N-k-1 nós (0<k<N+1).
Por hipótese, a subárvore esquerda tem k+1 folhas
e a subárvore direita tem N-k folhas.
Somando, a árvore tem (k+1)+(N-k)=N+1 folhas.
QED
•
••••••
k N-k-1
AED (IST/DEEC) 13
Árvores - Propriedades (2)
Teorema A2: Uma árvore binária com N nós não-terminais possui 2N arestas (N-1 para 
os nós não-terminais e N+1 para as folhas).
Estratégia de prova: contar o número de arestas para cada nó.
– Exceptuando a raiz, cada nó possui um único ascendente, pelo que só há uma 
aresta entre um nó e o seu ascendente.
– Pelo teorema A1 e observação anterior, há N+1 arestas para as folhas. Pelas duas 
observações anteriores, há N-1 arestas para os nós intermédios. No total, a árvore 
com N nós não-terminais possui (N+1)+(N-1)=2N arestas.
QED
AED (IST/DEEC) 14
Árvores - Propriedades (3)
Teorema A3: Numa árvore binária com N nós, o nível das folhas hl varia entre ëlog2Nû e 
N-1.
Estratégia de prova: identificar níveis máximo e mínimo.
– O nível máximo é o da árvore degenerada numa lista.
Neste caso, hl=N-1 arestas.
– O nível mínimo é o da árvore balanceada, cada nível
i com 2i nós. Por A1 há N+1 folhas, logo 2hl-1<N+1£2hl. 
Assim, hl é o maior inteiro igual ou inferior a log2N
(ex: ëlog27û = 2, ëlog28û = 3)
QED
•
• •
• • • •
•
•
•
•
AED (IST/DEEC) 15
• Introdução às árvores
• Representação em C
• Propriedades básicas de árvores
Síntese da Aula 1 de Árvores
AED (IST/DEEC) 16
Árvores - Inserção (1)
• Sendo as árvores recursivas, as funções de manipulação podem 
ser recursivas: a instrução recursiva é aplicada nos nós 
intermédios e a instrução terminal nas folhas.
• As árvores são, usualmente, construídas de forma descendente 
(top-down).
Nos algoritmos de inserção consideramos o item um inteiro 
(typedef int Item;) e uma árvore BST. Se a informação 
a armazenar for uma estrutura, um dos campos designado chave
(key) tem de ser tipo ordenado. Ex: no bilhete de identidade, a 
chave é o número do BI.
AED (IST/DEEC) 17
Árvores - Inserção (2)
Inserção directa
A inserção efectuada em dois casos, conforme situação da árvore:
– vazia: insere directamente novo dado
– não vazia: procura, em primeiro lugar, o nó onde inserir o novo dado
node *insert(int i, node *tree) {
node *upper = tree, *child = tree, *leaf;
if (tree == NULL) { /* árvore vazia */
tree = (node *) malloc(sizeof(node));
tree->data = i; /* insere dado */
tree->left = tree->right = NULL; /* sub-árvores vazias */
return tree;
}
AED (IST/DEEC) 18
Árvores - Inserção (3)
while (child != NULL){/* procura nó onde inserir dado */
upper = child;
if (child->data == i) return tree; /* já existe! */
child = (child->data > i) ? child->left : child->right;}
/* criada e inicializada nova folha */
leaf = (node *) malloc(sizeof(node));
leaf->data = i; 
leaf->left = leaf->right = NULL;
/* upper passa a nó intermédio e aponta para nova folha */
if (upper->data > i) upper->left = leaf;
else upper->right = leaf;
return tree; 
}
/* rotina insert retorna nova árvore (i.e. ponteiro para raíz), porque a inicial foi alterada */
AED (IST/DEEC) 19
Árvores - Inserção (4)
Exemplo A5: inserção de 7 na árvore do exemplo A3
i) 7 < 12: insere na sub-árvore esquerda.
ii) 7 > 5: insere na sub-árvoredireita.
iii) 8 é folha:
– cria nova folha.
– 7 < 8: a nova folha é sub-árvore 
esquerda.
O algoritmo degenera numa lista, se os dados inseridos forem 
sucessivamente crescentes (ou sucessivamente decrescentes). 
5
2
17
8
12
7
i
ii
iii
31
AED (IST/DEEC) 20
Árvores - Inserção (5)
A complexidade da inserção depende do tipo de árvore:
• Árvore degenerada (lista): O(N)
• Árvore perfeitamente balanceada: complexidade determinada pela 
pesquisa do local de inserção ëlog2Nû, ou seja, O(log N)
• Árvore de inserção aleatória: considerando que a altura de cada sub-
árvore possui uma distribuição uniforme 1..N, tem-se que a pesquisa 
do local de inserção custa ln N, ou seja, O(log N)
AED (IST/DEEC) 21
Árvores - Inserção (6)
Estratégia de prova: simplesmente, efectuar os cálculos!
O custo é 1 (visita à raiz) somado ao custo da visita à sub-árvore: esta pode ter 
entre 0 e N-1 nós, com distribuição uniforme
• CN = 1 + 1/N * S Ck-1 1 £ k £ N, para N ³ 2
C1 = 1
Para eliminar S, multiplica-se ambos os lados por N, e subtrai-se a fórmula 
para N-1 (nota: k varia até N nos dois S)
NCN - (N-1)CN-1 = N + SCk-1 – (N-1 + SCk-2 ) = 1 + CN-1
NCN = NCN-1 +1
CN = CN-1 + 1/N
AED (IST/DEEC) 22
Árvores - Inserção (7)
por substituição telescópica
CN = C1 + 1/N + 1/(N-1) + ... + 1/2
Trata-se da série harmónica, pelo que
CN » ln N + g + 1/12N
QED
Conclusão: o custo da inserção é mínimo se a árvore for 
balanceada
… O problema reside na maior dificuldade em manter a árvore 
balanceada (como se vai ver nos acetatos seguintes)
AED (IST/DEEC) 23
Árvores balanceadas AVL (1)
• Def: Uma árvore diz-se balanceada AVL2, sse em todos os nós 
a diferença entre as alturas das subárvores for igual ou inferior a 
1.
Exemplo A6: árvore A3 é balanceada, A4 já não é (subárvore 
esquerda tem altura 2 e direita tem altura 4).
Para manter a árvore balanceada, respeitando a ordem, depois da 
inserção pode ser necessário rodar a configuração de nós 
(rotação simples e rotação dupla)
2Adel’son-Vel’skii e Landis
AED (IST/DEEC) 24
Rotação à direita
Rotação à esquerda
Árvores balanceadas AVL (2)
Operações de rotação são classificadas de acordo com o sentido (à
direita e à esquerda).
y
x y
x
Quando a diferença de alturas for igual a 2, a operação de rotação 
diminui o nível da folha mais afastada da raiz, mantendo a 
ordenação da árvore.
a
a
b b
g
g
AED (IST/DEEC) 25
Árvores balanceadas AVL (3)
A função de rotação apenas actualiza ponteiros (b é a única subárvore a mudar de ascendente). 
Assim, a rotação tem complexidade O(1).
node *rotate_right(node * tree) {
node *x, *y, *beta;
/* inalterada se árvore vazia, ou subárvore esquerda vazia */
if (tree == NULL) return tree;
else if (tree->left == NULL) return tree;
/* salva ponteiros */
y = tree; x = tree->left; beta = x->right;
/* actualiza ligações */
x->right = y; y->left = beta;
return x;
}
AED (IST/DEEC) 26
Árvores balanceadas AVL (4)
Há dois pares de casos em que se torna necessário rodar subárvores:
1: Rotação simples (à direita)
h+1
h
x
y
h+1
h
x
y
A1 A2
A3 A1
A2 A3
h
AED (IST/DEEC) 27
Árvores balanceadas AVL (5)
2: Rotação dupla (à direita)
h
h
y
x
z
z
h
xy
A2 ou A3 de altura h
A1 A1
A2
A2
A3
A3
A4
A4
AED (IST/DEEC) 28
Árvores balanceadas AVL (6)
Código de inserção AVL
int height(node *tree) {
int hl, hr;
if (tree == NULL) return 0;
if (tree->left == NULL && tree->right == NULL)
return 1;
hl = height(tree->left); hr = height(tree->right);
return ((hl>hr) ? 1+hl : 1+hr);
}
AED (IST/DEEC) 29
Árvores balanceadas AVL (7)
node *insert(int i, node *tree) {
/* tree é ponteiro para árvore: a alteração é feita directamente na
árvore que é dada como parâmetro */
int h1, h2, h3;
if (tree == NULL) { /* árvore vazia */
tree = (node*) malloc(sizeof(node));
tree->data = i; 
tree->left = tree->right = NULL;
return tree;
}
AED (IST/DEEC) 30
Árvores balanceadas AVL (8)
if (i == tree->data) return tree; /* já instalado */
if (i < tree->data){ /* insere na sub-árvore esquerda */
tree->left = insert(i, tree->left);
h1 = height(tree->left->left);
h2 = height(tree->left->right);
h3 = height(tree->right);
if (h1 > h3) /* Caso 1, rotação simples à direita */
tree = rotate_right(tree);
if (h2 > h3) { /* Caso 2, rotação dupla à direita */
tree->left = rotate_left(tree->left);
tree = rotate_right(tree); } }
AED (IST/DEEC) 31
Árvores balanceadas AVL (9)
else {/* insere na sub-árvore direita */
tree->right = insert(i, tree->right); 
h1 = height(tree->right->right);
h2 = height(tree->right->left);
h3 = height(tree->left);
if (h1 > h3) /* Caso 1, rotação simples à esquerda */
tree = rotate_left(tree);
if (h2 > h3) {/* Caso 2, rotação dupla à esquerda */
tree->right = rotate_right(tree->right);
tree = rotate_left(tree); } }
retun tree;
}
AED (IST/DEEC) 32
Árvores balanceadas AVL (10)
• O algoritmo AVL não garante distribuição total pelos níveis 
intermédios (por exemplo, na série S0+(-1)nn, a sub-árvore 
esquerda só deriva à esquerda e a sub-árvore direita só deriva à
direita).
• O algoritmo de inserção listado é pesado devido à determinação 
das alturas. Uma versão mais eficiente (embora mais complexa 
e ocupando mais memória), guarda em cada nó o balanceamento 
das sub-árvores (maior à esquerda, iguais ou maior à direita).
AED (IST/DEEC) 33
• Inserção de elementos
• Árvores balanceadas AVL
Síntese da Aula 2 de Árvores
AED (IST/DEEC) 34
Árvores balanceadas RB (1)
• Def: Uma árvore balanceada RB3 é uma BST, em que:
– Todos os nós possuem uma cor: Vermelha , Negra.
– A raiz e todas as folhas são negras.
– Filhos dos nós vermelhos são negros.
– Todos os caminhos, da raiz às folhas, possuem o mesmo número de nós 
negros (diferenças do número de nós vermelhos inferior a 2)
Nota: nos grafos, ponteiros nulos
considerados como folhas negras
3 Red Black
AED (IST/DEEC) 35
Árvores balanceadas RB (2)
Código de inserção RB
1 Inserir directamente, como nó vermelho.
2 Há 3 alterações possíveis.
Se a alteração quebrar as regras das árvores RB, então rodar e 
recolorir em direcção à raiz.
A inserção custa O(log N).
AED (IST/DEEC) 36
Árvores balanceadas RB (3)
A Se inserir como raiz, passar nó a negro. 
B Se o nó ascendente for negro, terminar.
novo nó
AED (IST/DEEC) 37
Árvores balanceadas RB (4)
C Se o nó ascendente for vermelho, rodar duplamente e actualizar cores do 
pai/mãe, avô/avó e tio/tia
x
novo nó
y z
w a b g
novo nó
x
y z
w a b g
y
xw
z
b g
a
y
xw
z
b g
a
Pode ter de recolorir 
em cima
AED (IST/DEEC) 38
Árvores balanceadas RB (5)
novo nó
y z
a
b g
w
y
z
a b g
wx
x
Codificação pode ser feita de 2 formas:
• Cada nó possuir ponteiro para o nó pai/mãe
• Recursivamente (muito complicado!)
AED (IST/DEEC) 39
Árvores - Combinação (1)
Combinação permite juntar, numa única árvore, duas árvores (cada 
uma com dados parciais)
– Se uma das árvores é nula, a combinação é apenas a outra árvore.
– Senão, insere-se os elementos da primeira na segunda.
node *join(node *a, node *b) {
if (a == NULL) return b;
if (b == NULL) return a;
b = insert(a->data, b);
b = join(a->left, b); /* Sedgewick tem join(a->left,b->left); */
b = join(a->right, b);/* Sedgewick tem join(a->right,b->right); */
free(a);
return b;}
AED (IST/DEEC) 40
Árvores - Combinação (2)
Solução proposta por Sedgewick (Prog 12.16) incorrecta!
– Fazer join , logo nas sub-árvores esquerda e direita, impede verificar o 
mesmo dado em nós de alturas distintas!
10
0 20
30
-10
0
+ Þ
10
20
30
-10
0
+ Þ
0
0
+
10
20
30
0 Þ
10
20
30
0
-10
Errado!!!
0
-10
AED (IST/DEEC) 41
Árvores - Retirada
Um dado é eliminado da árvore, executando os passos
– Procurar o nó de residência
– Se existir, executar:
• Combinar sub-árvores esquerda e direita
• Substituir nó pelo resultado da combinação
node *delete(int i, node *tree) {
node *aux = tree;
if (tree == NULL) return NULL;
if(i < tree->data) tree->left = delete(i, tree->left);
if(i > tree->data) tree->right = delete(i, tree->right);
if(i == tree->data) {
tree = join(tree->left, tree->right);
free(aux); }
return tree;}
AED (IST/DEEC) 42
Árvores - Varrimento (1)
Existem diversas estratégias de percurso/varrimento (transverse) 
de árvores:
1 De acordo com o operador, existente em todos os nós que não sejam 
folhas (percurso também designado por dump)
• Pré-fixado: antes do varrimento das sub-árvores.
• In-fixado: varrer primeiro sub-árvore esquerda, imprimir operador e varrer 
depois a sub-árvore direita.
• Pós-fixado4: depois do varrimento das sub-árvores.
2 De acordo com o nível
• Profundidade (depth-first)
• Largura (breadth-first)
4 também conhecido por notação polaca invertida
AED (IST/DEEC) 43
Árvores - Varrimento (2)
1: De acordo com o operador
As subárvores são varridas de forma ordenada e o operador é
listado de forma pré-determinada (pré-fixado, in-fixado ou pós-
fixado)
Exemplo A7: percurso pós-fixado da árvore aritmética A2
typedef struct {
enum {nod, leaf} node_type;
union {
enum {plus, times} oper;
int value; } info;
} Item;
AED (IST/DEEC) 44
Árvores - Varrimento (3)
void postfix (node *tree){
if (tree == NULL) return;
switch(tree->data.node_type) { 
case leaf: /* imprime o valor */
printf(“ %d”, tree->data.info.value);
break;
case nod: /* imprime sub-árvores esquerda e direita */
postfix(tree->left); postfix(tree->right);
switch(tree->data.info.oper) { /* imprime oper */
case plus: printf(“ +”); break;
case times: printf(“ *”); break; }}}
AED (IST/DEEC) 45
Árvores - Varrimento (4)
o resultado final é: 2 3 5 * +
n1
n2 n3
2 n4
3
n5
5
*
+
+
2 *
3 5
n1
n2 n3
n4 n5
AED (IST/DEEC) 46
Árvores - Varrimento (5)
2: De acordo com o nível
• Profundidade: idêntico ao varrimento pré-fixado
void depth_first (node *tree){
if (tree ==NULL) return;
printf(“ %d”, tree->data);
depth_first(tree->left);
depth_first(tree->right); }
2
17
31
5
12
8
Exemplo A8: O varrimento em profundidade da árvore A3 executa 
a seguinte sequência de passos:
(a) elemento da raiz: 12
(b) visita em profundidade sub-árvore esquerda: 5 2 8
(c) visita em profundidade sub-árvore direita: 17 31.
O resultado é 12 5 2 8 17 31
AED (IST/DEEC) 47
Árvores - Varrimento (6)
• Largura: O varrimento é feito por nível. As sub-árvores são 
colocadas no fim de uma lista.
typedef struct _s2 {
node *this;
struct _s2 *next; 
} link;
link *New(); /* cria lista vazia */ 
void InsertLast(link *, node *);/* insere no fim da lista */
link *GetFirst(link *);/* obtém primeiro elemento da lista */
AED (IST/DEEC) 48
Árvores - Varrimento (7)
void breadht_first (link *list){
if (list == NULL) return;
else {
link * aux = GetFirst(list);
printf(“ %d”, aux->this->data);
InsertLast(list, aux->this->left);
InsertLast(list, aux->this->right);
breadht_first(list); } 
}
Rotina deve ser chamada com a raiz inserida na lista.
breadht_first(InsertLast(New(), root));
AED (IST/DEEC) 49
Árvores - Varrimento (8)
Exemplo A9: varrimento em largura da árvore A3
Lista Acção Saída
[12] Recolhe 1º elemento
Imprime valor 12
[5, 17] Insere subárvores esq e dir
[17] Recolhe 1º elemento
Imprime valor 5
[17,2,8] Insere subárvores esq e dir
[2,8] Recolhe 1º elemento
Imprime valor 17
[2,8,31] Insere subárvores esq e dir
[8,31] Recolhe 1º elemento
Imprime valor 2
Insere subárvores esq e dir
[31] Recolhe 1º elemento
Imprime valor 8
Insere subárvores esq e dir
[] Recolhe 1º elemento
Imprime valor 31
Insere subárvores esq e dir
2
17
31
5
12
8
AED (IST/DEEC) 50
• Árvores balanceadas RB
• Combinação de árvores
• Retirada de elementos
• Varrimento de árvores
Síntese da Aula 3 de Árvores