Arvore Binaria de Pesquisa - Implementacao e Conceitos

Árvore Binária de Pesquisa Profa Rachel Reis Prof Guilherme Pena Apresentação A operação de busca em uma estrutura visa descobrir se o elemento pertence ou não à estrutura Em uma árvore é preciso percorrêla até encontrar o elemento se existir Organizar os elementos em uma árvore Binária de Pesquisa permite facilitar a busca Definição Uma Árvore Binária de Pesquisa possui as mesmas propriedades de uma Árvore Binária acrescida das seguintes propriedades 1 Os nós pertencentes à subárvore esquerda possuem valores menores do que o valor associado ao nóraiz 20 10 30 35 17 Definição Uma Árvore Binária de Pesquisa possui as mesmas propriedades de uma Árvore Binária acrescida das seguintes propriedades 2 Os nós pertencentes à subárvore direita possuem valores maiores do que o valor associado ao nóraiz 20 10 30 35 17 Definição Uma Árvore Binária de Pesquisa possui as mesmas propriedades de uma Árvore Binária acrescida das seguintes propriedades 3 Os percurso emordem nessa árvore resulta na sequência de valores em ordem crescente 20 10 30 35 17 Percurso emordem 10 17 20 30 35 Implementação Dinâmica Inserir elemento Pesquisar elemento Inicializar ABP Definir ABP Árvore Binária de Pesquisa ABP Remover elemento typedef struct sNo TIPO info struct sNo esq struct sNo dir NO typedef struct sABP NO ptRaiz ABP ptRaiz Definição esq info dir Implementação Dinâmica Inserir elemento Pesquisar elemento Inicializar ABP Definir ABP Árvore Binária de Pesquisa ABP Remover elemento void inicializarNO raiz raiz NULL raiz ptRaiz Inicializar Implementação Dinâmica Inserir elemento Pesquisar elemento Inicializar ABP Definir ABP Árvore Binária de Pesquisa ABP Remover elemento Pesquisar elemento 1 Comece a pesquisar a partir do nóraiz 2 Para cada nóraiz de uma subárvore compare Se o valor procurado é maior que o valor do nóraiz continue pela subárvore direita Se o valor procurado é menor que o valor do nóraiz continue pela subárvore esquerda 3 Caso o elemento seja encontrado retorne o endereço do nó 4 Caso o elemento não seja encontrado retorne NULL NO pesquisarNO raiz int elem NO aux aux raiz ifaux NULL return NULL else ifelem auxinfo return pesquisarauxesq elem else ifelem auxinfo return pesquisarauxdir elem else return aux Exercício 1 Crie uma árvore binária de pesquisa A formada pelos seguintes elementos 20 10 30 17 13 e 35 Considere que o elemento 11 está sendo procurado na árvore A verifique quantas vezes as instruções de cada ifelse da função pesquisar serão executadas Implementação Dinâmica Inserir elemento Pesquisar elemento Inicializar ABP Definir ABP Árvore Binária de Pesquisa ABP Remover elemento Inserir elemento Exemplo Considere a árvore inicialmente vazia Considere o conjunto de números na sequência 17 99 13 1 void inserirNO raiz int elem NO aux raiz NO aux2 NULL NO novo novo criarNo ifnovo NULL printf Erro Memória não alocada return Inserir elemento void inserirNO raiz int elem NO aux raiz NO aux2 NULL NO novo novo criarNo ifnovo NULL printf Erro Memória não alocada return raiz ptrRaiz 24 12 26 void inserirNO raiz int elem NO aux raiz NO aux2 NULL NO novo novo criarNo ifnovo NULL printf Erro Memória não alocada return raiz ptrRaiz 24 elem 25 12 26 void inserirNO raiz int elem NO aux raiz NO aux2 NULL NO novo novo criarNo ifnovo NULL printf Erro Memória não alocada return raiz ptrRaiz 24 12 26 elem 25 aux void inserirNO raiz int elem NO aux raiz NO aux2 NULL NO novo novo criarNo ifnovo NULL printf Erro Memória não alocada return raiz ptrRaiz 24 12 26 elem 25 aux2 NULL aux void inserirNO raiz int elem NO aux raiz NO aux2 NULL NO novo novo alocarNo ifnovo NULL printf Erro Memória não alocada return raiz ptrRaiz 24 12 26 elem 25 aux2 NULL novo aux void inserirNO raiz int elem NO aux raiz NO aux2 NULL NO novo novo alocarNo ifnovo NULL printf Erro Memória não alocada return raiz ptrRaiz 24 12 26 elem 25 aux2 NULL novo aux void inserirNO raiz int elem novo info elem novo esq NULL novo dir NULL whileaux NULL aux2 aux ifelem aux info aux aux esq else aux aux dir raiz ptrRaiz 24 12 26 elem 25 aux2 NULL novo 25 aux void inserirNO raiz int elem novo info elem novo esq NULL novo dir NULL whileaux NULL aux2 aux ifelem aux info aux aux esq else aux aux dir raiz ptrRaiz 24 12 26 elem 25 aux2 NULL novo 25 aux void inserirNO raiz int elem novo info elem novo esq NULL novo dir NULL whileaux NULL aux2 aux ifelem aux info aux aux esq else aux aux dir raiz ptrRaiz 24 12 26 elem 25 aux2 NULL novo 25 aux TRUE void inserirNO raiz int elem novo info elem novo esq NULL novo dir NULL whileaux NULL aux2 aux ifelem aux info aux aux esq else aux aux dir raiz ptrRaiz 24 12 26 elem 25 aux aux2 novo 25 void inserirNO raiz int elem novo info elem novo esq NULL novo dir NULL whileaux NULL aux2 aux ifelem aux info aux aux esq else aux aux dir raiz ptrRaiz 24 12 26 elem 25 aux aux2 novo 25 False void inserirNO raiz int elem novo info elem novo esq NULL novo dir NULL whileaux NULL aux2 aux ifelem aux info aux aux esq else aux aux dir raiz ptrRaiz 24 12 26 elem 25 aux aux2 novo 25 void inserirNO raiz int elem novo info elem novo esq NULL novo dir NULL whileaux NULL aux2 aux ifelem aux info aux aux esq else aux aux dir raiz ptrRaiz 24 12 26 elem 25 aux aux2 novo 25 void inserirNO raiz int elem novo info elem novo esq NULL novo dir NULL whileaux NULL aux2 aux ifelem aux info aux aux esq else aux aux dir raiz ptrRaiz 24 12 26 elem 25 aux aux2 novo 25 TRUE void inserirNO raiz int elem novo info elem novo esq NULL novo dir NULL whileaux NULL aux2 aux ifelem aux info aux aux esq else aux aux dir raiz ptrRaiz 24 12 26 elem 25 aux aux2 novo 25 void inserirNO raiz int elem novo info elem novo esq NULL novo dir NULL whileaux NULL aux2 aux ifelem aux info aux aux esq else aux aux dir raiz ptrRaiz 24 12 26 elem 25 aux novo 25 aux2 TRUE void inserirNO raiz int elem novo info elem novo esq NULL novo dir NULL whileaux NULL aux2 aux ifelem aux info aux aux esq else aux aux dir raiz ptrRaiz 24 12 26 aux novo 25 aux2 elem 25 void inserirNO raiz int elem novo info elem novo esq NULL novo dir NULL whileaux NULL aux2 aux ifelem aux info aux aux esq else aux aux dir raiz ptrRaiz 24 12 26 aux novo 25 aux2 False elem 25 void inserirNO raiz int elem ifaux2 NULL raiz novo else ifelem aux2 info aux2 esq novo else aux2 dir novo raiz ptrRaiz 24 12 26 novo 25 aux2 False elem 25 void inserirNO raiz int elem ifaux2 NULL raiz novo else ifelem aux2 info aux2 esq novo else aux2 dir novo raiz ptrRaiz 24 12 26 novo 25 aux2 elem 25 void inserirNO raiz int elem ifaux2 NULL raiz novo else ifelem aux2 info aux2 esq novo else aux2 dir novo raiz ptrRaiz 24 12 26 novo 25 aux2 TRUE elem 25 void inserirNO raiz int elem ifaux2 NULL raiz novo else ifelem aux2 info aux2 esq novo else aux2 dir novo raiz ptrRaiz 24 12 26 novo 25 aux2 raiz ptrRaiz 24 12 26 25 24 12 26 25 void inserirNO raiz int elem NO aux raiz NO aux2 NULL NO novo novo alocarNo ifnovo NULL printf Erro Memória não alocada return novo info elem novo esq NULL novo dir NULL whileaux NULL aux2 aux ifelem aux info aux aux esq else aux aux dir ifaux2 NULL raiz novo else ifelem aux2 info aux2 esq novo else aux2 dir novo Exercício 2 Implemente uma função recursiva para a operação de inserção em uma árvore binária de pesquisa Implementação Dinâmica Inserir elemento Pesquisar elemento Inicializar ABP Definir ABP Árvore Binária de Pesquisa ABP Remover elemento Remover elemento Casos a serem considerados Caso 1 o nó é folha Caso 2 o nó possui apenas uma subárvore esq ou dir Caso 3 o nó possui as duas subárvores esq e dir Remover elemento Caso 1 o nó é folha Basta remover o nó da árvore Exemplo 11 9 14 6 12 13 11 9 14 6 12 13 Remover elemento Casos a serem considerados Caso 1 o nó é folha Caso 2 o nó possui apenas uma subárvore esq ou dir Caso 3 o nó possui as duas subárvores esq e dir Remover elemento Caso 2 o nó possui apenas uma subárvore esq ou dir O nó raiz da subárvore esq ou dir ocupa o lugar do nó removido Exemplo 11 9 14 6 12 13 11 9 14 6 12 13 11 9 6 12 13 Remover elemento Casos a serem considerados Caso 1 o nó é folha Caso 2 o nó possui apenas uma subárvore esq ou dir Caso 3 o nó possui as duas subárvores esq e dir Remover elemento Caso 3 o nó possui as duas subárvores esq e dir 1 Substituir pelo nó com o menor valor da subárvore direita ou 2 Substituir pelo nó com o maior valor da subárvore esquerda 11 9 14 6 12 13 10 11 9 14 6 12 13 10 12 9 14 6 13 10 Remover elemento Caso 3 o nó possui as duas subárvores esq e dir 1 Substituir pelo nó com o menor valor da subárvore direita ou 2 Substituir pelo nó com o maior valor da subárvore esquerda 11 9 14 6 12 10 13 11 9 14 6 12 10 13 10 9 14 6 12 13 NO removerNO raiz int elem ifraiz NULL return NULL else ifraizinfo k raizesq removerraizesq elem else ifraizinfo k raizdir removerraizdir elem else Remover elemento NO removerNO raiz int elem ifraiz NULL return NULL else ifraizinfo k raizesq removerraizesq elem else ifraizinfo k raizdir removerraizdir elem else raiz 24 12 26 NO removerNO raiz int elem ifraiz NULL return NULL else ifraizinfo k raizesq removerraizesq elem else ifraizinfo k raizdir removerraizdir elem else 24 12 26 elem 24 raiz NO removerNO raiz int elem ifraiz NULL return NULL else ifraizinfo k raizesq removerraizesq elem else ifraizinfo k raizdir removerraizdir elem else 24 12 26 False elem 24 raiz NO removerNO raiz int elem ifraiz NULL return NULL else ifraizinfo elem raizesq removerraizesq elem else ifraizinfo k raizdir removerraizdir elem else 24 12 26 elem 24 False raiz NO removerNO raiz int elem ifraiz NULL return NULL else ifraizinfo elem raizesq removerraizesq elem else ifraizinfo elem raizdir removerraizdir elem else 24 12 26 elem 24 False raiz NO removerNO raiz int elem ifraiz NULL return NULL else ifraizinfo elem raizesq removerraizesq elem else ifraizinfo elem raizdir removerraizdir elem else encontrou o elemento 24 12 26 elem 24 raiz NO removerNO raiz int elem ifraizesq NULL raizdir NULL apagarNoraiz raiz NULL 24 12 26 elem 24 raiz Elemento sem filhos False NO removerNO raiz int elem else ifraizesq NULL NO temp raiz raiz raizdir apagarNotemp 24 12 26 elem 24 raiz Só possui filho à direita False NO removerNO raiz int elem else ifraizdir NULL NO temp raiz raiz raizdir apagarNotemp 24 12 26 elem 24 raiz Só possui filho à esquerda False NO removerNO raiz int elem else NO Pai raiz NO F raizesq whileFdir NULL Pai F F Fdir 24 12 26 elem 24 raiz Elemento possui os dois filhos True NO removerNO raiz int elem else NO Pai raiz NO F raizesq whileFdir NULL Pai F F Fdir 24 12 26 elem 24 Pai raiz NO removerNO raiz int elem else NO Pai raiz NO F raizesq whileFdir NULL Pai F F Fdir 24 12 26 elem 24 Pai F raiz NO removerNO raiz int elem else NO Pai raiz NO F raizesq whileFdir NULL Pai F F Fdir 24 12 26 elem 24 Pai False F raiz NO removerNO raiz int elem raizinfo Finfo Finfo elem raizesq removerraizesq elem return raiz 12 24 26 raiz Pai F Trocam os dados elem 24 NO removerNO raiz int elem raizinfo Finfo Finfo elem raizesq removerraizesq elem return raiz 12 24 26 elem 24 raiz Pai F Passa a nova subárvore para retirada do nó NO removerNO raiz int elem ifraiz NULL return NULL else ifraizinfo k raizesq removerraizesq elem else ifraizinfo k raizdir removerraizdir elem else 12 24 26 raiz raiz NO removerNO raiz int elem ifraiz NULL return NULL else ifraizinfo k raizesq removerraizesq elem else ifraizinfo k raizdir removerraizdir elem else elem 24 12 24 26 raiz raiz NO removerNO raiz int elem ifraiz NULL return NULL else ifraizinfo k raizesq removerraizesq elem else ifraizinfo k raizdir removerraizdir elem else elem 24 False 12 24 26 raiz raiz NO removerNO raiz int elem ifraiz NULL return NULL else ifraizinfo elem raizesq removerraizesq elem else ifraizinfo k raizdir removerraizdir elem else elem 24 False 12 24 26 raiz raiz NO removerNO raiz int elem ifraiz NULL return NULL else ifraizinfo elem raizesq removerraizesq elem else ifraizinfo elem raizdir removerraizdir elem else elem 24 12 24 26 raiz raiz False NO removerNO raiz int elem ifraiz NULL return NULL else ifraizinfo elem raizesq removerraizesq elem else ifraizinfo elem raizdir removerraizdir elem elseencontrou o elemento elem 24 12 24 26 raiz raiz NO removerNO raiz int elem ifraizesq NULL raizdir NULL apagarNoraiz raiz NULL 12 24 26 elem 24 raiz raiz Elemento sem filhos True NO removerNO raiz int elem ifraizesq NULL raizdir NULL desalocarNoraiz raiz NULL 12 24 26 elem 24 raiz raiz NO removerNO raiz int elem ifraizesq NULL raizdir NULL desalocarNoraiz raiz NULL 12 26 elem 24 raiz raiz NO removerNO raiz int elem raizinfo Finfo Finfo elem raizesq removerraizesq elem return raiz 12 26 raiz raiz NO removerNO raiz int elem ifraiz NULL return NULL else ifraizinfo elem raizesq removerraizesq elem else ifraizinfo elem raizdir removerraizdir elem elseAchou o elemento ifraizesq NULL raizdir NULL desalocarNoraiz raiz NULL else ifraizesq NULL NO temp raiz raiz raizdir desalocarNOtemp só tem filho à direita elemento sem filhos NO removerNO raiz int elem else ifraizdir NULL NO temp raiz raiz raizesq desalocarNOtemp else o elemento possui os dois filhos NO Pai raiz NO F raizesq whileFdir NULL Pai F F Fdir raizinfo Finfo Finfo elem raizesq removerraizesq elem return raiz só tem filho à esquerda Exercício 3 Alterar a função remover para que o elemento a ser removido seja substituído pelo menor valor da subárvore direita Referências Bibliográficas Ascencio A F G Araújo G S de 2010 Estruturas de Dados algoritmos análise da complexidade e implementações em JAVA e C São Paulo Pearson Prentice Hall Forbellone A L V Eberspacher H F 2005 Lógica de Programação A construção de algoritmos e estruturas de dados 3ª edição São Paulo Pearson Prentice Hall