Estrutura de Dadoswiki.cbatista.net/lib/exe/fetch.php/ed-aula13-arvores_pt... · 2014-03-19 · O...

Estrutura de Dados Carlos Eduardo Batista

Centro de Informática - UFPB

bidu@ci.ufpb.br

Estruturas de Dados

Árvores (parte 3)

2

Árvores

Organização dos dados: ◦ Linear:

Listas, pilhas, filas.

Relação sequencial.

◦ Não-linear:

Outros tipos de relação entre dados;

Hierarquia;

Árvores

Grafos.

3

Árvores

Estrutura não-linear que representa uma relação de hierarquia

Exemplo:

◦Árvore de diretórios;

◦Árvore genealógica.

4

Árvores

Caracterização de uma árvore: ◦ Composta por um conjunto de nós

◦ Existe um nó r, chamado nó raiz

Este nó contém zero ou mais sub-árvores, cujas raízes são ligadas diretamente a r

Os nós raízes das sub-árvores são ditos filhos do nó pai r ◦ “Nós” que não têm filhos são chamados de folhas

É tradicional desenhar as árvores com a raiz para cima e folhas para baixo

5

Árvores 6

raiz

A B C D …

Sub-árvores do

nó raiz

Filhos de C Filhos de A

Árvores

O número de sub-árvores de um nó determina o “grau de saída“ desse nó. Ou seja, a quantidade de filhos.

Grau Máximo, ou grau da árvore ◦ Maior grau de seus nós.

Nós que não tem grau (grau == 0), são denominados de nó folha

Para identificar os nós de uma estrutura, usamos a relação de hierarquia existente em uma árvore genealógica ◦ Filho, pai, neto, irmão

7

Árvores

Nível ◦ Representa a distância de um nó até a raiz

◦ O nó de maior nível nos fornece a altura

◦ Só existe um caminho da raiz para qualquer nó

8

nível 0

nível 1

nível 2

nível 3

Árvores

Árvore cheia ◦ Árvore com número máximo de nós.

◦ Uma árvore de grau d tem número máximo de nós se cada nó, com exceção das folhas, tem grau d.

9

Árvores Binárias

◦Tipo de árvore em que seus nós possuem no máximo duas sub-árvores

Árvore de grau máximo igual a 2

◦As duas sub-árvores de cada nó são denominadas:

sub-árvore esquerda

sub-árvore direita

Árvore binária completa

◦Árvore em que cada nó possui dois filhos, exceto o nó folha.

10

Árvores Binárias

11

A

B C

D E F

G

Nivel 1

Nivel 2

Nivel 3

Raízes das sub-árvores

Raiz

Esquerda Direita

Grau máximo: 02

Folhas

Árvores Binárias

A maioria das funções de manipulação de árvores são implementadas de forma recursiva

Que operações serão necessárias? Criação/Iniciliazação da árvore Cria nó raiz Árvore vazia Imprimir a árvore Inserir filho esquerdo Inserir filho direito Remover um determinado nó

12

Árvores Binárias

Percurso ◦Um percurso define a ordem em que os nós de uma árvore serão processados

Tipos de percurso: ◦Pré-ordem Utiliza o nó

Percorre a sub-árvore esquerda

Percorre a sub-árvore direita

◦In-ordem Percorre a sub-árvore esquerda

Utiliza o nó

Percorre a sub-árvore direita

13

Árvores Binárias 14

A

B C

D E GF

Pré-ordem:

In-ordem

Pós-ordem

ABDECFG

DBEAFCG

DEBFGCA

Árvores binárias de pesquisa

1. Todas as chaves da subárvore esquerda são menores que a chave da raiz.

2. Todas as chaves da subárvore direita são maiores que a chave raiz.

3. As subárvores direita e esquerda são também Árvores Binárias de Busca.

15

Árvores binárias de pesquisa 16

Árvores binárias de pesquisa

Solução para implementação da busca binária encadeada.

Busca binária sequencial: ◦ Cada comparação na busca binária reduz o número de possíveis candidatos por uma fator de 2. Sendo assim, o número máximo de comparações da chave é aproximadamente log2N.

Árvore binária de pesquisa: ◦ Quando a árvore tem altura mínima possui o mesmo comportamento.

17

Árvores binárias de pesquisa

Implementação: ◦ Mudança nos métodos:

Busca (pesquisa);

Inserção

Remoção

Exibição só in-ordem

18

Árvores binárias de pesquisa 19

t_no * busca(t_arvore tree, t_elemento dado)

{

t_no* achou;

if (tree == NULL)

return NULL;

if (compara(tree->dado, dado)==0)

return tree;

achou = busca(tree->esq, dado);

if (achou == NULL)

achou = busca(tree->dir, dado);

return achou;

}

Árvores binárias de pesquisa 20

t_no * busca(t_arvore tree, t_elemento dado)

{

if (tree == NULL)

return NULL;

if (compara(tree->dado, dado)==0)

return tree;

if (compara(tree->dado, dado)>0)

return busca(tree->esq, dado);

else

return busca(tree->dir, dado);

}

Árvores binárias de pesquisa 21

t_no * buscaSetPai(t_arvore tree, t_elemento dado, t_no ** pai)

{

if (tree == NULL) {

*pai = NULL;

return NULL;

}

if (compara(tree->dado, dado)==0)

return tree;

if (compara(tree->dado, dado)>0) {

*pai = tree;

return buscaSetPai(tree->esq, dado, pai);

}

else {

*pai = tree;

return buscaSetPai(tree->dir, dado, pai);

}

}

Árvores binárias de pesquisa 22

int inserir (t_arvore *tree, t_elemento item)

{

int ok;

// se a raiz for nula, entao insere na raiz

if (*tree == NULL) {

*tree = criar();

if (*tree == NULL)

return 0;

(*tree)->dado = item;

return 1;

}

if (compara((*tree)->dado, item)<0)

ok = inserir (&((*tree)->dir), item);

else

if (compara((*tree)->dado, item)>0)

ok = inserir (&((*tree)->esq), item);

else

ok = 0;

return ok;

}

Árvores binárias de pesquisa

Remoção ◦ Nó a ser removido não possui filhos:

Remove-se o nó e a ligação do pai com o filho é anulada.

◦ Nó a ser removido possui apenas 1 filho:

Remove-se o nó e o pai passa a apontar para o ex-neto, que agora vira filho.

◦ Nó a ser removido possui dois filhos:

Obtém-se o sucessor do nó. O sucessor vai para o lugar do no a ser excluído. O pai do sucessor, aponta agora para o ex-neto. O sucessor->dir passa a apontar para onde o no->dir apontava.

23

Árvores binárias de pesquisa 24

Árvores binárias de pesquisa

Sucessor: ◦ Menor nó do conjunto de nós maiores que o nó atual.

Antecessor: ◦ Maior nó do conjunto de nós menores que o nó atual.

25

Árvores binárias de pesquisa 26

int remover (t_arvore *tree, t_elemento item) {

t_no *no, // no aponta para o no a ser removido

*pai, // pai aponta para o pai do no

*sub, // sub aponta que ira substituir o no no

*paiSuce, // pai do no sucessor

*suce; // sucessor do no no

no = *tree; pai=NULL;

no = buscaSetPai(*tree, item, &pai); // procura o no a ser removido, e seta o seu pai.

if (no==NULL)

return 0; // a chave nao existe na arvore, nao conseguiu remover

if (no->esq == NULL) // ver os dois primeiros casos, o no tem um filho no maximo

sub = no->dir;

else {

if (no->dir == NULL)

sub = no->esq;

else { // caso em que o no tem dois filhos

}}

// insere sub na posicao ocupada anteriormente por no

if (pai == NULL) // no eh a raiz, nao tem pai

*tree = sub;

else // verifica se o no eh o filho da esquerda ou da direita

if (no == pai->esq)

pai->esq = sub;

else

pai->dir = sub;

free(no); // libera o no

return 1; // verdadeiro, conseguiu remover

}

Árvores binárias de pesquisa 27

else { // caso em que o no tem dois filhos

paiSuce=no;

sub = no->dir;

suce = sub->esq; // suce eh sempre o filho esq de sub

while (suce != NULL) {

paiSuce = sub;

sub = suce;

suce = sub->esq;

}

// neste ponto, sub eh o sucessor em ordem de no

if (paiSuce != no) {

// no nao e o pai de sub, e sub == paiSuce->esq

paiSuce->esq = sub->dir;

// remove o no sub de sua atual posicao e o

// substitui pelo filho direito de sub

// sub ocupa o lugar de no

sub->dir = no->dir;

}

// define o filho esquerdo de sub de modo que sub

// ocupe o lugar de no

sub->esq = no->esq;

}

Árvore binária estrita

Todo nó não folha possui filhos a esquerda e a direita = Árvore Binária Estrita

Uma árvore binária estrita com n folhas sempre contém 2n-1 nós

28

Árvores binárias

Árvore binária cheia de nível d: árvore binária estrita com todas as folhas no nível d

Árvore binária completa de nível d: uma árvore binária estrita com todas as folhas no nível d ou no nível d-1

29

Árvores binárias 30

D E

B

H I

F G

C

A

H I

D

J K

E

B

L M

F

N O

G

C

A

Completa Cheia

Árvores binárias

O total de nós n em uma árvore binária cheia de altura d é a soma do número de nós a cada nível

n = 20 + 21 + 22 + ..... + 2d = Ʃ 2j

n = 2d+1 -1 d = log (n+1) –1

número de folhas de uma árvore cheia com n nós

2d = 2log(n+1)-1 = 2log(n+1) = n+1 2 2

31

Árvores binárias 32

H I

D

J K

E

B

L M

F

N O

G

C

A

Árvore Binária Cheia de altura 3 23+1-1 = 15 nós

Árvores binárias

Seja T uma árvore binária completa com n nós, então sua altura h = log2n

Seja T’ a árvore obtida pela remoção dos k nós do último nível

T’ é cheia já que T só tinha folhas no último e no penúltimo nível (definição de completa)

nós de T’

n’ = n - k = 2d +1 -1 , onde d é a altura de T’

33

Árvores AVL

Os algoritmos convencionais podem gerar árvores degeneradas ou ótimas ◦ Árvores de crescimento irrestrito

Árvores AVL (Adelson-Velskki & Landis) ◦ Árvores de busca binária auto-balanceada ◦ Nesse tipo de árvore, as alturas das duas sub-

árvores a partir de cada nó difere no máximo em uma unidade.

◦ Mesmo depois de inclusões e exclusões o custo se mantem O (log n) onde n é o numero de nós

◦ Inserções e eliminações podem requerer o rebalanceamento da árvore, exigindo uma ou mais rotações.

34

Árvores AVL 35

Árvores AVL

Dizemos que uma árvore está balanceada em altura (ou profundidade) quando, para cada nó, a diferença entre as alturas de suas sub-árvores é igual a -1, 0 ou 1.

36

Árvores AVL 37

Árvores AVL

Fator de equilíbrio de um nó

Fe(A) = hEsq – hDir

Fe(A) = 2 – 3 = -1

Fe(C) = 2 – 1 = 1

AVL Fe(N) {-1, 0, +1}; N

38

Árvores AVL

Fe(A) = 2 – 3 = -1 Fe(B) = 1 – 1 = 0 Fe(C) = 2 – 1 = 1 Fe(D) = 0 – 0 = 0 Fe(E) = 0 – 0 = 0 Fe(F) = 1 – 1 = 0 Fe(G) = 0 – 0 = 0 Fe(H) = 0 – 0 = 0 Fe(I) = 0 – 0 = 0

39

Árvores AVL 40

Com base na tabela acima, se tivéssemos 1.048.575 elementos, poderíamos armazená-los em uma árvore binária perfeitamente balanceada com 20 níveis. Em outras palavras, poderíamos localizar um elemento qualquer dentro dessa árvore com apenas 20 comparações.

Árvores AVL

O que pode acontecer quando um novo nó é inserido numa árvore balanceada ?

Dada uma raiz r com subárvores L (left) e R (right), e supondo que a inserção deve ser feita na sub-árvore da esquerda. Podemos distriguir 3 casos: ◦ Se hL = hR, então L e R ficam com alturas

diferentes mas continuam balanceadas. ◦ Se hL < hR, então L e R ficam com alturas iguais e

balanceamento foi melhorado. ◦ Se hL > hR, então L fica ainda maior e

balanceamento foi violado.

41

Árvores AVL

Inserindo em H ou I, dois casos ◦ Em H: Fe(F) = 1, Fe(C) = 2, F(A) = -2

◦ Em I: Fe(F) = -1, Fe(C) = 2, F(A) = - 2

Inserir e depois rotacionar visto ser necessário alguns ajustes, tal que: ◦ Continue ABB

◦ Continue balanceada

42

Árvores AVL

Rotação simples ◦ Uma rotação simples ocorre quando um nó está desbalanceado e seu filho estiver no mesmo sentido da inclinação, formando uma linha reta.

Rotação dupla ◦ Ocorre quando um nó estiver desbalanceado e seu filho estiver inclinado no sentido inverso ao pai, formando um “joelho”.

43

Árvores AVL

Rebalanceamento mapeado em dois casos ◦ Raíz (2|-2) e filho (1|-1) com o mesmo sinal

Rotação simples do nó com |Fe| = 2 na direção correta

◦ Raíz (2|-2) com um sinal e filho(-1|1) com outro

Rotação do nó com |Fe| = 1 na direção correta

Rotação do nó que tinha |Fe| = 2 na direção oposta

44

Árvores AVL

Rotação à direita ◦ Numa árvore binária basta empurrar o nó N para baixo e para a direita. O filho à esquerda de N o substitui, e o filho à direita do filho à esquerda vem a ser o novo filho à esquerda de N. Segue pseudocódigo:

Seja Y o filho à esquerda de X

Torne X o filho à direita de Y

Torne o filho à direita de Y o filho à esquerda de X.

45

Árvores AVL

Rotação à esquerda ◦ Em uma árvore binária, basta empurrar o nó N para baixo e para a esquerda. O filho à direita de N o substitui, e o filho à esquerda do filho à direita vem a ser o novo filho à direita de N. Segue pseudocódigo:

Seja Y o filho à direita de X

Torne X filho à esquerda de Y

Torne o filho à esquerda de Y o filho à direita de X.

46

Árvores AVL 47

Árvores AVL 48

void roda_dir(ARVORE p)

{

ARVORE q, temp;

q = p->esq;

temp = q->dir;

q->dir = p;

p->esq = temp;

p = q;

}

Árvores AVL 49

8

4

2

3

6

10

q

temp

8

9

14

q

temp

12

temp

q

p

Árvores AVL 50

8

4

2

3

6

10

p

q

temp

Árvores AVL 51

8

4

2

3

6

10

p

q

temp

8

4

2

3

6

10

p

q

temp

Árvores AVL 52

8

4

2

3

6

10

Árvores AVL 53

Árvores AVL 54

55

Rotação simples à esquerda

Rotação simples à direita

56

Árvores AVL 57

Exercícios 58

Balancear

Próximas aulas

Árvores AVL (continuação)

Árvores B e B+

Heap

59

2ª. Prova – 20/03

Reposição – 25/03

Final – 27/03

2º. Trabalho – Deadline 22/03 23h59 GMT-3

60

Referências

Notas de Aula do Prof. Bruno B. Boniati

Notas de Aula do Prof. João Luís Garcia Rosa

Notas de Aula do Prof. Derzu Omaia

61

Estrutura de Dados Carlos Eduardo Batista

Centro de Informática - UFPB

bidu@ci.ufpb.br