Implemente uma rotação dupla à esquerda sem utilizar uma rotação direita e depois uma esquerda.
Passo 1
Beleza, vamos lá! O exercício pede pra gente implementar uma rotação dupla à esquerda em uma árvore binária, mas sem usar primeiro uma rotação à direita e depois uma à esquerda. Isso está relacionado ao conteúdo de estruturas de dados, mais especificamente árvores balanceadas como as árvores AVL. Para resolver isso, vamos precisar entender como funcionam as rotações em árvores binárias e como combiná-las para fazer uma rotação dupla à esquerda de forma direta.
Passo 2
Primeiro, vamos relembrar o que é uma rotação simples à esquerda. Imagine que temos um nó chamado X com um filho direito chamado Y. Uma rotação à esquerda vai fazer com que Y suba para a posição de X, e X passe a ser o filho esquerdo de Y. Assim, balanceamos a árvore quando ela está desbalanceada à direita.
Passo 3
Agora, para uma rotação dupla à esquerda, geralmente fazemos duas rotações: primeiro uma à direita no filho esquerdo e depois uma à esquerda no nó principal. Mas o exercício quer que a gente faça isso sem usar uma rotação à direita primeiro. Então, vamos pensar em como combinar esses passos em uma única operação.
Passo 4
Vamos considerar que na rotação dupla à esquerda, temos três nós envolvidos: X, Y, e Z, onde Y é filho direito de X e Z é filho esquerdo de Y. Na rotação dupla, queremos que Z suba para a posição de X, com Y se tornando o filho direito de Z e X o filho esquerdo de Z.
Passo 5
Para implementar isso sem usar uma rotação à direita e depois à esquerda, vamos ajustar diretamente os ponteiros dos nós envolvidos. Vamos:
- Fazer Z subir para a posição de X.
- Ajustar Y para ser o filho direito de Z.
- Ajustar X para ser o filho esquerdo de Z.
- Se Z tinha filhos, ajustá-los corretamente para manter a árvore ordenada.
Passo 6
Vamos escrever o código para essa rotação dupla à esquerda. Vou usar uma estrutura básica de nó de árvore em Python para ilustrar:
class No:
def __init__(self, chave):
self.chave = chave
self.esquerda = None
self.direita = None
def rotacao_dupla_esquerda(x):
y = x.direita
z = y.esquerda
# Rotaciona Z para cima
z.esquerda = x
z.direita = y
# Ajusta os filhos de X e Y
x.direita = z.esquerda
y.esquerda = z.direita
return z
Passo 7
Vamos explicar o que está acontecendo no código:
- x é o nó onde a rotação dupla vai ocorrer.
- y é o filho direito de x, e z é o filho esquerdo de y.
- A função ajusta os ponteiros para que z se torne o novo nó no lugar de x, com x como filho esquerdo e y como filho direito.
- Isso balanceia a árvore sem precisar fazer uma rotação à direita primeiro.
Resposta
Pronto! Implementamos uma rotação dupla à esquerda sem utilizar uma rotação direita seguida de uma à esquerda. O código acima realiza essa operação ajustando diretamente os ponteiros dos nós envolvidos para manter a árvore balanceada.
Exercícios relacionados
Desenhe a árvore AVL formada pela inserção dos números de 1 a 12 em ordem crescente.
Prove ou dê um contraexemplo para as afirmações abaixo:
© Toda árvore estritamente binária é AVL.
© Toda árvore estritamente binária é AVL.
Desenhe passo a passo a ávore AVL resultante da inserção dos elementos 5, 7, 11,
e 3, nesta ordem, indicando as rotações que foram executadas.
Prove que uma rotação dupla à direita pode ser obtida com uma rotação esquerda seguida de uma rotação direita.