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.

Passo 1

Beleza, vamos entender o que a questão tá pedindo. A gente tem uma árvore AVL, que é um tipo de árvore binária de busca balanceada. Cada nó dessa árvore agora tem um campo extra chamado parent, que aponta para o nó pai. A raiz não tem pai, então esse campo aponta para nulo.
O que a gente precisa fazer é implementar todas as funções da árvore AVL que vimos em sala, mas de forma iterativa (ou seja, sem usar recursão). Além disso, precisamos garantir que o campo parent de cada nó seja atualizado corretamente durante essas operações.

Passo 2

Primeiro, vamos lembrar o que são as funções básicas de uma árvore AVL:
  1. Inserção: Adicionar um novo nó na árvore.
  2. Remoção: Tirar um nó da árvore.
  3. Rotação: Ajustar a árvore para mantê-la balanceada após inserções ou remoções.
Como vamos fazer tudo de forma iterativa, precisamos usar estruturas de repetição (como loops) em vez de chamadas recursivas.

Passo 3

Implementando a Inserção Iterativa com Atualização do Campo Parent
Vamos começar com a inserção. O processo é:
  1. Buscar a posição correta para inserir o novo nó.
  2. Inserir o nó.
  3. Atualizar os campos parent.
  4. Rebalancear a árvore se necessário.
Como tudo isso será feito de forma iterativa, vamos usar um loop para encontrar a posição correta.
class NoAVL:
    def __init__(self, chave):
        self.chave = chave
        self.esquerda = None
        self.direita = None
        self.parent = None
        self.altura = 1

def inserir_iterativo(root, chave):
    novo_no = NoAVL(chave)
    if root is None:
        return novo_no

    atual = root
    parent = None

    while atual:
        parent = atual
        if chave < atual.chave:
            atual = atual.esquerda
        else:
            atual = atual.direita

    novo_no.parent = parent
    if chave < parent.chave:
        parent.esquerda = novo_no
    else:
        parent.direita = novo_no

    # Aqui você adicionaria a lógica de rebalanceamento
    return root

Passo 4

Explicando o Código de Inserção
No código acima:
  • Classe NoAVL: Define cada nó da árvore com chave, esquerda, direita, parent e altura.
  • Função inserir_iterativo:
    • Cria um novo nó.
    • Se a árvore está vazia (root é None), retorna o novo nó como raiz.
    • Usa um loop while para encontrar a posição correta para inserir o novo nó.
    • Atualiza o campo parent do novo nó para apontar para o nó pai encontrado.
    • Insere o novo nó como filho esquerdo ou direito, dependendo da chave.
    • Depois da inserção, você deve adicionar a lógica para rebalancear a árvore, garantindo que ela continue AVL.

Passo 5

Implementando a Remoção Iterativa com Atualização do Campo Parent
A remoção é um pouco mais complexa, pois precisamos considerar três casos:
  1. Nó sem filhos: Simplesmente remove.
  2. Nó com um filho: Substitui o nó pelo filho.
  3. Nó com dois filhos: Encontra o sucessor ou predecessor in-order, troca de posição e remove.
Vamos implementar de forma iterativa:
def remover_iterativo(root, chave):
    atual = root
    parent = None

    # Encontrar o nó a ser removido
    while atual and atual.chave != chave:
        parent = atual
        if chave < atual.chave:
            atual = atual.esquerda
        else:
            atual = atual.direita

    if atual is None:
        return root  # Chave não encontrada

    # Caso 1: Nó sem filhos
    if atual.esquerda is None and atual.direita is None:
        if atual != root:
            if parent.esquerda == atual:
                parent.esquerda = None
            else:
                parent.direita = None
        else:
            root = None

    # Caso 2: Nó com um filho
    elif atual.esquerda is None or atual.direita is None:
        filho = atual.esquerda if atual.esquerda else atual.direita
        if atual != root:
            if atual == parent.esquerda:
                parent.esquerda = filho
            else:
                parent.direita = filho
            filho.parent = parent
        else:
            root = filho
            root.parent = None

    # Caso 3: Nó com dois filhos
    else:
        # Encontrar o sucessor (menor nó na subárvore direita)
        sucessor = atual.direita
        while sucessor.esquerda:
            sucessor = sucessor.esquerda

        # Copiar a chave do sucessor para o nó atual
        atual.chave = sucessor.chave

        # Remover o sucessor
        if sucessor.parent.esquerda == sucessor:
            sucessor.parent.esquerda = sucessor.direita
            if sucessor.direita:
                sucessor.direita.parent = sucessor.parent
        else:
            sucessor.parent.direita = sucessor.direita
            if sucessor.direita:
                sucessor.direita.parent = sucessor.parent

    # Aqui você adicionaria a lógica de rebalanceamento
    return root

Passo 6

Explicando o Código de Remoção
No código de remoção:
  • Buscar o nó: Usamos um loop para encontrar o nó que contém a chave que queremos remover.
  • Três casos:
    1. Sem filhos: Se o nó é uma folha, simplesmente o removemos.
    2. Com um filho: Substituímos o nó pelo seu único filho e atualizamos o campo parent.
    3. Com dois filhos: Encontramos o sucessor in-order (o menor nó na subárvore direita), copiamos a chave dele para o nó atual e então removemos o sucessor, que será um nó com no máximo um filho.
  • Atualização do Campo Parent: Sempre que movemos um nó ou removemos, atualizamos o campo parent para manter a referência correta.
  • Rebalanceamento: Após a remoção, devemos rebalancear a árvore para mantê-la AVL.

Passo 7

Implementando Rotação à Esquerda e à Direita Iterativas com Atualização do Campo Parent
As rotações são usadas para manter a árvore balanceada. Vamos implementar as rotações e garantir que os campos parent sejam atualizados corretamente.
def rotacao_direita(y):
    x = y.esquerda
    T2 = x.direita

    # Rotação
    x.direita = y
    y.esquerda = T2

    # Atualizar pais
    x.parent = y.parent
    y.parent = x
    if T2:
        T2.parent = y

    # Retornar nova raiz
    return x

def rotacao_esquerda(x):
    y = x.direita
    T2 = y.esquerda

    # Rotação
    y.esquerda = x
    x.direita = T2

    # Atualizar pais
    y.parent = x.parent
    x.parent = y
    if T2:
        T2.parent = x

    # Retornar nova raiz
    return y

Passo 8

Explicando o Código de Rotação
Nas funções de rotação:
  • Rotação à Direita (rotacao_direita):
    • y é o nó atual que será rotacionado.
    • x é o filho esquerdo de y.
    • Fazemos x virar a nova raiz da subárvore, com y como seu filho direito.
    • Atualizamos os campos parent de x, y e de qualquer nó que foi movido (T2).
  • Rotação à Esquerda (rotacao_esquerda):
    • Similar à rotação à direita, mas na direção oposta.
    • x é o nó atual que será rotacionado.
    • y é o filho direito de x.
    • Fazemos y virar a nova raiz da subárvore, com x como seu filho esquerdo.
    • Atualizamos os campos parent de x, y e de qualquer nó que foi movido (T2).
Essas rotações ajudam a manter o balanceamento da árvore AVL após inserções ou remoções.

Passo 9

Atualizando o Balanceamento Iterativamente
Após cada inserção ou remoção, precisamos verificar se a árvore está balanceada e, se não estiver, aplicar as rotações necessárias.
Vamos adicionar uma fun��ão para atualizar as alturas e balancear a árvore de forma iterativa:
def atualizar_altura_no(no):
    no.altura = 1 + max(altura(no.esquerda), altura(no.direita))

def altura(no):
    if not no:
        return 0
    return no.altura

def fator_balanceamento(no):
    if not no:
        return 0
    return altura(no.esquerda) - altura(no.direita)

def rebalancear_iterativo(no):
    while no:
        atualizar_altura_no(no)
        balance = fator_balanceamento(no)

        # Caso Esquerda Esquerda
        if balance > 1 and fator_balanceamento(no.esquerda) >= 0:
            if no.parent is None:
                no = rotacao_direita(no)
            else:
                if no.parent.esquerda == no:
                    no.parent.esquerda = rotacao_direita(no)
                else:
                    no.parent.direita = rotacao_direita(no)

        # Caso Esquerda Direita
        elif balance > 1 and fator_balanceamento(no.esquerda) < 0:
            no.esquerda = rotacao_esquerda(no.esquerda)
            if no.esquerda:
                no.esquerda.parent = no
            if no.parent is None:
                no = rotacao_direita(no)
            else:
                if no.parent.esquerda == no:
                    no.parent.esquerda = rotacao_direita(no)
                else:
                    no.parent.direita = rotacao_direita(no)

        # Caso Direita Direita
        elif balance < -1 and fator_balanceamento(no.direita) <= 0:
            if no.parent is None:
                no = rotacao_esquerda(no)
            else:
                if no.parent.esquerda == no:
                    no.parent.esquerda = rotacao_esquerda(no)
                else:
                    no.parent.direita = rotacao_esquerda(no)

        # Caso Direita Esquerda
        elif balance < -1 and fator_balanceamento(no.direita) > 0:
            no.direita = rotacao_direita(no.direita)
            if no.direita:
                no.direita.parent = no
            if no.parent is None:
                no = rotacao_esquerda(no)
            else:
                if no.parent.esquerda == no:
                    no.parent.esquerda = rotacao_esquerda(no)
                else:
                    no.parent.direita = rotacao_esquerda(no)

        no = no.parent

Passo 10

Explicando o Código de Rebalanceamento
Na função rebalancear_iterativo:
  • Atualizar Altura: A cada nó, atualizamos sua altura com base nas alturas dos filhos.
  • Fator de Balanceamento: Calculamos a diferença entre as alturas dos subarvores esquerda e direita.
  • Quatro Casos de Rotação:
    1. Esquerda Esquerda: Fazemos uma rotação à direita.
    2. Esquerda Direita: Primeiro rotacionamos à esquerda o filho esquerdo, depois à direita o nó atual.
    3. Direita Direita: Fazemos uma rotação à esquerda.
    4. Direita Esquerda: Primeiro rotacionamos à direita o filho direito, depois à esquerda o nó atual.
  • Atualização dos Campos Parent: Após cada rotação, garantimos que os campos parent estejam corretos.
  • Iteração: Movemos para o nó pai e repetimos o processo até chegar na raiz.
Esse processo garante que a árvore permaneça balanceada após inserções e remoções.

Resposta

Seguindo esses passos, conseguimos implementar todas as funções básicas da árvore AVL de forma iterativa, garantindo que os campos parent de cada nó sejam atualizados corretamente durante inserções, remoções e rotações para manter o balanceamento da árvore.

Exercícios relacionados

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.
Implemente uma rotação dupla à direita sem utilizar uma rotação esquerda e depois uma direita.
Projete um contador assíncrono de módulo 13 crescente (contagem de 0 a 12).
Projete um contador Johnson de 5 bits disparado na borda de subida de um sinal de clock. O que você deve mudar para que esse circuito vire um contador em anel? Descreva o comportamento de ambos os circuitos.