69
ÁRVORES BINÁRIAS DE BUSCA Vanessa Braganholo Estruturas de Dados e Seus Algoritmos

ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

  • Upload
    others

  • View
    11

  • Download
    0

Embed Size (px)

Citation preview

Page 1: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

ÁRVORES BINÁRIAS DE BUSCA Vanessa BraganholoEstruturas de Dados e Seus Algoritmos

Page 2: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

REFERÊNCIA

Szwarcfiter, J.; Markezon, L. Estruturas de Dados e seus Algoritmos, 3a. ed. LTC. Cap. 4

INSTITUTO DE COMPUTAÇÃO - UFF 2

Page 3: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

BUSCA

Diversas aplicações precisam buscar um determinado valor em um conjunto de dados

Essa busca deve ser feita da forma mais eficiente possível

Árvores binárias possibilitam buscas com eficiência

Exemplo: buscar dados de uma pessoa que possui um determinado CPF

Dados das pessoas são armazenados numa árvore binária de busca

CPF funciona como “chave”, pois é único para cada pessoa (não existem duas pessoas com o mesmo CPF)

INSTITUTO DE COMPUTAÇÃO - UFF 3

Page 4: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

ÁRVORES BINÁRIAS DE BUSCA

Apresentam uma relação de ordem entre os nós

Ordem é definida pela chave

raiz500

300 800

150 400 900600

esq chave info dir

Demais infos do nóINSTITUTO DE COMPUTAÇÃO - UFF 4

Page 5: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

ÁRVORES BINÁRIAS DE BUSCA

Uma árvore binária T é uma árvore binária de busca se: ­ Chaves da subárvore esquerda de T são

menores do que chave da raiz de T; e­ Chaves da subárvore da direita de T são

maiores do que a chave da raiz de T; e­ Subárvores da esquerda e da direita de T são

árvores binárias de busca

raiz500

300 800

150 400 900600

INSTITUTO DE COMPUTAÇÃO - UFF 5

Page 6: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

ÁRVORES BINÁRIAS DE BUSCA

Para um mesmo conjunto de chaves, existem várias árvores binárias de busca possíveis

Exemplos para o conjunto de chaves:

{1, 2, 3, 4, 5, 6, 7}

INSTITUTO DE COMPUTAÇÃO - UFF 6

3

1 7

2 5

4 6

2

1 7

3

4

5

6

Page 7: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

OPERAÇÕES

Buscar nó com determinada chave

Inserir novo nó

Remover nó

raiz500

300 800

150 400 900600Operações devem respeitar a

ordem!

INSTITUTO DE COMPUTAÇÃO - UFF 7

Page 8: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

BUSCA POR NÓ COM CHAVE X

raiz500

300 800

150 400 900600

INSTITUTO DE COMPUTAÇÃO - UFF 8

Em qualquer nó: X = ChaveX > ChaveX < Chave

Page 9: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

BUSCA POR NÓ COM DETERMINADA CHAVEesq chave info dir/* representação dos nós de a */

typedef struct sNoA {char info;int chave;struct sNoA* esq;struct sNoA* dir;

} TNoA;

TNoA* busca(TNoA *no, int chave) {//Recebe endereço da raiz e chave procurada.

Se encontrar, retorna nó encontrado. //Caso contrário, retorna NULO}

Fazer agora!

INSTITUTO DE COMPUTAÇÃO - UFF 9

Page 10: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

IMPLEMENTAÇÃO ITERATIVATNoA* busca(TNoA *no, int chave) {

while (no != NULL) {if (no->chave == chave )

return no; //achou retorna o ponteiro para o nóelseif (no->chave > chave)

no = no->esq;else

no = no->dir;}return NULL; //não achou, retorna null

}

INSTITUTO DE COMPUTAÇÃO - UFF 10

Page 11: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

IMPLEMENTAÇÃO RECURSIVATNoA* buscaRecursiva(TNoA *no, int chave) {

if (no == NULL)return NULL;

else if (no->chave == chave)return no;

else if (no->chave > chave)return buscaRecursiva(no->esq, chave);

elsereturn buscaRecursiva(no->dir, chave);

}

INSTITUTO DE COMPUTAÇÃO - UFF 11

Page 12: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

COMPLEXIDADE

Em cada chamada da função busca, é efetuado um número constante de operações.

A complexidade da busca é igual ao número de chamadas da função.

No pior caso (quando chave buscada está na folha), a complexidade é a altura da árvore.

Complexidade de pior caso mínima ocorre para árvore completa, onde altura é log n (n é o número de nós da árvore).

Portanto, o ideal é que a árvore binária de busca seja o mais balanceada possível.

INSTITUTO DE COMPUTAÇÃO - UFF 12

Page 13: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

INSERÇÃO

Se a árvore for vazia, instala o novo nó na raiz

Se não for vazia, compara a chave com a chave da raiz:­ se for menor, instala o nó na sub-árvore da esquerda­ caso contrário, instala o nó na sub-árvore da direita

IMPORTANTE: inserção é sempre feita nas folhas

INSTITUTO DE COMPUTAÇÃO - UFF 13

Page 14: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

INSERÇÃO

Se a árvore for vazia, instala o novo nó na raiz

Se não for vazia, compara a chave com a chave da raiz:­ se for menor, instala o nó na sub-árvore da esquerda­ caso contrário, instala o nó na sub-árvore da direita

INSTITUTO DE COMPUTAÇÃO - UFF 14

Ordem de Inserção: 500 – 800 – 300 - 400

500

Page 15: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

INSERÇÃO

Se a árvore for vazia, instala o novo nó na raiz

Se não for vazia, compara a chave com a chave da raiz:­ se for menor, instala o nó na sub-árvore da esquerda­ caso contrário, instala o nó na sub-árvore da direita

INSTITUTO DE COMPUTAÇÃO - UFF 15

Ordem de Inserção: 500 – 800 – 300 - 400

500

800

Page 16: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

INSERÇÃO

Se a árvore for vazia, instala o novo nó na raiz

Se não for vazia, compara a chave com a chave da raiz:­ se for menor, instala o nó na sub-árvore da esquerda­ caso contrário, instala o nó na sub-árvore da direita

INSTITUTO DE COMPUTAÇÃO - UFF 16

Ordem de Inserção: 500 – 800 – 300 - 400

500

300 800

Page 17: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

INSERÇÃO

Se a árvore for vazia, instala o novo nó na raiz

Se não for vazia, compara a chave com a chave da raiz:­ se for menor, instala o nó na sub-árvore da esquerda­ caso contrário, instala o nó na sub-árvore da direita

500

300 800

INSTITUTO DE COMPUTAÇÃO - UFF 17

Ordem de Inserção: 500 – 800 – 300 - 400

400

Page 18: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

+ 380

500

300 800

150 400 900600

raizEXERCÍCIO

INSTITUTO DE COMPUTAÇÃO - UFF 18

Page 19: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

+ 380

500

300 800

150 400 900600

raiz

380

EXERCÍCIO

INSTITUTO DE COMPUTAÇÃO - UFF 19

Page 20: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

+ 380

+ 750

500

300 800

150 400 900600

raiz

380

EXERCÍCIO

INSTITUTO DE COMPUTAÇÃO - UFF 20

Page 21: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

+ 380

+ 750

500

300 800

150 400 900600

raiz

380 750

EXERCÍCIO

INSTITUTO DE COMPUTAÇÃO - UFF 21

Page 22: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXERCÍCIOS

1. Inserir em uma ABB inicialmente vazia, os seguintes valores:

25, 22, 40, 30, 45, 27, 20, 21, 48

2. Inserir em uma ABB inicialmente vazia, os seguintes valores:

40, 25, 20, 30, 45, 27, 22, 21, 48

INSTITUTO DE COMPUTAÇÃO - UFF 22

Page 23: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

INSERÇÃO25 22 40 30 45 27 20 21 48

22

25

40

20 30 45

21 27 48

40 25 20 30 45 27 22 21 48

25

40

45

20 30

21

22

48

27

INSTITUTO DE COMPUTAÇÃO - UFF 23

Page 24: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

INSERÇÃO25 22 40 30 45 27 20 21 48

A árvore gerada depende da ordem de inserção dos nós

22

25

40

20 30 45

21 27 48

40 25 20 30 45 27 22 21 48

25

40

45

20 30

21

22

48

27

INSTITUTO DE COMPUTAÇÃO - UFF 24

Page 25: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

IMPLEMENTAÇÃO DE INSERÇÃOTNoA *insere(TNoA *no, int chave) {

if (no == NULL) {no = (TNoA *) malloc(sizeof(TNoA));no->chave = chave;no->esq = NULL;no->dir = NULL;

} else if (chave < (no->chave))no->esq = insere(no->esq, chave);

else if (chave > (no->chave)) no->dir = insere(no->dir, chave);

else {printf("Inserção inválida! "); // chave já existeexit(1);

}return no;

}

INSTITUTO DE COMPUTAÇÃO - UFF 25

Page 26: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

IMPLEMENTAÇÃO DE INSERÇÃOTNoA *insere(TNoA *no, int chave) {

if (no == NULL) {no = (TNoA *) malloc(sizeof(TNoA));no->chave = chave;no->esq = NULL;no->dir = NULL;

} else if (chave < (no->chave))no->esq = insere(no->esq, chave);

else if (chave > (no->chave)) no->dir = insere(no->dir, chave);

else {printf("Inserção inválida! "); // chave já existeexit(1);

}return no;

}

INSTITUTO DE COMPUTAÇÃO - UFF 26

Árvore Binária de Busca não pode ter chave duplicada

Page 27: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

PROBLEMA

A ordem em que as chaves são inseridas numa árvore de busca binária pode fazer com que uma árvore binária se deteriore, ficando com altura muito grande.

Exemplo:

INSTITUTO DE COMPUTAÇÃO - UFF 27

25 40 39 27 25

40

39

27

Page 28: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

CRIAÇÃO DE ÁRVORE BINÁRIA DE BUSCA MAIS BALANCEADA POSSÍVELSabendo disso, é possível reordenar as chaves de entrada de forma a obter uma árvore o mais balanceada possível.

Algoritmo: ­ Seja v um vetor ORDENADO contendo as chaves a serem inseridas ­ Inserir a chave do meio­ Chamar recursivamente para os dois pedaços que sobraram

INSTITUTO DE COMPUTAÇÃO - UFF 28

Page 29: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

CRIAÇÃO DE ÁRVORE BINÁRIA DE BUSCA MAIS BALANCEADA POSSÍVELAlgoritmo: ­ Seja v um vetor ORDENADO contendo as

chaves a serem inseridas ­ Inserir a chave do meio­ Chamar recursivamente para os dois pedaços

que sobraram (esquerda e direita)

INSTITUTO DE COMPUTAÇÃO - UFF 29

150 300 400 500 600 800 900

500

Page 30: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

CRIAÇÃO DE ÁRVORE BINÁRIA DE BUSCA MAIS BALANCEADA POSSÍVELAlgoritmo: ­ Seja v um vetor ORDENADO contendo as

chaves a serem inseridas ­ Inserir a chave do meio­ Chamar recursivamente para os dois pedaços

que sobraram (esquerda e direita)

INSTITUTO DE COMPUTAÇÃO - UFF 30

150 300 400 500 600 800 900

500

Page 31: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

CRIAÇÃO DE ÁRVORE BINÁRIA DE BUSCA MAIS BALANCEADA POSSÍVELAlgoritmo: ­ Seja v um vetor ORDENADO contendo as

chaves a serem inseridas ­ Inserir a chave do meio­ Chamar recursivamente para os dois pedaços

que sobraram (esquerda e direita)

INSTITUTO DE COMPUTAÇÃO - UFF 31

150 300 400 500 600 800 900

500

300

Page 32: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

CRIAÇÃO DE ÁRVORE BINÁRIA DE BUSCA MAIS BALANCEADA POSSÍVELAlgoritmo: ­ Seja v um vetor ORDENADO contendo as

chaves a serem inseridas ­ Inserir a chave do meio­ Chamar recursivamente para os dois pedaços

que sobraram (esquerda e direita)

INSTITUTO DE COMPUTAÇÃO - UFF 32

150 300 400 500 600 800 900

500

300

150

Page 33: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

CRIAÇÃO DE ÁRVORE BINÁRIA DE BUSCA MAIS BALANCEADA POSSÍVELAlgoritmo: ­ Seja v um vetor ORDENADO contendo as

chaves a serem inseridas ­ Inserir a chave do meio­ Chamar recursivamente para os dois pedaços

que sobraram (esquerda e direita)

INSTITUTO DE COMPUTAÇÃO - UFF 33

150 300 400 500 600 800 900

500

300

150 400

Page 34: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

CRIAÇÃO DE ÁRVORE BINÁRIA DE BUSCA MAIS BALANCEADA POSSÍVELAlgoritmo: ­ Seja v um vetor ORDENADO contendo as

chaves a serem inseridas ­ Inserir a chave do meio­ Chamar recursivamente para os dois pedaços

que sobraram (esquerda e direita)

INSTITUTO DE COMPUTAÇÃO - UFF 34

150 300 400 500 600 800 900

500

300

150 400

800

Page 35: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

CRIAÇÃO DE ÁRVORE BINÁRIA DE BUSCA MAIS BALANCEADA POSSÍVELAlgoritmo: ­ Seja v um vetor ORDENADO contendo as

chaves a serem inseridas ­ Inserir a chave do meio­ Chamar recursivamente para os dois pedaços

que sobraram (esquerda e direita)

INSTITUTO DE COMPUTAÇÃO - UFF 35

150 300 400 500 600 800 900

500

300

150 400

800

600

Page 36: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

CRIAÇÃO DE ÁRVORE BINÁRIA DE BUSCA MAIS BALANCEADA POSSÍVELAlgoritmo: ­ Seja v um vetor ORDENADO contendo as

chaves a serem inseridas ­ Inserir a chave do meio­ Chamar recursivamente para os dois pedaços

que sobraram (esquerda e direita)

INSTITUTO DE COMPUTAÇÃO - UFF 36

150 300 400 500 600 800 900

500

300

150 400

800

600 900

Page 37: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

CRIAÇÃO DE ÁRVORE BINÁRIA DE BUSCA MAIS BALANCEADA POSSÍVELAlgoritmo: ­ Seja v um vetor ORDENADO contendo as

chaves a serem inseridas ­ Inserir a chave do meio­ Chamar recursivamente para os dois pedaços

que sobraram (esquerda e direita)

INSTITUTO DE COMPUTAÇÃO - UFF 37

500

300 800

150 400 900600

150 300 400 500 600 800 900

Page 38: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

IMPLEMENTAÇÃO

INSTITUTO DE COMPUTAÇÃO - UFF 38

void criaArvoreBalanceada(TNoA *raiz, int v[], int inicio, int fim) {if (inicio <= fim) {

int meio = (inicio + fim) / 2;raiz = insere(raiz, v[meio]);//constroi subárvores esquerda e direitacriaArvoreBalanceada(raiz, v, inicio, meio - 1);criaArvoreBalanceada(raiz, v, meio + 1, fim);

}}

int main(void) {int tam = 7;int v[] = {150, 300, 400, 500, 600, 800, 900};TNoA *raiz;raiz = NULL;criaArvoreBalanceada(raiz,v,0,tam-1);imprime(raiz, 0);

};

Page 39: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXCLUSÃO

?500

300 800

150 400 900600

INSTITUTO DE COMPUTAÇÃO - UFF 39

Fonte de Referência:Celes, W., Cerqueira, R., Rangel, J.L. Introdução a Estruturas de Dados,

Campus, 1a Edição, 2004.

Page 40: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXCLUSÃO

Exclusão Física

3 casos­ Nó é folha­ Nó não folha

­ Uma subárvore

­ Duas subárvores

500

300 800

150 400 900600

INSTITUTO DE COMPUTAÇÃO - UFF 40

Page 41: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXCLUSÃO – CASO 1: NÓ FOLHA

500

300 800

150 400 900600

INSTITUTO DE COMPUTAÇÃO - UFF 41

Quando o nó a ser excluído é uma folha, basta removê-lo

(lembrar de desalocar memória)

Page 42: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXCLUSÃO – CASO 1: NÓ FOLHA

500

300 800

150 900600

INSTITUTO DE COMPUTAÇÃO - UFF 42

Quando o nó a ser excluído é uma folha, basta removê-lo

(lembrar de desalocar memória)

Page 43: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXCLUSÃO – CASO 2: NÓ INTERNO COM APENAS UMA SUBÁRVORERaiz da subárvore passa a ocupar o lugar do nodo excluído

550 650

500

300 800

150 400 600

INSTITUTO DE COMPUTAÇÃO - UFF 43

Page 44: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXCLUSÃO – CASO 2: NÓ INTERNO COM APENAS UMA SUBÁRVORERaiz da subárvore passa a ocupar o lugar do nodo excluído

550 650

500

300

150 400

600

INSTITUTO DE COMPUTAÇÃO - UFF 44

Page 45: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXCLUSÃO – CASO 3: NÓ POSSUI 2 SUBÁRVORES

Reestruturar a árvore

550 650

500

300 800

150 400 600 900

INSTITUTO DE COMPUTAÇÃO - UFF 45

Page 46: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXCLUSÃO – CASO 3: NÓ POSSUI 2 SUBÁRVORES

Estratégia Recursiva­ Trocar o valor do nó a ser removido com

­ valor do nó que tenha a maior chave da sua subárvore à esquerda (será o que adotaremos em aula); OU­ valor do nó que tenha menor chave da sua subárvore à direita

­ Ir à subárvore onde foi feita a troca e remover o nó

INSTITUTO DE COMPUTAÇÃO - UFF 46

Page 47: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXCLUSÃO – CASO 3: NÓ POSSUI 2 SUBÁRVORES

550 650

500

300 800

150 400 600 900

550

500

300 650

150 400 600 900

Þ

INSTITUTO DE COMPUTAÇÃO - UFF 47

Page 48: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXCLUSÃO DO NÓ DE CHAVE 80200

100 300

150

120

110 130

250

220 270

260

400

350 500

INSTITUTO DE COMPUTAÇÃO - UFF 48

1º. Caso: nó folha 80

Page 49: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXCLUSÃO DO NÓ DE CHAVE 80200

100 300

150

120

110 130

250

220 270

260

400

350 500

INSTITUTO DE COMPUTAÇÃO - UFF 49

1º. Caso: nó folha

Page 50: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXCLUSÃO DO NÓ DE CHAVE 150200

100 300

15080

120

110 130

250

220 270

260

400

350 500

INSTITUTO DE COMPUTAÇÃO - UFF 50

2º. Caso: nó com apenas 1 subárvore

Page 51: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXCLUSÃO DO NÓ DE CHAVE 150200

100 300

80 120

110 130

250

220 270

260

400

350 500

INSTITUTO DE COMPUTAÇÃO - UFF 51

2º. Caso: nó com apenas 1 subárvore

Page 52: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXCLUSÃO DO NÓ DE CHAVE 300200

100 300

15080 250

220 270

260

400

350 500

280

275 290INSTITUTO DE COMPUTAÇÃO - UFF 52

3º. Caso: nó com 2 subárvores

Page 53: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXCLUSÃO DO NÓ DE CHAVE 300200

100 300

15080 250

220 270

260

400

350 500

280

275 290INSTITUTO DE COMPUTAÇÃO - UFF 53

Encontrar maior valor da subárvore esquerda

Page 54: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXCLUSÃO DO NÓ DE CHAVE 300200

100 290

15080 250

220 270

260

400

350 500

280

275 290INSTITUTO DE COMPUTAÇÃO - UFF 54

Encontrar maior valor da subárvore esquerda e substituir

o nó a ser excluído por uma cópia do nó encontrado

Page 55: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXCLUSÃO DO NÓ DE CHAVE 300200

100 290

15080 250

220 270

260

400

350 500

280

275 290INSTITUTO DE COMPUTAÇÃO - UFF 55

Excluir 290 (1º. Caso)

Page 56: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXCLUSÃO DO NÓ DE CHAVE 300200

100 290

15080 250

220 270

260

400

350 500

280

275INSTITUTO DE COMPUTAÇÃO - UFF 56

FIM

Page 57: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXCLUSÃO DO NÓ DE CHAVE 300 (OUTRA ÁRVORE)

200

100 300

15080

120

110 130

250

220 270

260

400

350 500

INSTITUTO DE COMPUTAÇÃO - UFF 57

3º. Caso: nó com 2 subárvores

Page 58: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXCLUSÃO DO NÓ DE CHAVE 300 (OUTRA ÁRVORE)

200

100 270

15080

120

110 130

250

220 270

260

400

350 500

INSTITUTO DE COMPUTAÇÃO - UFF 58

Encontrar maior valor da subárvore esquerda e substituir

o nó a ser excluído por uma cópia do nó encontrado

Page 59: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXCLUSÃO DO NÓ DE CHAVE 300 (OUTRA ÁRVORE)

200

100 270

15080

120

110 130

250

220 270

260

400

350 500

INSTITUTO DE COMPUTAÇÃO - UFF 59

Excluir 270 (2º. Caso)

Page 60: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXCLUSÃO DO NÓ DE CHAVE 300 (OUTRA ÁRVORE)

200

100 270

15080

120

110 130

250

220 260

400

350 500

INSTITUTO DE COMPUTAÇÃO - UFF 60

FIM

Page 61: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXCLUSÃO DE NÓ DE CHAVE 300 (TERCEIRO EXEMPLO) 200

100 300

15080 250

220 270

260

400

350 500

255 265 INSTITUTO DE COMPUTAÇÃO - UFF 61

3º. Caso: nó com 2 subárvores

Page 62: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXCLUSÃO DE NÓ DE CHAVE 300 (TERCEIRO EXEMPLO) 200

100 300

15080 250

220 270

260

400

350 500

255 265 INSTITUTO DE COMPUTAÇÃO - UFF 62

Encontrar maior valor da subárvore esquerda e substituir

o nó a ser excluído por uma cópia do nó encontrado

Page 63: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXCLUSÃO DE NÓ DE CHAVE 300 (TERCEIRO EXEMPLO) 200

100 270

15080 250

220 270

260

400

350 500

255 265 INSTITUTO DE COMPUTAÇÃO - UFF 63

Encontrar maior valor da subárvore esquerda e substituir

o nó a ser excluído por uma cópia do nó encontrado

Page 64: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXCLUSÃO DE NÓ DE CHAVE 300 (TERCEIRO EXEMPLO) 200

100 270

15080 250

220 270

260

400

350 500

255 265 INSTITUTO DE COMPUTAÇÃO - UFF 64

Excluir 270 (2º. Caso)

Page 65: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXCLUSÃO DE NÓ DE CHAVE 300 (TERCEIRO EXEMPLO) 200

100 270

15080 250

220 260

400

350 500

255 265

INSTITUTO DE COMPUTAÇÃO - UFF 65

FIM

Page 66: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXERCÍCIO

Dada a árvore a seguir, executar o procedimento de exclusão cumulativo dos seguintes nós:

100 – 150 – 80 – 270 – 400 – 200

INSTITUTO DE COMPUTAÇÃO - UFF 66

200

100 300

15080

120

110 130

250

220 270

260

400

350 50070

65 79

Page 67: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

EXERCÍCIO

Implementar uma função para excluir um nó que possui uma chave determinada em uma árvore binária de busca. A função deve retornar um ponteiro para a raiz da árvore.

ATENÇÃO: é OBRIGATÓRIO usar o esqueleto fornecido no Google Classroom para a resolução desse exercício.

Assinatura da função:

TNoA *exclui(TNoA *raiz, int chave)

INSTITUTO DE COMPUTAÇÃO - UFF 67

Page 68: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

CONSIDERAÇÕES FINAIS

Para grandes volumes de dados, árvores binárias de busca não são as alternativas mais eficientes. Ao longo da disciplina veremos outras alternativas para buscas eficientes em grandes volumes de dados (Tabelas Hash, Árvores B, Árvores B+).

INSTITUTO DE COMPUTAÇÃO - UFF 68

Page 69: ÁRVORES BINÁRIAS DE BUSCAvanessa/material/ed/04-ArvoresBinariasBusca.pdf · ÁRVORES BINÁRIAS DE BUSCA Apresentam uma relação de ordementre os nós Ordem é definida pela chave

AGRADECIMENTOS

Material baseado nos slides de Renata Galante, UFRGS

INSTITUTO DE COMPUTAÇÃO - UFF 69