Dê exemplo de uma família de árvores AVL cuja exclusão de nós implica a realização de operações de rotação para o rebalanceamento.

Passo 1

Beleza, vamos lá! O exercício pede para a gente dar um exemplo de uma família de árvores AVL onde, ao excluir nós, a gente precise fazer cerca de rotações para rebalancear a árvore. Então, vamos falar de árvores AVL, que são árvores binárias de busca balanceadas, e entender como as rotações funcionam quando a gente remove um nó.

Passo 2

Primeiro, vamos lembrar o que é uma árvore AVL. É uma árvore binária de busca que mantém o equilíbrio ao garantir que, para cada nó, a diferença de altura entre sua subárvore esquerda e direita seja no máximo 1. Isso é importante para manter as operações de busca, inserção e deleção eficientes, em tempo .
Quando a gente remove um nó de uma árvore AVL, pode acontecer de a árvore ficar desequilibrada. Para resolver isso, a gente realiza rotações, que são reestruturas locais na árvore para restaurar o equilíbrio. Existem rotações simples (simples à direita ou à esquerda) e rotações duplas (primeiro uma rotação à esquerda, depois à direita, ou vice-versa).
Normalmente, uma deleção pode requerer várias rotações ao longo do caminho da raiz até a folha onde ocorreu a remoção. No pior caso, esse caminho tem altura , então poderíamos ter até rotações.

Passo 3

Agora, para criar uma família de árvores AVL que exija rotações ao excluir nós, precisamos construir árvores onde cada remoção cause um desequilíbrio que precise ser corrigido com rotações em cada nível do caminho da deleção até a raiz.
Um exemplo disso é uma árvore AVL que seja uma “espinha” à esquerda ou à direita, onde cada nível tem um filho apenas em um dos lados. Por exemplo, uma árvore que se parece com uma lista ligada, mas balanceada como uma árvore AVL.

Passo 4

Vamos construir uma árvore AVL onde cada nível tem um filho apenas à esquerda. Assim, a árvore tem a forma de uma espinha à esquerda. Quando a gente remove o nó mais profundo, a remoção faz com que cada ancestral precise ser reavaliado para manter o equilíbrio, resultando em uma rotação em cada nível.
Por exemplo, considere uma árvore AVL com altura . Ao remover o nó na profundidade , precisamos realizar uma rotação em cada nível desde a profundidade até a raiz para manter o balanceamento. Isso resulta em rotações, já que em uma árvore AVL, é proporcional a .

Resposta

Portanto, uma família de árvores AVL que são essencialmente “espinhas” balanceadas à esquerda ou à direita, com altura , exige rotações ao excluir nós, já que cada nível do caminho da deleção até a raiz precisa de uma rotação para manter o equilíbrio da árvore.

Exercícios relacionados

Descreva a estrutura de uma árvore AVL formada pela inserção dos números de 1 a n em ordem crescente. Qual é a altura dessa árvore?
Prove que uma rotação dupla à direita pode ser obtida com uma rotação esquerda seguida de uma rotação direita.
Implemente uma versão da AVL em que a condição de balanceamento seja:
Qual o número mínimo e máximo de nós em uma árvore AVL de altura ? Justifique sua resposta.