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:
- Nó
: altura máxima da subárvore esquerda (subárvore com raiz ) é 2, e da direita (subárvore com raiz ) é 2. - Nó
: 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:
- Nó
: subárvore esquerda tem altura 2, subárvore direita tem altura 3. Diferença de 1, ainda ok. - Nó
: 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:
- Nó
: subárvore esquerda tem altura 2 (nó ), subárvore direita tem altura 3 (nó ). Diferença de 1, ok. - Nó
: subárvore esquerda (nó ) tem altura 2, subárvore direita (nó ) tem altura 1. Diferença de 1, ok. - Nó
: 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:
- Nó
: subárvore esquerda tem altura 2, subárvore direita tem altura 3. Diferença de 1, ok. - Nó
: subárvore esquerda (nó ) tem altura 1, subárvore direita é 0. Diferença de 1, ok. - Nó
: subárvore esquerda (nó ) tem altura 2, subárvore direita (nó ) tem altura 1. Diferença de 1, ok. - Nó
: 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.