Baixe o app para aproveitar ainda mais
Prévia do material em texto
Algoritmo e Estrutura de Dados II COM 112 Vanessa Souza Universidade Federal de Itajubá – Instituto de Matemática e Computação Aula 8 Árvore de pesquisa binária Estrutura de dados não linear Além de um campo chave e dos dados satélite, cada nó contém os campos esquerda, direita e pai, que apontam para os nós correspondentes a seu filho da esquerda, seu filho da direita e seu pai, respectivamente. Se o nó for folha, os filhos da esquerda e da direita recebem NULL Árvore de pesquisa binária Estrutura de dados não linear Operações Cria árvore Insere nó na árvore Percorre os nós da árvore Pré-ordem Ordem Pós-ordem Remove nó da árvore Maior Menor Árvore de pesquisa binária Operações Cria árvore Cria o sentinela e devolve seu endereço, que será único durante toda execução do programa. Árvore de pesquisa binária Operações Insere nó na árvore Insere um nó na árvore binária. Se a árvore estiver vazia, cria a raiz Se a árvore tiver elementos, adiciona seguindo a regra de menores a esquerda, maiores a direita. 5 é raiz da árvore Árvore de pesquisa binária Operações Insere nó na árvore Insere um nó na árvore binária. Se a árvore estiver vazia, cria a raiz Se a árvore tiver elementos, adiciona seguindo a regra de menores a esquerda, maiores a direita. Inserir 7 e 3 na árvore Árvore de pesquisa binária Operações Percorre os nós da ávore Pré-ordem: raiz, esq, dir – 5,3,7 Ordem : esq, raiz, dir – 3,5,7 Pós-ordem: esq, dir, raiz – 3,7,5 Remoção Uma operação mais complicada é a remoção de um nó de uma árvore binária de procura. Para removermos um nó X de uma árvore de busca binária preservando suas propriedades, precisamos considerar três casos: X não possui nenhum filho (folha). X possui apenas um filho. X possui dois filhos. + complexidade Remoção Caso 1 : Nó folha Remoção simples. Basta fazer o pai do nó apontar para NULL Lembrar de liberar a memória do nó 3 Remover o nó 3 Remoção Caso 2 : O nó tem apenas um filho Basta modificar o ponteiro no nó pai de X para que ele aponte para o filho de X. Lembrar de liberar a memória do nó 8 Remover o nó 8 Remoção Caso 3 : O nó tem dois filhos O caso mais complicado ocorre quando o nó a ser removido tem dois filhos (ou seja, é pai de uma subárvore esquerda e de uma subárvore direita). Um algoritmo possível é conhecido como remoção por cópia. Remoção Caso 3 : O nó tem dois filhos O algoritmo consiste em encontrar o sucessor (ou predecessor) imediato do nó a ser removido e substituir este nó por seu sucessor (ou predecessor). O sucessor de um nó X é o nó com a menor chave maior que X Filho mais à esquerda, da subárvore da direita de X Se o sucessor for folha, basta copiar a chave e os dados satélites do sucessor para o lugar do nó X e remover o sucessor. Se o sucessor tiver um filho, faz a remoção do sucessor e copia os dados do sucessor para o lugar do nó X. Remoção Exemplo : Remover o nó 4 Passo 1 : tem dois filhos Passo 2 : encontra sucessor – 5 Passo 3 : 5 é folha Passo 4 : copia os dados do sucessor para o nó a ser removido. Passo 5 : remove a folha Remoção Exemplo : Remover o nó 7 Passo 1 : tem dois filhos Passo 2 : encontra sucessor – 8 Passo 3 : 8 tem um filho Passo 4 : copia os dados do sucessor para o nó a ser removido. Passo 5 : remove o nó com 1 filho Remoção Exercício Dada a árvore abaixo, remover sucessivamente os nós 13, 16, 5 e 20, utilizando o sucessor. Remoção Exercício Dada a árvore abaixo, remover sucessivamente os nós 13, 16, 5 e 20, utilizando o predecessor. Remoção Vamos implementar?? Remoção Remoção Para casa: Implementar as funções: Considerações Dependendo da ordem das Inserções e da quantidade de remoções sucessivas, a árvore pode tornar-se desbalanceada. Problema : a árvore pode virar uma lista. Perde-se a característica de árvore e as vantagens associadas a ela. Considerações Dependendo da ordem das Inserções e da quantidade de remoções sucessivas, a árvore pode tornar-se desbalanceada. Problema : a árvore pode virar uma lista. Perde-se a característica de árvore e as vantagens associadas a ela. SOLUÇÃO: Balanceamento
Compartilhar