AED Algoritmos e Estruturas de Dados

LEEC - 2006/2007

Á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 Ε ⊆ 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 Kfilhos. 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 < DTodos 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 esquerdatem 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 folhase 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, h l=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, h l é 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-árvore direita.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 * Σ Ck-1 1 ≤ k ≤ N, para N ≥ 2

C1 = 1Para eliminar Σ, multiplica-se ambos os lados por N, e subtrai-se a fórmula

para N-1 (nota: k varia até N nos dois Σ)

NCN - (N-1)CN-1 = N + ΣCk-1 – (N-1 + ΣCk-2 ) = 1 + CN-1

NCN = NCN-1 +1CN = CN-1 + 1/N

AED (IST/DEEC) 22

Árvores - Inserção (7)por substituição telescópicaCN = C1 + 1/N + 1/(N-1) + ... + 1/2Trata-se da série harmónica, pelo queCN ≈ ln N + γ + 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-V el’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.

α

α

β β

γ

γ

AED (IST/DEEC) 25

Árvores balanceadas AVL (3)A função de rotação apenas actualiza ponteiros (β é 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

yh+1

h

x

y

A1 A2

A3 A1

A2 A3h

AED (IST/DEEC) 27

Árvores balanceadas AVL (5)2: Rotação dupla (à direita)

h

hy

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 nulosconsiderados como folhas negras

3 Red Black

AED (IST/DEEC) 35

Árvores balanceadas RB (2)

Código de inserção RB1 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/tiax

novo nó

y z

w α β γ

novo nó

x

y z

w α β γ

y

xw

z

β γ

α

y

xw

z

β γ

α

Pode ter de recolorir em cima

AED (IST/DEEC) 38

Árvores balanceadas RB (5)

novo nó

y z

α

β γ

w

y

zα β γ

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 - RetiradaUm 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 A2typedef 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 * +

n1n2 n3

2 n4

3n5

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é-fixadovoid 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 A3Lista Acção Saída

[12] Recolhe 1º elementoImprime 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 2Insere subárvores esq e dir

[31] Recolhe 1º elementoImprime valor 8Insere subárvores esq e dir

[] Recolhe 1º elementoImprime valor 31Insere 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