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:
  1. Fazer Z subir para a posição de X.
  2. Ajustar Y para ser o filho direito de Z.
  3. Ajustar X para ser o filho esquerdo de Z.
  4. 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.
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.