Linguagem C: Árvores Binariaslmarti.com/wp-content/uploads/2015/12/Aula-8-Arvores-Binárias.pdf · Árvores Binarias Instituto de C. 23/04/14 Estrutura de Dados I 2 Tópicos Principais

Luis Martí Instituto de Computação

Universidade Federal Fluminense [email protected] - http://lmarti.com

Linguagem C: Árvores Binarias

Instituto de

C

23/04/14 Estrutura de Dados I 2

Tópicos Principais

• Introdução

• Árvores binárias

• Implementação em C

• Ordens de percurso

• Árvore binária de busca (ABB)

• Funções para ABBs – Impressão

– Busca


Tópicos Complementares

• Inserção em ABB

• Remoção em ABB


Introdução

• Árvore – um conjunto de nós tal que

• existe um nó r, denominado raiz, com zero ou mais sub-árvores, cujas raízes estão ligadas a r

• os nós raízes destas sub-árvores são os filhos de r

• os nós internos da árvore são os nós com filhos

• as folhas ou nós externos da árvore são os nós sem filhos

nó raiz

. . . sub-árvores

nó raiz

. . . sub-árvores


Árvores binárias

• Árvore binária

– uma árvore em que cada nó tem zero, um ou dois filhos

– uma árvore binária é: • uma árvore vazia; ou

• um nó raiz com duas sub-árvores: – a sub-árvore da esquerda (sae)

– a sub-árvore da direita (sad)

raiz

sadsae

vazia


Árvores binárias

• Exemplo – árvores binárias representando expressões aritméticas:

• nós folhas representam operandos

• nós internos operadores

• exemplo: (3+6)*(4-1)+5

*

+ –

1463

5

+


Implementação em C

• Representação de uma árvore: – através de um ponteiro para o nó raiz

• Representação de um nó da árvore: – estrutura em C contendo

• a informação propriamente dita (exemplo: um caractere)

• dois ponteiros para as sub-árvores, à esquerda e à direita

struct noArv { int info; struct noArv* esq; struct noArv* dir; };



• Interface do tipo abstrato Árvore Binária: arv.h

typedef struct noArv NoArv;

NoArv* arv_cria (int x, NoArv* e, NoArv* d); void arv_libera (NoArv* a); int arv_contem (NoArv* a, int x); void arv_imprime (NoArv* a);



• Implementação das funções: – implementação recursiva, em geral

– usa a definição recursiva da estrutura

Uma árvore binária é: • uma árvore vazia; ou

• um nó raiz com duas sub-árvores: – a sub-árvore da direita (sad)

– a sub-árvore da esquerda (sae)

raiz

sadsae

vazia



• função arv_cria – cria um nó raiz dadas a informação e as duas sub-árvores, a da

esquerda e a da direita

– retorna o endereço do nó raiz criado

NoArv* arv_cria (int x, NoArv* sae, NoArv* sad) { NoArv* p=(NoArv*)malloc(sizeof(NoArv)); p->info = x; p->esq = sae; p->dir = sad; return p; }



• função arv_libera – libera memória alocada pela estrutura da árvore

• as sub-árvores devem ser liberadas antes de se liberar o nó raiz

– retorna uma árvore vazia, representada por NULL

void arv_libera (NoArv* a){ if (a != NULL){ arv_libera(a->esq); /* libera sae */ arv_libera(a->dir); /* libera sad */ free(a); /* libera raiz */ } }



• função arv_contem – verifica se uma árvore contém um dado inteiro

– retorna um valor inteiro (1 ou 0) indicando a ocorrência ou não do inteiro na árvore

int arv_contem (NoArv* a, int x){ if (a == NULL) return 0; /* árvore vazia: não encontrou */ if (a->info==x) return 1; else return (arv_contem(a->esq, x) || arv_contem(a->dir, x)); }



• função arv_imprime – percorre recursivamente a árvore, visitando todos os nós e

imprimindo sua informação

void arv_imprime (NoArv* a) { if (a != NULL){ printf("%d ", a->info); /* mostra raiz */ arv_imprime(a->esq); /* mostra sae */ arv_imprime(a->dir); /* mostra sad */ } }



• Exemplo:

/* sub-árvore 'd' */ NoArv* a1= arv_cria(9,NULL, NULL); /* sub-árvore 'b' */ NoArv* a2= arv_cria(5, NULL, a1); /* sub-árvore 'e' */ NoArv* a3= arv_cria(3, NULL, NULL); /* sub-árvore 'f' */ NoArv* a4= arv_cria(6, NULL, NULL); /* sub-árvore 'c' */ NoArv* a5= arv_cria(8, a3, a4); /* árvore 'a' */ NoArv* a = arv_cria(7, a2, a5 );

7

5 8

639



• Exemplo:

NoArv* a = arv_cria(7, arv_cria(5, NULL, arv_cria(9, NULL, NULL) ), arv_cria(8, arv_cria(3, NULL, NULL), arv_cria(6, NULL, NULL) ) );

7

5 8

639



• Exemplo - acrescenta nós

a->esq->esq = arv_cria(2, arv_cria(4, NULL, NULL ), arv_cria(1, NULL, NULL ) );

7

5 8

6392

14



• Exemplo - libera nós

a->dir->esq = libera(a->dir->esq); 7

5 8

6392

14


Ordens de percurso

• Ordens de percurso: – pré-ordem:

• trata raiz, percorre sae, percorre sad

• exemplo: 7 5 9 8 3 6

– ordem simétrica: • percorre sae, trata raiz, percorre sad

• exemplo: 5 9 7 3 8 6

– pós-ordem: • percorre sae, percorre sad, trata raiz

• exemplo: 9 5 3 6 8 7

7

5 8

639


Imprime em Ordem Simétrica

• função arv_imprime_sim – percorre recursivamente a árvore, visitando todos os nós e

imprimindo sua informação em ordem simétrica

void arv_imprime_sim (NoArv* a) { if (a != NULL){ arv_imprime_sim(a->esq); /* mostra sae */ printf("%d ", a->info); /* mostra raiz */ arv_imprime_sim(a->dir); /* mostra sad */ } }


Imprime em Pós-ordem

• função arv_imprime_pos – percorre recursivamente a árvore, visitando todos os nós e

imprimindo sua informação em pós-ordem

void arv_imprime_pos (NoArv* a) { if (a != NULL){ arv_imprime_pos(a->esq); /* mostra sae */ arv_imprime_pos(a->dir); /* mostra sad */ printf("%d ", a->info); /* mostra raiz */ } }


Tipos de Árvores Binárias

• Árvores Estritamente Binárias

• Árvores Binárias Completas

• Árvores Binárias Cheias


15 1

Árvores Estritamente Binárias• Ocorre quando todo

nó que não é folha tiver sub-árvores esquerda e direita não vazias.

• Ou seja: todo nó tem 0 ou 2 filhos.

• Número de nós em uma árvore estritamente binária com n folhas: 2n-1

7

9 19

4 8

6 17


Árvores Binárias Completas

• É uma árvore estritamente binária, na qual todos os nós folha estão ou no penúltimo ou no último nível

• Todas as sub-árvores vazias são filhas de nós do último ou penúltimo nível 15 1

7

9

12 13

10 5 11 2

19

4 8


15 1

Árvores Binárias Cheias• É uma árvore

estritamente binária, na qual todos os nós folha estão no último nível

• Todas as subárvores vazias são filhas de nós do último nível

7

9

12 13

10 5 11 2

19

4 8

6 17

Embora possua muitos nós, a distância

da raiz até os nós é relativamente baixa


• Os vértices da árvore estão classificados em níveis. O nível pode ser calculado como o número de nós no caminho entre o vértice e a raiz⇒ nível da raiz é zero ⇒ nível de B e C é 1 ⇒ nível de F e G é 3 ⇒ nível de H é 4

⇒ nível de um nó = nível de seu pai + 1

Nível de um nó da Árvore

H I

A

B C

D E

F G


Altura de uma Árvore

• Existe um único caminho da raiz para qualquer nó da árvore.

• A altura de uma árvore pode ser definida como sendo o comprimento do caminho mais longo da raiz até uma das folhas.

• Por definição, a altura de uma árvore que possui somente o nó raiz é zero.

• A altura de uma árvore é igual a maior altura de uma das suas sub-árvores +1


nível 0 – (somente a raiz) contém um nó nível 1 – contém no máximo 2 nós nível 2 – contém no máximo 4 nós ..... no nível L - pode conter no máximo 2L nós

Uma árvore binária cheia de altura d tem exatamente 2L nós em cada nível 0 ≤ L ≤ d

Árvore Binária - altura mínima


O total de nós n em uma árvore binária cheia (que seria o máximo) de altura d é a soma do número de nós a cada nível d

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

j=0

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

pode-se mostrar também por indução!

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

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



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


15 1

7

9

12 13

10 5 11 2

19

4 8

6 17


• A árvore binária cheia é a árvore binária com o máximo de nós para uma dada altura, mas ▪ a distância da raiz é pequena

• Lema: Seja T uma árvore binária completa com n>0 nós. Então, T possui altura h mínima. Além disso, h = ⎣log n⎦



Árvore Binária de Busca (ABB)

• o valor associado à raiz é sempre maior que o valor associado a qualquer nó da sub-árvore à esquerda (sae) e

• o valor associado à raiz é sempre menor ou igual (para permitir repetições) que o valor associado a qualquer nó da sub-árvore à direita (sad)

• quando a árvore é percorrida em ordem simétrica (sae - raiz - sad), os valores são encontrados em ordem não decrescente


Pesquisa em Árvore Binária de Busca• compare o valor dado com o valor

associado à raiz

• se for igual, o valor foi encontrado

• se for menor, a busca continua na sae

• se for maior, a busca continua na sad


Pesquisa em Árvore Binária de Busca

• Em árvores balanceadas os nós internos têm todos, ou quase todos, 2 filhos

• Qualquer nó pode ser alcançado a partir da raiz em O(log n) passos

6

4

2 5

8

7 9

1 3


Pesquisa em Árvore Binária de Busca

• Em árvores degeneradas todos os nós têm apenas 1 filho, com exceção da (única) folha

• Qualquer nó pode ser alcançado a partir da raiz em O(n) passos

1

2

3

4

5

6

7

8

9


Tipo Árvore Binária de Busca

• árvore é representada pelo ponteiro para o nó raiz

struct noArv { int info; struct noArv* esq; struct noArv* dir; };




• Extensão da interface do tipo abstrato Árvore Binária para uma árvore binária de busca: arvbb.h


NoArv* arv_cria (int x, NoArv* e, NoArv* d); NoArv* arv_libera (NoArv* a); void abb_imprime (NoArv* a); int abb_busca (NoArv* a, int x); NoArv* abb_insere (NoArv* a, int x); NoArv* abb_retira (NoArv* a, int x);


ABB: Impressão

• imprime os valores da árvore em ordem crescente, percorrendo os nós em ordem simétrica

void abb_imprime (NoArv* a) { if (a != NULL) { abb_imprime(a->esq); printf("%d\n",a->info); abb_imprime(a->dir); } }


ABB: Busca• explora a propriedade de ordenação da árvore

• possui desempenho computacional proporcional à altura (O(lg n) para o caso de árvore balanceada)

NoArv* abb_busca (NoArv* a, int v) { if (a == NULL) return NULL; else if (a->info > v) return abb_busca (a->esq, v); else if (a->info < v) return abb_busca (a->dir, v); else return a; }


ABB: Inserção

• recebe um valor v a ser inserido

• retorna o eventual novo nó raiz da (sub-)árvore

• para adicionar v na posição correta, faça: – se a (sub-)árvore for vazia

• crie uma árvore cuja raiz contém v

– se a (sub-)árvore não for vazia • compare v com o valor na raiz

• insira v na sae ou na sad, conforme o resultado da comparação


NoArv* abb_insere (NoArv* a, int v) { int hesq =-1, hdir =-1; if (a==NULL) { a = (NoArv*)malloc(sizeof(NoArv)); a->info = v; a->esq = a->dir = NULL; a->h = 0; } else { if (v < a->info) a->esq = abb_insere(a->esq,v); else /* v >= a->info */ a->dir = abb_insere(a->dir,v);

if (a->esq!=NULL) hesq = a->esq->h if (a->dir!=NULL) hdir = a->dir->h

if(hesq>hadir) a->h = hesq+1; else a->h = hdir+1; } return a; }


6

4

2 5

8

7 9

1 3

insere 6

cria

insere 8

insere 4

insere 5

insere 2

insere 3

insere 1

insere 9

insere 7

Exemplo

Arv


6

4

2 5

8

7 9

1 3

insere 6

cria

insere 8

insere 4

insere 5

insere 2

insere 3

insere 1

insere 9insere 7

insere 6

6

Exemplo (c/ repetição de valores)


ABB: Remoção• recebe um valor v a ser inserido

• retorna a eventual nova raiz da árvore

• para remover v, faça: – se a árvore for vazia

• nada tem que ser feito

– se a árvore não for vazia • compare o valor armazenado no nó raiz com v

• se for maior que v, retire o elemento da sub-árvore à esquerda

• se for menor do que v, retire o elemento da sub-árvore à direita

• se for igual a v, retire a raiz da árvore


ABB: Remoção

• para retirar a raiz da árvore, há 3 casos: – caso 1: a raiz que é folha

– caso 2: a raiz a ser retirada possui um único filho

– caso 3: a raiz a ser retirada tem dois filhos


ABB: Remoção de folha

• Caso 1: a raiz da sub-árvore é folha da árvore original – libere a memória alocada pela raiz

– retorne a raiz atualizada, que passa a ser NULL

retirar 3


ABB: Remoção de pai de filho único

• Caso 2: a raiz a ser retirada possui um único filho – libere a memória alocada pela raiz

– a raiz da árvore passa a ser o único filho da raiz

retirar 4


ABB: remoção de pai de dois filhos

• Caso 3: a raiz a ser retirada tem dois filhos – encontre o nó N que precede a raiz na ordenação

(o elemento mais à direita da sub-árvore à esquerda)

– troque o dado da raiz com o dado de N

– retire N da sub-árvore à esquerda (que agora contém o dado da raiz que se deseja retirar)

• retirar o nó N mais à direita é trivial, pois N é um nó folha ou N é um nó com um único filho (no caso, o filho da direita nunca existe)

retirar 6


NoArv* abb_retira (NoArv* a, int v) { if (a == NULL) return NULL; else if (a->info > v) a->esq = abb_retira(a->esq, v); else if (a->info < v) a->dir = abb_retira(a->dir, v); else { /* achou o nó a remover */ /* nó sem filhos */ if (a->esq == NULL && a->dir == NULL) { free (a); a = NULL; } /* nó só tem filho à direita */ else if (a->esq == NULL) { NoArv* t = a; a = a->dir; free (t); }


/* só tem filho à esquerda */ else if (r->dir == NULL) { NoArv* t = r; r = r->esq; free (t); } /* nó tem os dois filhos */ else { NoArv* f = r->esq; while (f->dir != NULL) { f = f->dir; } r->info = f->info; /* troca as informações */ f->info = v; r->esq = abb_retira(r->esq,v); } } return r; }


Referências

Waldemar Celes, Renato Cerqueira, José Lucas Rangel, Introdução a Estruturas de Dados, Editora Campus (2004)

• Capítulo 13 – Árvores

• Capítulo 17 – Busca

Material adaptado por Luis Martí a partir dos slides de José Viterbo Filho que forem elaborados por Marco Antonio Casanova e Marcelo Gattas para o curso de Estrutura de Dados para Engenharia da PUC-Rio, com base no livro Introdução a Estrutura de Dados, de Waldemar Celes, Renato Cerqueira e José Lucas Rangel, Editora Campus (2004).

Documents

Linguagem C: Árvores Binariaslmarti.com/wp-content/uploads/2015/12/Aula-8-Arvores-Binárias.pdf · Árvores Binarias Instituto de C. 23/04/14 Estrutura de Dados I 2 Tópicos Principais