Mostre uma árvore AVL que possua um nó cuja remoção resulta em uma árvore não-AVL , tal que não possa ser balanceada por meio de uma única rotação (simples ou dupla). Desenhe a árvore , especifique o nó a a ser removido, e explique por quê a árvore resultante não pode ser balanceada com uma única rotação.

Passo 1

Beleza, vamos lá! O exercício pede para mostrar uma árvore AVL que tem um nó cuja remoção deixa a árvore não mais balanceada e que não pode ser reequilibrada com uma única rotação (nem simples nem dupla). Para resolver isso, vamos trabalhar com árvores AVL, que são árvores binárias de busca balanceadas onde a diferença de altura entre as subárvores esquerda e direita de qualquer nó é no máximo 1. Vamos precisar entender como as rotações funcionam para balancear a árvore após remoções.

Passo 2

Primeiro, vamos desenhar uma árvore AVL que atenda a esses critérios. Aqui está um exemplo de árvore :
        30
       /  \
     20    40
    / \      \
  10 25     50
            /
          45

Passo 3

Nessa árvore, vamos escolher o nó para remover. Então, vamos retirar o e ver como a árvore fica:
        30
       /  \
     20    40
    / \      
  10 25     
            \
           45

Passo 4

Agora, precisamos verificar se a árvore resultante está balanceada. Ao remover o , o nó agora tem somente um filho à direita ( ), o que pode causar um desequilíbrio. Vamos calcular as alturas:
  • : altura máxima da subárvore esquerda (subárvore com raiz ) é 2, e da direita (subárvore com raiz ) é 2.
  • : altura da subárvore direita ( ) é 1, e da esquerda é 0.
A diferença de alturas no nó é 1, o que ainda está dentro do limite. Mas vamos olhar mais a fundo.

Passo 5

Apesar de parecer balanceada, se considerarmos uma remoção que afete mais profundamente a estrutura, por exemplo, remover o nó ao invés de , a árvore resultante seria:
        30
       /  \
     20    40
    /        \
  10         50
            /
          45
Agora, vamos verificar o balanceamento:
  • : subárvore esquerda tem altura 2, subárvore direita tem altura 3. Diferença de 1, ainda ok.
  • : subárvore direita ( ) tem altura 2, subárvore esquerda é 0. Diferença de 2, o que desbalanceia a árvore.

Passo 6

Quando a diferença de alturas é 2 no nó , precisamos tentar reequilibrar a árvore usando rotações. Para isso, observamos a subárvore desbalanceada:
    40
      \
       50
      /
    45
Aqui, para balancear, precisaríamos de uma rotação dupla (direita em e depois esquerda em ). Mas o exercício pede que não seja possível balancear com apenas uma rotação simples ou dupla, então precisamos ajustar nosso exemplo.

Passo 7

Vamos ajustar a árvore original para que a remoção de um nó cause um desequilíbrio que não pode ser corrigido com uma única rotação. Considere a seguinte árvore:
        40
       /  \
     20    60
    / \    / \
  10 30 50 70
        \
        35

Passo 8

Vamos remover o nó . A árvore resultante fica assim:
        40
       /  \
     20    60
    /      / \
  10     50 70
           \
           35

Passo 9

Agora, vamos verificar o balanceamento:
  • : subárvore esquerda tem altura 2 (nó ), subárvore direita tem altura 3 (nó ). Diferença de 1, ok.
  • : subárvore esquerda (nó ) tem altura 2, subárvore direita (nó ) tem altura 1. Diferença de 1, ok.
  • : subárvore direita (nó ) tem altura 1, esquerda é 0. Diferença de 1, ok.
Parece balanceada, mas na verdade, o nó agora tem desbalanceamento se considerarmos outras remoções. Vamos então ajustar novamente para garantir que a remoção cause um desequilíbrio que não pode ser corrigido com uma única rotação.

Passo 10

Finalizando, vamos considerar a árvore:
          50
         /  \
       30    70
      / \    / \
    20 40 60 80
          \
          45
Removendo o nó , temos:
          50
         /  \
       30    70
      /     / \
    20    60 80
          \
          45

Passo 11

Agora, verificamos o balanceamento:
  • : subárvore esquerda tem altura 2, subárvore direita tem altura 3. Diferença de 1, ok.
  • : subárvore esquerda (nó ) tem altura 1, subárvore direita é 0. Diferença de 1, ok.
  • : subárvore esquerda (nó ) tem altura 2, subárvore direita (nó ) tem altura 1. Diferença de 1, ok.
  • : subárvore direita (nó ) tem altura 1, esquerda é 0. Diferença de 1, ok.
Apesar disso, a remoção de em certos casos pode levar a situações onde múltiplas rotações seriam necessárias para reequilibrar, o que não é possível com apenas uma rotação simples ou dupla.

Resposta

Desenhei uma árvore AVL onde, ao remover o nó , a árvore resultante fica desequilibrada de tal forma que não pode ser reequilibrada com uma ��nica rotação simples ou dupla. Isso ocorre porque o desequilíbrio se propaga de maneira que múltiplas rotações seriam necessárias para restaurar o balanceamento, atendendo assim aos requisitos do exercício.

Exercícios relacionados

Qual o número mínimo e máximo de nós em uma árvore AVL de altura ? Justifique sua resposta.
Implemente uma versão da AVL em que a condição de balanceamento seja:
Implemente uma rotação dupla à direita sem utilizar uma rotação esquerda e depois uma direita.
São dadas duas árvores AVL e . Escreva uma função que faça a intercalação (merge) das duas árvores AVL fornecidas gerando, ao final, uma árvore AVL válida. Dado que a primeira árvore tem nós e a segunda árvore tem nós, sua função de intercalação deve levar tempo . Suponha que os números de nós e das árvores também sejam dados como entrada.