Slide Árvores Avl-2022 1

Histórico • Inventada em por Georgy Maximovich Adelson-Velskii (Георгий Максимович Адельсон-Вельский) e Yevgeniy Mikhailovich Landis (Евгений Михайлович Ландис) e publicada em: "An algorithm for the organization of information. Trans. of Akademiya Nauk SSSR. Doklady, 1962, v. 146, no. 2, pp. 263-266 " Georgy Maximovich Adelson-Velskii (Samara, Rússia, 1922) Yevgeniy Mikhailovich Landis (Kharkov, Ucrânia, 1921) Arvores Binárias Semibalanceadas • Árvore Binária Balanceada: – max. dif. de altura: 1 – max. dif. de nº de nodos: 1 • Manter uma árvore binária de busca balanceada sob a presença de constantes inserções e deleções é ineficiente • Árvore Semibalanceada: – critério de balaceamento é relaxado (aproximado) – mais liberdade na definição de algoritmos – algoritmos mais eficientes – novo critério de semi-balanceamento depende do modelo a ser usado Características • Para contornar o problema do balanceamento absoluto foi criada a árvore AVL (Adelson-Velskii e Landis). • A árvore AVL é uma árvore binária com uma condição de balanço, porém não completamente balanceada. • Árvores AVL permitem inserção / deleção e rebalanceamento aceitavelmente rápidos. Características • Critério de balanceamento: • dado um nodo qualquer, uma árvore está AVL-balanceada se as alturas das duas subárvores deste nodo diferem de, no máximo, 1. • Para rebalancear uma árvore após uma inserção, são utilizadas rotações de subárvores: • rotações simples em muitos casos; • rotações duplas em alguns. Características Estrutura de um nodo na árvore AVL Estrutura nodoAVL { info : tipo_info; esq : *nodoAVL; dir : *nodoAVL; alt : inteiro; }; • O campo alt deve ser atualizado recursivamente quando um nodo for inserido ou deletado. Características • Para o retorno da altura de uma subárvore necessitamos de uma função especial – um nodo pode não ter um ou ambos os filhos – lembre-se que a pesquisa para garantir a condição-AVL é realizada perguntando-se a altura das duas subárvores inteiro altura( subárvore *nodoAVL) início se (subárvore for NULO) retorne -1; /* A altura de uma subárvore inexistente é definida como -1 */ senão retorne subárvore->alt; fim se fim Inclusão com rotação Exemplo de rebalanceamento: • o nodo com chave 6.5 desequilibrou a árvore. Com a rotação da subárvore em torno do nodo 7, rebalanceamos. 6 2 1 4 3 8 7 6,5 6 2 1 4 3 8 7 6,5 Inclusão com rotação Algoritmo básico: • partimos do nodo inserido e subimos a árvore; • atualizamos a informação do balanceamento em cada nodo (na árvore AVL, cada nodo conhece a sua altura); • se chegamos à raiz sem encontrar nada errado, terminamos; • caso encontremos um nodo desbalanceado (|altesq - altdir| < 2 ferida), realizamos a rotação no primeiro nodo desbalanceado encontrado. • No exemplo anterior, isto significa que, depois da inserção de 6.5, o nodo 8 ficou desbalanceado. Exemplo: criação de uma árvore AVL com os números de 1 a 7 O primeiro problema ocorre quando inserimos o 3. A condição-AVL foi violada. • executamos uma rotação simples entre a raiz (cuja condição-AVL está violada) e seu filho da direita. 1 2 3 1 2 3 Exemplo: criação de uma árvore AVL com os números de 1 a 7 • Inserimos o elemento 4 sem problemas. • Inserimos o elemento 5: violação em 3. • Mesmo processo da rotação anterior será seguido. • Importantíssimo: observe-se que 2 precisa ser notificado que seu filho agora é o nodo com chave 4. 1 2 3 4 5 1 2 3 4 5 Exemplo: criação de uma árvore AVL com os números de 1 a 7 A inclusão do elemento 6 desequilibra a raiz: • subárvore direita tem altura 0; • subárvore esquerda tem altura 2. Rotacionamos na raiz entre 2 e 4: • transformamos 2 em filho de 4; • subárvore esquerda original de 4 é agora subárvore direita de 2. Condição de ordem da árvore de busca é mantida. Exemplo: criação de uma árvore AVL com os números de 1 a 7 A inclusão de um nodo com chave 7 causa uma rotação como já havíamos visto antes: • 5 fica desequilibrado; • rotacionamos em 6. Inclusão com rotação simples à esquerda • Corresponde a uma rotação entre os nodos k2 e seu filho da esquerda, k1, envolvendo as subárvores A, B e C k1 B k2 A C Esta aresta é o ponto de desequilíbrio Devolvo k1 como a nova raiz desta subárvore Inclusão com rotação simples à esquerda nodoAVL *simp_roda_esq(k2 *nodoAVL) variáveis locais k1 : *nodoAVL; início k1 <- k2->esq; k2->esq <- k1->dir; k1->dir <- k2; /* atualize alturas */ k2->alt <- max(altura(k2->esq), altura(k2->dir)) + 1; k1->alt <- max(altura(k1->esq), k2->alt) + 1; retorne k1; /* nova raiz da subárvore */ fim Inclusão com rotação simples à direita nodoAVL *simp_roda_dir(k2 *nodoAVL) variáveis locais k1 : *nodoAVL; início k1 <- k2->dir; k2->dir <- k1->esq; k1->esq <- k2; /* atualize alturas */ k2->alt <- max(altura(k2->dir), altura(k2->esq)) + 1; k1->alt <- max(altura(k1->dir), k2->alt) + 1; retorne k1; /* nova raiz da subárvore */ fim Inclusão com rotação dupla O algoritmo descrito até agora tem um problema: • existem casos onde ele não basta para consertar a árvore após uma inclusão ou exclusão. Exemplo: inserimos as chaves 15 a 8, em ordem inversa, na árvore anterior. • a inserção de 15 não provoca problemas, nem desbalanceia a árvore; • a inserção de 14, por sua vez, faz o rebalanceamento falhar. Inclusão com rotação dupla • O problema que surge aqui é que tanto 7 como 14 são candidatos à subárvore esquerda de 15. • Neste caso, necessitamos de uma dupla rotação. Inclusão com rotação dupla • O processo é semelhante à rotação simples, só que envolve 4 subárvores: A, B, C e D • corresponderia a uma rotação efetuada primeiro entre k1 e k2 e depois entre k2 e k3. k3 k1 k2 A B D C k3 A B C D k2 k1 Inclusão com rotação dupla • P1: Rotação entre k1 e k2 k3 A k2 B k1 D C Inclusão com rotação dupla • P2: Rotação entre k2 e k3 k3 A k2 B D C k1 Devolvo k2 como a nova raiz desta subárvore Rotação dupla à esquerda • Exemplo simétrico ao anterior. k3 k1 k2 A B D C k3 A B C D k2 k1 Inclusão do elemento 14 com rotação dupla No exemplo, a rotação direita-esquerda envolve o 7, o 15 e o 14: • k3 é o nodo de chave 7, k1 o de chave 15 e k2 o de chave 14; • primeiro rotacionamos 14-15 à direita, depois 7-14 à esquerda. Inclusão do elemento 13 com rotação dupla • Novamente uma dupla rotação direita- esquerda: • desta vez a rotação envolverá 6 (k3), 14 (k1) e 7 (k2). Inclusão do elemento 12 • A inclusão do elemento 12 provoca um desequilíbrio na raiz: • como 12 não está entre 4 e 7, sabemos que uma rotação simples vai funcionar. Inclusão do elemento 11 • A inclusão do elemento 11 provoca um desequilíbrio logo embaixo: • como 11 não está entre 12 e 13, sabemos que uma rotação simples vai funcionar. Inclusão dos elementos 10, 9 e 8 • Os elementos 10 e 9 serão inseridos com rotação simples, e o elemento 8 sem rotação alguma. • Tente em casa • A árvore resultante será vista a seguir. Caso interessante: inclusão do elemento 8.5 Temos uma rotação dupla que parece ser uma simples Rotação Dupla à Esquerda • Função chamada somente se k3 possuir um filho à esquerda e se o filho à esquerda de k3 possuir um filho à direita. Ela realiza a rotação e atualiza as alturas das subárvores rotacionadas. nodoAVL *dup_roda_esq(k3 : *nodoAVL) início /* Rotacione entre k1 e k2 */ k3->esq <- simp_roda_dir( k3-> esq ); /* Rotacione entre k3 e k2 */ retorne ( simp_roda_esq( k3 ) ); fim • Da mesma forma que com a rotação simples, a rotação dupla à direita é a operação simétrica da rotação à esquerda e é facilmente implementada. Inserção em Árvore AVL nodoAVL *inserçãoAVL(info : tipo_info, arv : *nodoAVL, pai : *nodoAVL) v variáveis arv_rodada : *nodoAVL; início se (arv é NULO) então /* Folha: aloca novo nodo */ arv <- aloca novo nodo; se (arv é NULO) então retorne ERRO; arv->info <- info; arv->alt <- 0; arv->esq <- NULO; arv->dir <- NULO; senão se (info < arv->info) então arv->esq <- inserçãoAVL(info, arv->esq, arv); se ((altura(arv->esq) - altura(arv->dir) > 1) então se (info < arv->esq->info) então arv_rodada <- simp_roda_esq(arv); senão arv_rodada <- dup_roda_esq(arv); fim se se (pai->esq = arv) então pai->esq <- arv_rodada; senão pai->dir <- arv_rodada; fim se senão arv->alt <- max( altura(arv->esq), altura(arv->dir)) + 1; fim se senão se (info > arv->info) então /* caso simétrico para árvore direita */ senão retorne ERRO: ,,chave já está na árvore" fim se fim se fim se retorne arv; fim Inserção em Árvore AVL nodoAVL *inserçãoAVL(info : tipo_info, arv : *nodoAVL, pai : *nodoAVL) variáveis arv_rodada : *nodoAVL; início se (arv é NULO) então /* Folha: aloca novo nodo */ arv <- aloca novo nodo; se (arv é NULO) então retorne ERRO; arv->info <- info; arv->alt <- 0; arv->esq <- NULO; arv->dir <- NULO; senão se (info < arv->info) então arv->esq <- inserçãoAVL(info, arv->esq, arv); se ((altura(arv->esq) - altura(arv->dir) > 1) então se (info < arv->esq->info) então arv_rodada <- simp_roda_esq(arv); senão arv_rodada <- dup_roda_esq(arv); fim se se (pai->esq = arv) então pai->esq <- arv_rodada; senão pai->dir <- arv_rodada; fim se senão arv->alt <- max( altura(arv->esq), altura(arv->dir)) + 1; fim se senão se (info > arv->info) então /* caso simétrico para árvore direita */ senão retorne ERRO: ,,chave já está na árvore" fim se fim se fim se retorne arv; fim nodoAVL *inserçãoAVL(info : tipo_info, arv : *nodoAVL, pai : *nodoAVL) variáveis arv_rodada : *nodoAVL; início se (arv é NULO) então /* Folha: aloca novo nodo */ arv <- aloca novo nodo; se (arv é NULO) então retorne ERRO; arv->info <- info; arv->alt <- 0; arv->esq <- NULO; arv->dir <- NULO; senão se (info < arv->info) então arv->esq <- inserçãoAVL(info, arv->esq, arv); se ((altura(arv->esq) - altura(arv->dir) > 1) então se (info < arv->esq->info) então arv_rodada <- simp_roda_esq(arv); senão arv_rodada <- dup_roda_esq(arv); fim se se (pai->esq = arv) então pai->esq <- arv_rodada; senão pai->dir <- arv_rodada; fim se senão arv->alt <- max( altura(arv->esq), altura(arv->dir)) + 1; fim se senão se (info > arv->info) então /* caso simétrico para árvore direita */ senão retorne ERRO: ,,chave já está na árvore" fim se fim se fim se retorne arv; fim Inserção em Árvore AVL nodoAVL *inserçãoAVL(info : tipo_info, arv : *nodoAVL, pai : *nodoAVL) variáveis arv_rodada : *nodoAVL; início se (arv é NULO) então /* Folha: aloca novo nodo */ arv <- aloca novo nodo; se (arv é NULO) então retorne ERRO; arv->info <- info; arv->alt <- 0; arv->esq <- NULO; arv->dir <- NULO; senão se (info < arv->info) então arv->esq <- inserçãoAVL(info, arv->esq, arv); se ((altura(arv->esq) - altura(arv->dir) > 1) então se (info < arv->esq->info) então arv_rodada <- simp_roda_esq(arv); senão arv_rodada <- dup_roda_esq(arv); fim se se (pai->esq = arv) então pai->esq <- arv_rodada; senão pai->dir <- arv_rodada; fim se senão arv->alt <- max( altura(arv->esq), altura(arv->dir)) + 1; fim se senão se (info > arv->info) então /* caso simétrico para árvore direita */ senão retorne ERRO: ,,chave já está na árvore" fim se fim se fim se retorne arv; fim nodoAVL *inserçãoAVL(info : tipo_info, arv : *nodoAVL, pai : *nodoAVL) variáveis arv_rodada : *nodoAVL; início se (arv é NULO) então /* Folha: aloca novo nodo */ arv <- aloca novo nodo; se (arv é NULO) então retorne ERRO; arv->info <- info; arv->alt <- 0; arv->esq <- NULO; arv->dir <- NULO; senão se (info < arv->info) então arv->esq <- inserçãoAVL(info, arv->esq, arv); se ((altura(arv->esq) - altura(arv->dir) > 1) então se (info < arv->esq->info) então arv_rodada <- simp_roda_esq(arv); senão arv_rodada <- dup_roda_esq(arv); fim se se (pai->esq = arv) então pai->esq <- arv_rodada; senão pai->dir <- arv_rodada; fim se senão arv->alt <- max( altura(arv->esq), altura(arv->dir)) + 1; fim se senão se (info > arv->info) então /* caso simétrico para árvore direita */ senão retorne ERRO: ,,chave já está na árvore" fim se fim se fim se retorne arv; fim Inserção em Árvore AVL nodoAVL *inserçãoAVL(info : tipo_info, arv : *nodoAVL, pai : *nodoAVL) variáveis arv_rodada : *nodoAVL; início se (arv é NULO) então /* Folha: aloca novo nodo */ arv <- aloca novo nodo; se (arv é NULO) então retorne ERRO; arv->info <- info; arv->alt <- 0; arv->esq <- NULO; arv->dir <- NULO; senão se (info < arv->info) então arv->esq <- inserçãoAVL(info, arv->esq, arv); se ((altura(arv->esq) - altura(arv->dir) > 1) então se (info < arv->esq->info) então arv_rodada <- simp_roda_esq(arv); senão arv_rodada <- dup_roda_esq(arv); fim se se (pai->esq = arv) então pai->esq <- arv_rodada; senão pai->dir <- arv_rodada; fim se senão arv->alt <- max( altura(arv->esq), altura(arv->dir)) + 1; fim se senão se (info > arv->info) então /* caso simétrico para árvore direita */ senão retorne ERRO: ,,chave já está na árvore" fim se fim se fim se retorne arv; fim nodoAVL *inserçãoAVL(info : tipo_info, arv : *nodoAVL, pai : *nodoAVL) variáveis arv_rodada : *nodoAVL; início se (arv é NULO) então /* Folha: aloca novo nodo */ arv <- aloca novo nodo; se (arv é NULO) então retorne ERRO; arv->info <- info; arv->alt <- 0; arv->esq <- NULO; arv->dir <- NULO; senão se (info < arv->info) então arv->esq <- inserçãoAVL(info, arv->esq, arv); se ((altura(arv->esq) - altura(arv->dir) > 1) então se (info < arv->esq->info) então arv_rodada <- simp_roda_esq(arv); senão arv_rodada <- dup_roda_esq(arv); fim se se (pai->esq = arv) então pai->esq <- arv_rodada; senão pai->dir <- arv_rodada; fim se senão arv->alt <- max( altura(arv->esq), altura(arv->dir)) + 1; fim se senão se (info > arv->info) então /* caso simétrico para árvore direita */ senão retorne ERRO: ,,chave já está na árvore" fim se fim se fim se retorne arv; fim Verifica se vai rodar Inserção em Árvore AVL nodoAVL *inserçãoAVL(info : tipo_info, arv : *nodoAVL, pai : *nodoAVL) variáveis arv_rodada : *nodoAVL; início se (arv é NULO) então /* Folha: aloca novo nodo */ arv <- aloca novo nodo; se (arv é NULO) então retorne ERRO; arv->info <- info; arv->alt <- 0; arv->esq <- NULO; arv->dir <- NULO; senão se (info < arv->info) então arv->esq <- inserçãoAVL(info, arv->esq, arv); se ((altura(arv->esq) - altura(arv->dir) > 1) então se (info < arv->esq->info) então arv_rodada <- simp_roda_esq(arv); senão arv_rodada <- dup_roda_esq(arv); fim se se (pai->esq = arv) então pai->esq <- arv_rodada; senão pai->dir <- arv_rodada; fim se senão arv->alt <- max( altura(arv->esq), altura(arv->dir)) + 1; fim se senão se (info > arv->info) então /* caso simétrico para árvore direita */ senão retorne ERRO: ,,chave já está na árvore" fim se fim se fim se retorne arv; fim nodoAVL *inserçãoAVL(info : tipo_info, arv : *nodoAVL, pai : *nodoAVL) variáveis arv_rodada : *nodoAVL; início se (arv é NULO) então /* Folha: aloca novo nodo */ arv <- aloca novo nodo; se (arv é NULO) então retorne ERRO; arv->info <- info; arv->alt <- 0; arv->esq <- NULO; arv->dir <- NULO; senão se (info < arv->info) então arv->esq <- inserçãoAVL(info, arv->esq, arv); se ((altura(arv->esq) - altura(arv->dir) > 1) então se (info < arv->esq->info) então arv_rodada <- simp_roda_esq(arv); senão arv_rodada <- dup_roda_esq(arv); fim se se (pai->esq = arv) então pai->esq <- arv_rodada; senão pai->dir <- arv_rodada; fim se senão arv->alt <- max( altura(arv->esq), altura(arv->dir)) + 1; fim se senão se (info > arv->info) então /* caso simétrico para árvore direita */ senão retorne ERRO: ,,chave já está na árvore" fim se fim se fim se retorne arv; fim Verifica o tipo de rotação e roda Inserção em Árvore AVL nodoAVL *inserçãoAVL(info : tipo_info, arv : *nodoAVL, pai : *nodoAVL) variáveis arv_rodada : *nodoAVL; início se (arv é NULO) então /* Folha: aloca novo nodo */ arv <- aloca novo nodo; se (arv é NULO) então retorne ERRO; arv->info <- info; arv->alt <- 0; arv->esq <- NULO; arv->dir <- NULO; senão se (info < arv->info) então arv->esq <- inserçãoAVL(info, arv->esq, arv); se ((altura(arv->esq) - altura(arv->dir) > 1) então se (info < arv->esq->info) então arv_rodada <- simp_roda_esq(arv); senão arv_rodada <- dup_roda_esq(arv); fim se se (pai->esq = arv) então pai->esq <- arv_rodada; senão pai->dir <- arv_rodada; fim se senão arv->alt <- max( altura(arv->esq), altura(arv->dir)) + 1; fim se senão se (info > arv->info) então /* caso simétrico para árvore direita */ senão retorne ERRO: ,,chave já está na árvore" fim se fim se fim se retorne arv; fim nodoAVL *inserçãoAVL(info : tipo_info, arv : *nodoAVL, pai : *nodoAVL) variáveis arv_rodada : *nodoAVL; início se (arv é NULO) então /* Folha: aloca novo nodo */ arv <- aloca novo nodo; se (arv é NULO) então retorne ERRO; arv->info <- info; arv->alt <- 0; arv->esq <- NULO; arv->dir <- NULO; senão se (info < arv->info) então arv->esq <- inserçãoAVL(info, arv->esq, arv); se ((altura(arv->esq) - altura(arv->dir) > 1) então se (info < arv->esq->info) então arv_rodada <- simp_roda_esq(arv); senão arv_rodada <- dup_roda_esq(arv); fim se se (pai->esq = arv) então pai->esq <- arv_rodada; senão pai->dir <- arv_rodada; fim se senão arv->alt <- max( altura(arv->esq), altura(arv->dir)) + 1; fim se senão se (info > arv->info) então /* caso simétrico para árvore direita */ senão retorne ERRO: ,,chave já está na árvore" fim se fim se fim se retorne arv; fim Faz pai apontar para k2 nodoAVL *inserçãoAVL(info : tipo_info, arv : *nodoAVL, pai : *nodoAVL) variáveis arv_rodada : *nodoAVL; início se (arv é NULO) então /* Folha: aloca novo nodo */ arv <- aloca novo nodo; se (arv é NULO) então retorne ERRO; arv->info <- info; arv->alt <- 0; arv->esq <- NULO; arv->dir <- NULO; senão se (info < arv->info) então arv->esq <- inserçãoAVL(info, arv->esq, arv); se ((altura(arv->esq) - altura(arv->dir) > 1) então se (info < arv->esq->info) então arv_rodada <- simp_roda_esq(arv); senão arv_rodada <- dup_roda_esq(arv); fim se se (pai->esq = arv) então pai->esq <- arv_rodada; senão pai->dir <- arv_rodada; fim se senão arv->alt <- max( altura(arv->esq), altura(arv->dir)) + 1; fim se senão se (info > arv->info) então /* caso simétrico para árvore direita */ senão retorne ERRO: ,,chave já está na árvore" fim se fim se fim se retorne arv; fim Inserção em Árvore AVL nodoAVL *inserçãoAVL(info : tipo_info, arv : *nodoAVL, pai : *nodoAVL) variáveis arv_rodada : *nodoAVL; início se (arv é NULO) então /* Folha: aloca novo nodo */ arv <- aloca novo nodo; se (arv é NULO) então retorne ERRO; arv->info <- info; arv->alt <- 0; arv->esq <- NULO; arv->dir <- NULO; senão se (info < arv->info) então arv->esq <- inserçãoAVL(info, arv->esq, arv); se ((altura(arv->esq) - altura(arv->dir) > 1) então se (info < arv->esq->info) então arv_rodada <- simp_roda_esq(arv); senão arv_rodada <- dup_roda_esq(arv); fim se se (pai->esq = arv) então pai->esq <- arv_rodada; senão pai->dir <- arv_rodada; fim se senão arv->alt <- max( altura(arv->esq), altura(arv->dir)) + 1; fim se senão se (info > arv->info) então /* caso simétrico para árvore direita */ senão retorne ERRO: ,,chave já está na árvore" fim se fim se fim se retorne arv; fim Ajusta altura deste nodo aqui Inserção em Árvore AVL nodoAVL *inserçãoAVL(info : tipo_info, arv : *nodoAVL, pai : *nodoAVL) variáveis arv_rodada : *nodoAVL; início se (arv é NULO) então /* Folha: aloca novo nodo */ arv <- aloca novo nodo; se (arv é NULO) então retorne ERRO; arv->info <- info; arv->alt <- 0; arv->esq <- NULO; arv->dir <- NULO; senão se (info < arv->info) então arv->esq <- inserçãoAVL(info, arv->esq, arv); se ((altura(arv->esq) - altura(arv->dir) > 1) então se (info < arv->esq->info) então arv_rodada <- simp_roda_esq(arv); senão arv_rodada <- dup_roda_esq(arv); fim se se (pai->esq = arv) então pai->esq <- arv_rodada; senão pai->dir <- arv_rodada; fim se senão arv->alt <- max( altura(arv->esq), altura(arv->dir)) + 1; fim se senão se (info > arv->info) então /* caso simétrico para árvore direita */ senão retorne ERRO: ,,chave já está na árvore" fim se fim se fim se retorne arv; fim nodoAVL *inserçãoAVL(info : tipo_info, arv : *nodoAVL, pai : *nodoAVL) variáveis arv_rodada : *nodoAVL; início se (arv é NULO) então /* Folha: aloca novo nodo */ arv <- aloca novo nodo; se (arv é NULO) então retorne ERRO; arv->info <- info; arv->alt <- 0; arv->esq <- NULO; arv->dir <- NULO; senão se (info < arv->info) então arv->esq <- inserçãoAVL(info, arv->esq, arv); se ((altura(arv->esq) - altura(arv->dir) > 1) então se (info < arv->esq->info) então arv_rodada <- simp_roda_esq(arv); senão arv_rodada <- dup_roda_esq(arv); fim se se (pai->esq = arv) então pai->esq <- arv_rodada; senão pai->dir <- arv_rodada; fim se senão arv->alt <- max( altura(arv->esq), altura(arv->dir)) + 1; fim se senão se (info > arv->info) então /* caso simétrico para árvore direita */ arv->dir <- inserçãoAVL(info, arv->dir, arv); se ((altura(arv->dir) - altura(arv->esq) > 1) se (info < arv->dir->info) então arv_rodada <- simp_roda_dir(arv); senão arv_rodada <- dup_roda_dir(arv); fim se se (pai->dir = arv) então pai->dir <- arv_rodada; senão pai->esq <- arv_rodada; fim se senão arv->alt <- max( altura(arv->esq), altura(arv->dir)) + 1; fim se senão retorne “ERRO: chave já está na árvore" fim se fim se fim se retorne arv; fim Inserção em Árvore AVL nodoAVL *inserçãoAVL(info : tipo_info, arv : *nodoAVL, pai : *nodoAVL) variáveis arv_rodada : *nodoAVL; início se (arv é NULO) então /* Folha: aloca novo nodo */ arv <- aloca novo nodo; se (arv é NULO) então retorne ERRO; arv->info <- info; arv->alt <- 0; arv->esq <- NULO; arv->dir <- NULO; senão se (info < arv->info) então arv->esq <- inserçãoAVL(info, arv->esq, arv); se ((altura(arv->esq) - altura(arv->dir) > 1) então se (info < arv->esq->info) então arv_rodada <- simp_roda_esq(arv); senão arv_rodada <- dup_roda_esq(arv); fim se se (pai->esq = arv) então pai->esq <- arv_rodada; senão pai->dir <- arv_rodada; fim se senão arv->alt <- max( altura(arv->esq), altura(arv->dir)) + 1; fim se senão se (info > arv->info) então /* caso simétrico para árvore direita */ senão retorne ERRO: ,,chave já está na árvore" fim se fim se fim se retorne arv; fim nodoAVL *inserçãoAVL(info : tipo_info, arv : *nodoAVL, pai : *nodoAVL) variáveis arv_rodada : *nodoAVL; início se (arv é NULO) então /* Folha: aloca novo nodo */ arv <- aloca novo nodo; se (arv é NULO) então retorne ERRO; arv->info <- info; arv->alt <- 0; arv->esq <- NULO; arv->dir <- NULO; senão se (info < arv->info) então arv->esq <- inserçãoAVL(info, arv->esq, arv); se ((altura(arv->esq) - altura(arv->dir) > 1) então se (info < arv->esq->info) então arv_rodada <- simp_roda_esq(arv); senão arv_rodada <- dup_roda_esq(arv); fim se se (pai->esq = arv) então pai->esq <- arv_rodada; senão pai->dir <- arv_rodada; fim se senão arv->alt <- max( altura(arv->esq), altura(arv->dir)) + 1; fim se senão se (info > arv->info) então /* caso simétrico para árvore direita */ arv->dir <- inserçãoAVL(info, arv->dir, arv); se ((altura(arv->dir) - altura(arv->esq) > 1) se (info < arv->dir->info) então arv_rodada <- simp_roda_dir(arv); senão arv_rodada <- dup_roda_dir(arv); fim se se (pai->dir = arv) então pai->dir <- arv_rodada; senão pai->esq <- arv_rodada; fim se senão arv->alt <- max( altura(arv->esq), altura(arv->dir)) + 1; fim se senão retorne “ERRO: chave já está na árvore" fim se fim se fim se retorne arv; fim Caso simétrico: lembre de espelhar! Deleção em Árvore AVL • Busque a chave a deletar na árvore • Delete utilizando o algoritmo recursivo de Deleção da Árvore Binária de Busca (DABB)  Visto em aula • Modifique DABB para: – Logo após retorno da chamada recursiva atualizar & verificar alturas das subárvores filhas – Aplicar “regra do zique-zague” se necessário Deleção em Árvore AVL • “regra do zigue-zague”: – Olhar subárvore que desequilibrou e seus filhos – Desequilíbrio é à esquerda: • Sub-subárvore esquerda é a mais funda? – Esquerda-esquerda: rotação simples à esquerda • Sub-subárvore direita é a mais funda? – Esquerda-direita: rotação dupla à esquerda – Desequilíbrio é à direita: • Sub-subárvore direita é a mais funda? – Direita-direita: rotação simples à direita • Sub-subárvore esquerda é a mais funda? – Direita-esquerda: rotação dupla à direita Analisar filhos e netos do nodo desequilibrado Rebalanceamento após exclusão com rotação simples à direita • Direita-direita: Rotação entre k2 e k3 k3 A k1 B D C k2 Devolvo k1 como a nova raiz desta subárvore Desequilíbrio identificado em k3 Subárvore causadora é direita (k1) Sub-subárvore mais funda é direita (k2) Rebalanceamento após exclusão com rotação dupla à direita • P1: Rotação à esquerda entre k1 e k2 k3 A k2 B k1 D C Desequilíbrio identificado em k3 Subárvore causadora é direita (k1) Sub-subárvore mais funda é esquerda (k2) Rebalanceamento após exclusão com rotação dupla à direita • P2: Rotação à direita: Rotação entre k2 e k3 k3 A k2 B D C k1 Devolvo k2 como a nova raiz desta subárvore Resumindo: regras de deleção (à esquerda) Esquerda-esquerda k3 k1 / \ / \ k1 A rot.simples à esq. k2 k3 / \ - - - - - - - - -> / \ / \ k2 B D C B A / \ D C Esquerda-direita k3 k3 k2 / \ / \ / \ k1 T4 rot.dir.(k1) k2 T4 rot.esq.(k3) k1 k3 / \ - - - - - -> / \ - - - - - -> / \ / \ T1 k2 k1 T3 T1 T2 T3 T4 / \ / \ T2 T3 T1 T2 Resumindo: regras de deleção (à direita) Direita-direita k3 k1 / \ / \ A k1 rot.simples à dir. k3 k2 / \ - - - - - - - - -> / \ / \ B k2 A B C D / \ C D Direita-esquerda k3 k3 k2 / \ / \ / \ A k1 rot.esq.(k1) A k2 rot.dir.(k3) k3 k1 / \ - - - - - -> / \ - - - - - -> / \ / \ k2 D B k1 A B C D / \ / \ B C C D Relembrando: Algoritmo de deleção retorne arv; senão // Encontrei elemento que quero deletar. (CONTINUA) tNodo* FUNÇÃO delete(info: tInfo, arv: *tNodo) tmp, filho: *tNodo; início se (arv = NULO) então retorne arv senão se (info < arv->info) // Vá à esquerda. arv->filhoÀEsquerda <- delete(info, arv->filhoÀEsquerda); retorne arv; senão se (info > arv->info) // Vá à direita. arv->filhoÀDireita <- delete(info, arv->filhoÀDireita); arv <- atualiza-zigue-zague(arv); Relembrando: Algoritmo de deleção (cont) (CONTINUAÇÃO) se (arv->filhoÀDireita ~= NULO E arv->filhoÀEsquerda ~= NULO) // 2 filhos. tmp <- mínimo(arv->filhoÀDireita); arv->info <- tmp->info; arv->filhoÀDireita <- delete(arv->info, arv->filhoÀDireita); arv <- atualiza-zigue-zague(arv); retorne arv; senão // 1 filho. tmp <- arv; se (arv->filhoÀDireita ~= NULO) então // Filho à direita. filho <- arv->filhoÀDireita; retorne filho; senão se (arv->filhoÀEsquerda ~= NULO) então // Filho à esquerda. filho <- arv->filhoÀEsquerda; retorne filho; senão // Folha. libere arv; retorne NULO; fim se fim se fim se fim se fim se fim se fim DABB não ajusta alturas! Lembre de sempre atualizar alturas antes de calcular o “zigue-zague” Atribuição-Uso Não-Comercial-Compartilhamento pela Licença 2.5 Brasil Você pode: - copiar, distribuir, exibir e executar a obra - criar obras derivadas Sob as seguintes condições: Atribuição — Você deve dar crédito ao autor original, da forma especificada pelo autor ou licenciante. Uso Não-Comercial — Você não pode utilizar esta obra com finalidades comerciais. Compartilhamento pela mesma Licença — Se você alterar, transformar, ou criar outra obra com base nesta, você somente poderá distribuir a obra resultante sob uma licença idêntica a esta. Para ver uma cópia desta licença, visite http://creativecommons.org/licenses/by-nc-sa/2.5/br/ ou mande uma carta para Creative Commons, 171 Second Street, Suite 300, San Francisco, California, 94105, USA.