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

Passo 1

Beleza, vamos lá! O exercício pede para mostrar uma árvore AVL T que tem um nó v cuja remoção deixa a árvore T' 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 T:
        30
       /  \
     20    40
    / \      \
  10 25     50
            /
          45

Passo 3

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

Passo 4

Agora, precisamos verificar se a árvore resultante T' está balanceada. Ao remover o 50, o nó 40 agora tem somente um filho à direita ( 45), o que pode causar um desequilíbrio. Vamos calcular as alturas:
  • 30: altura máxima da subárvore esquerda (subárvore com raiz 20) é 2, e da direita (subárvore com raiz 40) é 2.
  • 40: altura da subárvore direita ( 45) é 1, e da esquerda é 0.
A diferença de alturas no nó 40 é 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ó 25 ao invés de 50, a árvore resultante seria:
        30
       /  \
     20    40
    /        \
  10         50
            /
          45
Agora, vamos verificar o balanceamento:
  • 30: subárvore esquerda tem altura 2, subárvore direita tem altura 3. Diferença de 1, ainda ok.
  • 40: subárvore direita ( 50) 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ó 40, 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 50 e depois esquerda em 40). 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 T 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ó 30. A árvore resultante T' fica assim:
        40
       /  \
     20    60
    /      / \
  10     50 70
           \
           35

Passo 9

Agora, vamos verificar o balanceamento:
  • 40: subárvore esquerda tem altura 2 (nó 20), subárvore direita tem altura 3 (nó 60). Diferença de 1, ok.
  • 60: subárvore esquerda (nó 50) tem altura 2, subárvore direita (nó 70) tem altura 1. Diferença de 1, ok.
  • 50: subárvore direita (nó 35) tem altura 1, esquerda é 0. Diferença de 1, ok.
Parece balanceada, mas na verdade, o nó 20 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ó 40, temos:
          50
         /  \
       30    70
      /     / \
    20    60 80
          \
          45

Passo 11

Agora, verificamos o balanceamento:
  • 50: subárvore esquerda tem altura 2, subárvore direita tem altura 3. Diferença de 1, ok.
  • 30: subárvore esquerda (nó 20) tem altura 1, subárvore direita é 0. Diferença de 1, ok.
  • 70: subárvore esquerda (nó 60) tem altura 2, subárvore direita (nó 80) tem altura 1. Diferença de 1, ok.
  • 60: subárvore direita (nó 45) tem altura 1, esquerda é 0. Diferença de 1, ok.
Apesar disso, a remoção de 40 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 T onde, ao remover o nó 40, a árvore resultante T' 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