Arvores Binarias de Pesquisa-Insercao e Algoritmos de Busca

ESTRUTURA DE DADOS II 60 HORAS PROF JULIANO RATUSZNEI EMAIL JULIANORATUSZNEIUNICIDEDUBR 2 INSERÇÃO EM ÁRVORES BINÁRIAS DE PESQUISA Como codificar as regras de árvore binária em um procedimento de inserção de modo que as regras de árvore binária sejam aplicadas a cada nodo inserido Sem indicação explicitamente onde os nodos devem ficar Desafio construir uma função para inserir nodos em uma árvore binária de pesquisa encontrar o ponto onde cada nodo deve ser inserido 3 INSERÇÃO EM ÁRVORES BINÁRIAS DE PESQUISA Para encontrar o ponto de inserção de um nodo em uma árvore binária de pesquisa precisamos observar as propriedades dessas árvores dado um nodo qualquer nodos menores do que ele são inseridos à sua esquerda nodos maiores do que ele são inseridos à sua direita Desafio como transformar essas ideias em código 4 INSERÇÃO EM ÁRVORES BINÁRIAS DE PESQUISA 5 ALGORITMO DE BUSCAS EM ÁRVORES BINÁRIAS DE PESQUISA O algoritmo de busca em árvores binárias de pesquisa pode ser dividido em três casos A chave procurada está na raiz da árvore Nesse caso simplesmente retornamos a raiz da árvore como resultado da busca A chave procurada é menor que a chave do nodo raiz Nesse caso precisamos procurar pela chave somente na subárvore esquerda A chave procurada é maior que a chave do nodo raiz Nesse caso precisamos procurar pela chave somente na subárvore direita A implementação da ideia acima assim como o tratamento do caso em que o nodo não está presente na árvore 6 ALGORITMO DE BUSCAS EM ÁRVORES BINÁRIAS DE PESQUISA ÁRVORES BINÁRIAS DE PESQUISA Apesar de alguns conceitos de árvores parecerem complexos somos capazes de implementálos com relativa facilidade Isso se deve ao fato de que a maioria dos conceitos de árvores possuírem uma natureza inerentemente recursiva A recursividade acaba sendo natural e simples Portanto sempre que você se deparar com um problema envolvendo árvores tente pensar em uma solução recursiva antes de mais nada 7 ESTRUTURA DE DADOS II 60 HORAS PROF JULIANO RATUSZNEI EMAIL JULIANORATUSZNEIUNICIDEDUBR ÁRVORES AVL 35 9 11 50 121 42 Na aula anterior foi abordado que a inserção de elementos em uma Árvore de Busca Binária determina a sua característica Dependendo da maneira de inserir os valores 9 35 9 11 50 121 42 ÁRVORES AVL 35 9 11 50 121 42 Qual a Problemática nesse caso para busca A árvore de busca podese tornar mais ou menos eficiente ao realizar uma busca Como contornar isso 10 35 9 11 50 121 42 ÁRVORES AVL 35 9 11 50 121 42 Devemos nesse caso balancear a carga entre os galhos da árvore Devemos entender que não existe balanceamento perfeito Basicamente o balanceamento perfeito é algo com custo elevado para computação Devese nesse caso criar um balanceamento razoavelmente bom Em tempo hábil e que realize a tarefa esperada 11 35 9 11 50 121 42 ÁRVORES AVL Para o balanceamento bom temos o algoritmo De AdelsonVelskii e Landis Verificar a altura da árvore binária Consecutivamente verificar a altura de suas sub árvores da direita e da esquerda De maneira geral a altura dessas subárvores não deve ultrapassar ou 1 altura subárvore da esquerda altura subárvore da direita utilizando o módulo dessa diferença O valor encontrado e chamado de Fator de Balanceamento Fator de balanceamento alturaNóEsquerda alturaNóDireita 35 9 11 50 121 42 12 ÁRVORES AVL O fator de balanceamento deve ser calculado a cada nó Respeitando a regra De maneira geral a altura dessas subárvores não deve ultrapassar ou 1 árvore vazia não possui nó na computação ela é chamada de altura 1 Isto serve para nós filhos vazios 13 14 ÁRVORES AVL VERIFICANDO BALANCEAMENTO 35 9 50 121 42 0 0 0 1 2 Altura dos nós AVL 35 9 150 50 121 42 0 0 0 1 1 2 Altura dos nós 1 15 35 9 150 50 121 42 151 ÁRVORES AVL VERIFICANDO BALANCEAMENTO Altura dos nós AVL 0 0 0 1 1 2 1 3 1 35 9 150 50 121 42 ÁRVORES AVL 35 9 150 50 121 42 151 Em apenas uma inserção podemos ter o desbalanceamento da árvore Isto é um nó com Fator de balanceamento ou 2 Notem que apenas o lado onde foi inserido o nó está desbalanceado o restante da árvore não foi modificado Portanto podemos concluir que o problema está na inserção De maneira geral na subárvore inserida todos os nós sofreram mudança de altura Outro fator importante é que nesse momento temos um caso peculiar de simples e pequeno de desbalanceamento 16 0 1 2 3 ÁRVORES AVL 35 9 150 50 121 42 151 Para ajustar o fator de balanceamento podemos rotacionar essa subárvore em torno do nó desbalanceado E é nesse ponto que AdelsonVelskii e Landis propuseram as rotações de um nó 17 0 1 2 3 A Ins B B A Ins A B α β µ ÁRVORES AVL OPERAÇÕES DE ROTAÇÃO Rotação a esquerda vai da direita para a esquerda portanto esquerda 18 A B α β µ ÁRVORES AVL OPERAÇÕES DE ROTAÇÃO Rotação a direita vai da esquerda para a direita portanto estado final direita 19 B A α β µ B A α β µ ÁRVORES AVL OPERAÇÕES DE ROTAÇÃO Rotação a esquerda Rotação a direita 20 A Ins B B A Ins A B Ins A B Ins ÁRVORES AVL OPERAÇÕES DE ROTAÇÃO Exemplo inserção de 151 21 35 9 150 50 121 42 151 150 50 121 151 35 42 9 AVL Não AVL ÁRVORES AVL OPERAÇÕES DE ROTAÇÃO EXTERNA B A α β µ Pressupomos a inserção de um nó nesta árvore 22 H H H H1 H2 C ÁRVORES AVL OPERAÇÕES DE ROTAÇÃO EXTERNA B A α β µ Pressupomos a inserção de um nó nesta árvore Logo desbalanceou toda a árvore Logo rotacionamos para direita 23 H1 H H H2 H3 C H B A α β µ C H2 H H H H1 H1 AVL 24 ÁRVORES AVL OPERAÇÕES DE ROTAÇÃO Rotações na parte externa são chamadas de rotações simples Rotação a direita e rotação a esquerda Entretanto quando a inserção for internamente da árvore devemos fazer rotações duplas ÁRVORES AVL OPERAÇÕES DE ROTAÇÃO INTERNA B A α β µ Pressupomos a inserção de um nó nesta árvore Vamos rotacionar 25 H H 1 H H2 H3 C H B A α β µ C H H H H 1 H 2 H3 Passei o problema adiante ÁRVORES AVL OPERAÇÕES DE ROTAÇÃO INTERNA B A α β µ Vamos tornar a arvore em uma rotacão externa 26 H H 1 H H2 H3 C H B A α β µ C ÁRVORES AVL OPERAÇÕES DE ROTAÇÃO INTERNA B A α β µ Vamos tornar a arvore em uma rotacão externa 27 H H 1 H H2 H3 C H B A α β µ C ÁRVORES AVL OPERAÇÕES DE ROTAÇÃO INTERNA B A α β µ Vamos tornar a arvore em uma rotacão externa 28 H H 1 H H2 H3 C H B A α β µ C B A α β µ C AVL H H H H 1 H 1 H 2 29 ÁRVORES AVL OPERAÇÕES DE ROTAÇÃO Regras Inserção a direita no filho à direita rotação a esquerda Inserção a esquerda no filho à esquerda rotação a direita Inserção a direita no filho à esquerda rotação esquerdadireita Inserção a esquerda no filho à direita rotação direitaesquerda B A ins B A ins B A ins B A ins 30 ÁRVORES AVL OPERAÇÕES DE ROTAÇÃO Inserção a direita no filho à esquerda rotação esquerdadireita Inserção a esquerda no filho à direita rotação direitaesquerda B A ins B A ins B A ins B A ins B A ins B A ins 31 ÁRVORES AVL OPERAÇÕES DE ROTAÇÃO Regras Inserção a direita no filho à direita rotação a esquerda Inserção a esquerda no filho à esquerda rotação a direita Inserção a direita no filho à esquerda rotação esquerdadireita Inserção a esquerda no filho à direita rotação direitaesquerda B A ins B A ins B A ins B A ins