Baixe o app para aproveitar ainda mais
Prévia do material em texto
Estrutura de Dados II Prof. Gilberto Vieira da Silva Árvores Balanceadas Objetivos • Entender o conceito de balanceamento, e sua importância para a eficiência das árvores de busca binárias (ABB); • Entender a lógica do processo de • Entender a lógica do processo de balanceamento de uma ABB; • Desenvolver habilidade para adaptar a lógica do balanceamento a novas situações, e para a elaboração de algoritmos sobre árvores binárias de busca balanceadas. Objetivos Objetivos Problemas com ABB Exercício 1: a) Dada uma ABB inicialmente vazia, insira (desenhe) os seguintes elementos (nessa ordem): M, F, S, D, J, P, U.ordem): M, F, S, D, J, P, U. Exercício 2: b) Dada uma ABB inicialmente vazia, insira (desenhe) os seguintes elementos (nessa ordem): A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z. Problemas com ABB Comparando as respostas dos exercícios 1 e 2: Problemas com ABB Comparando as respostas dos exercícios 1 e 2: Problemas com ABB Porque? Porque? Considere uma ABB uniformemente distribuída. Do nível 0 ao nível 2 cabem 7 elementos, mas temos que visitar apenas 3 nós para identificar se X está ou não na árvore. Problemas com ABB Então, como podemos identificar quantos elementos cabem em uma árvore binária: Nr elementos = (2n+1) – 1 Nível Quantos Cabem 0 1 1 3 2 7 3 15 Nr elementos = (2 ) – 1 Conforme pode ser observado, para identificar se X está em uma árvore com 1 milhão de registros é necessário visitar apenas 20 nós, incluindo a raiz 3 15 4 31 N (2n+1)-1 9 1023 12 8192 15 65.536 19 1 milhão 29 1 bilhão 39 1 trilhão Problemas com ABB Então, essa eficiência na busca por um elemento ocorre somente quando a árvore está corretamente balanceada. Definição de uma ABB Balanceada Uma árvore de busca binária é dita balanceada Uma árvore de busca binária é dita balanceada (ou ABBB, ou ainda árvore AVL) se e somente se para cada nó a altura de suas sub-árvores diferem de, no máximo, 1. Definição de uma ABB Balanceada Exemplos: Exercício: Considere a figura ao lado: • A inserção da chave 25 causaria desbalanceamento? •A inserção da chave 40 causaria desbalanceamento (considere a árvore como mostra a figura, sem a chave 25)? • A inserção da chave 9 causaria desbalanceamento (considere a árvore como mostra a figura, sem as chaves 25 e 40)? Exercício: Continuação:Continuação: • A inserção da chave 13 causaria desbalanceamento (considere a árvore como mostra a figura, sem as chaves 9, 25 e 40)? •A inserção da chave 17 causaria desbalanceamento (considere a árvore como mostra a figura, sem as chaves 9, 13, 25 e 40)? • A inserção da chave 21 causaria desbalanceamento (considere a árvore como mostra a figura, sem as chaves 9, 13, 17, 25 e 40)? Processo de Processo de RebalanceamentoRebalanceamentoRebalanceamentoRebalanceamento Caso do Algoritmo InsereCaso do Algoritmo Insere Rebalanceamento Caso 1: Caso 1: Rotação Simples: Esquerda-Esquerda (EE) Pense:Pense: Chave inserida causando o desbalanceamento da árvore. He = 2 e Hd = 0 Como a árvore poderia ser ajustada, de modo a ficar balanceada? Rebalanceamento Caso 1: Caso 1: Rotação Simples: Esquerda-Esquerda (EE) Desenhe uma nova ABB, e Desenhe uma nova ABB, e balanceadabalanceadabalanceadabalanceada Rebalanceamento Caso 2: Caso 2: Rotação Simples: Esquerda-Esquerda (EE) Chave inserida causando o desbalanceamento da árvore. He = 3 e Hd = 1 Rebalanceamento Caso 2: Caso 2: Rotação Simples: Esquerda-Esquerda (EE) Passo 1: Passo 2: Passo 1: Reposicionar a raiz e as chaves principais Passo 2: Reposicionar as demais chaves da árvore Cross Over Rebalanceamento Caso 3: Caso 3: Rotação Simples: Esquerda-Esquerda (EE) NOTA: �Para identificar o nó que desbalanceou, siga “de baixo para cima”, a partir da chave Chave inserida causando o desbalanceamento da árvore. He = 3 e Hd = 1 siga “de baixo para cima”, a partir da chave que acabou de ser inserida. Considere a primeira chave que achar desbalanceada, nesse caminho “de baixo para cima”. Rebalanceamento Caso 3: Caso 3: Rotação Simples: Esquerda-Esquerda (EE) Passo 1: Passo 2: Passo 1: Reposicionar a raiz e as chaves principais Passo 2: Reposicionar as demais chaves da árvore Exercícios Desenhe a nova árvore EE do Insere:Desenhe a nova árvore EE do Insere: Desenhe a nova árvore, resultante do rebalanceamento da árvore das figuras fornecidas. 1) Considere que a chave que acabou de ser inserida está indicada em vermelho. 2) A nova árvore deve ser uma árvore binária de busca, e deve ser balanceada. 3) Identifique a chave onde ocorreu o desbalanceamento, identifique as 3 chaves principais, posicione-as, e então posicione as demais chaves. Exercícios (Continuação) A) B) C) D) Rebalanceamento Caso 4: Caso 4: Rotação Simples: Direita-Direita (DD) Esta rotação segue a mesma simétrica da EE.Esta rotação segue a mesma simétrica da EE. Exercícios Desenhe a nova árvore DD do Insere:Desenhe a nova árvore DD do Insere: Desenhe a nova árvore, resultante do rebalanceamento da árvore das figuras fornecidas. 1) Considere que a chave que acabou de ser inserida está indicada em vermelho. 2) A nova árvore deve ser uma árvore binária de busca, e deve ser balanceada. 3) Identifique a chave onde ocorreu o desbalanceamento, identifique as 3 chaves principais, posicione-as, e então posicione as demais chaves. Exercícios (Continuação) A) B) C) D) Rebalanceamento Caso 5: Caso 5: Rotação Dupla: Esquerda-Direita (ED) Desbalanceada Balanceada Rebalanceamento Caso 6: Caso 6: Rotação Dupla: Esquerda-Direita (ED) Passo 1: Passo 2: Desbalanceada Árvore Balanceada Realocação das Chaves Cross Over Exercícios Desenhe a nova árvore ED do Insere:Desenhe a nova árvore ED do Insere: Desenhe a nova árvore, resultante do rebalanceamento da árvore das figuras fornecidas. 1) Considere que a chave que acabou de ser inserida está indicada em vermelho. 2) A nova árvore deve ser uma árvore binária de busca, e deve ser balanceada. 3) Identifique a chave onde ocorreu o desbalanceamento, identifique as 3 chaves principais, posicione-as, e então posicione as demais chaves. Exercícios (Continuação) A) B) C) D)
Compartilhar