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.
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:
- Inserção: Adicionar um novo nó na árvore.
- Remoção: Tirar um nó da árvore.
- 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 é:
- Buscar a posição correta para inserir o novo nó.
- Inserir o nó.
- Atualizar os campos
parent
. - 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 comchave
,esquerda
,direita
,parent
ealtura
. - 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:
- Nó sem filhos: Simplesmente remove.
- Nó com um filho: Substitui o nó pelo filho.
- 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:
- Sem filhos: Se o nó é uma folha, simplesmente o removemos.
- Com um filho: Substituímos o nó pelo seu único filho e atualizamos o campo
parent
. - 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 dey
.- Fazemos
x
virar a nova raiz da subárvore, comy
como seu filho direito. - Atualizamos os campos
parent
dex
,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 dex
.- Fazemos
y
virar a nova raiz da subárvore, comx
como seu filho esquerdo. - Atualizamos os campos
parent
dex
,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:
- Esquerda Esquerda: Fazemos uma rotação à direita.
- Esquerda Direita: Primeiro rotacionamos à esquerda o filho esquerdo, depois à direita o nó atual.
- Direita Direita: Fazemos uma rotação à esquerda.
- 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.