Implemente uma rotação dupla à direita sem utilizar uma rotação esquerda e depois uma direita.

Passo 1

Beleza, vamos entender o que a pergunta está pedindo. O exercício quer que a gente implemente uma rotação dupla à direita em uma árvore binária de busca ou AVL, mas de uma forma diferente: sem usar uma rotação esquerda seguida de uma rotação direita. Para resolver isso, vamos precisar saber como funcionam as rotações em árvores e especificamente como fazer uma rotação dupla à direita diretamente.

Passo 2

Primeiro, vamos lembrar o que é uma rotação em árvores binárias. Rotações são operações que reestruturam a árvore para manter ou melhorar seu balanceamento, o que é essencial para garantir que as operações de busca, inserção e remoção sejam eficientes.

Passo 3

Existem dois tipos básicos de rotações: rotação à esquerda e rotação à direita. Uma rotação à direita, por exemplo, faz com que o filho esquerdo de um nó se torne o novo nó pai, enquanto o nó original passa a ser o filho direito desse novo nó.

Passo 4

Uma rotação dupla à direita é usada quando a subárvore direita de um nó está desequilibrada para a esquerda. Normalmente, ela é realizada com uma rotação à esquerda seguida de uma rotação à direita. Mas como o exercício pede para não usar essas duas rotações separadas, precisamos encontrar uma maneira de fazer a rotação dupla diretamente.

Passo 5

Para implementar a rotação dupla à direita sem usar uma rotação esquerda seguida de uma direita, podemos combinar os passos dessas duas rotações em uma única operação. Isso envolve reorganizar os ponteiros dos nós de forma que a subárvore seja rebalanceada adequadamente.

Passo 6

Vamos implementar uma função que realiza a rotação dupla à direita diretamente. Vamos supor que estamos trabalhando com uma estrutura de árvore onde cada nó tem referências para seu filho esquerdo e direito.

Passo 7

Aqui está a implementação em Python:
class No:
    def __init__(self, chave):
        self.chave = chave
        self.esquerda = None
        self.direita = None

def rotacao_dupla_direita(no):
    if no is None:
        return None
    
    # Primeiro nível de rotação: faz o filho direito tornar-se o novo no
    novo_no = no.direita
    if novo_no is None:
        return no

    # Reorganiza os ponteiros
    no.direita = novo_no.esquerda
    novo_no.esquerda = no

    # Segundo nível de rotação: faz o novo_no tornar-se a raiz da subárvore
    # Aqui, você pode adicionar lógica adicional caso necessário

    return novo_no

Resposta

A função rotacao_dupla_direita implementa uma rotação dupla à direita diretamente, reorganizando os ponteiros dos nós para balancear a árvore sem usar rotações à esquerda e à direita separadamente.

Exercícios relacionados

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.
Qual o número mínimo e máximo de nós em uma árvore AVL de altura ? Justifique sua resposta.
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.
Suponha que, agora, todo nó da árvore AVL tem um novo campo chamado parent que nada mais é que um ponteiro para nó pai. Como a raiz não tem pai, seu campo parent aponta para nulo).
Implemente todas as funções da árvore AVL vistas em sala iterativamente (sem usar recursão) e atualize os campos parent de cada nó adequadamente.