Estrutura de Dados — Aula 04

# Importações da biblioteca padrão
from collections import deque   # usada no percurso por nível (fila)
import math                     # usada apenas nas demonstrações de complexidade

print("Ambiente pronto.")

def adicionar_metodo(classe):
    '''Decorador didático: anexa a função decorada à classe informada como um método.

    Uso:
        @adicionar_metodo(ArvoreAVL)
        def meu_metodo(self, ...):
            ...
    '''
    def decorador(funcao):
        setattr(classe, funcao.__name__, funcao)
        return funcao
    return decorador


print("Decorador 'adicionar_metodo' definido.")

class NoAVL:
    '''Representa um vértice (nó) de uma árvore AVL.'''

    def __init__(self, chave):
        self.chave = chave        # valor armazenado no nó
        self.esquerda = None      # subárvore esquerda (chaves menores)
        self.direita = None       # subárvore direita (chaves maiores)
        self.altura = 0           # folha recém-criada tem altura 0 (contagem por arestas)

    def eh_folha(self):
        '''Retorna True se o nó não possui filhos.'''
        return self.esquerda is None and self.direita is None

    def quantidade_de_filhos(self):
        '''Retorna quantos filhos (0, 1 ou 2) o nó possui.'''
        return (1 if self.esquerda is not None else 0) + (1 if self.direita is not None else 0)

    def __repr__(self):
        return f"NoAVL(chave={self.chave}, altura={self.altura})"

no_de_teste = NoAVL(10)
no_de_teste.esquerda = NoAVL(5)

print(no_de_teste)
print("É folha?", no_de_teste.eh_folha())
print("Quantidade de filhos:", no_de_teste.quantidade_de_filhos())
print("Filho da esquerda:", no_de_teste.esquerda)

class ArvoreAVL:
    '''Árvore binária de busca balanceada (AVL).

    Invariante mantida: para todo nó u, |h_d(u) - h_e(u)| <= 1.
    '''

    def __init__(self):
        self.raiz = None              # raiz da árvore (None = árvore vazia)
        self.quantidade_de_nos = 0    # total de chaves armazenadas

    def esta_vazia(self):
        '''Retorna True se a árvore não possui nenhum nó.'''
        return self.raiz is None

    def __len__(self):
        return self.quantidade_de_nos

@adicionar_metodo(ArvoreAVL)
def altura(self, no):
    '''Altura da subárvore enraizada em 'no'. Subárvore vazia tem altura -1.'''
    if no is None:
        return -1
    return no.altura

@adicionar_metodo(ArvoreAVL)
def atualizar_altura(self, no):
    '''Recalcula a altura do nó: 1 + a maior altura entre os filhos.'''
    altura_esquerda = self.altura(no.esquerda)
    altura_direita = self.altura(no.direita)
    no.altura = 1 + max(altura_esquerda, altura_direita)

@adicionar_metodo(ArvoreAVL)
def fator_balanceamento(self, no):
    '''Fator de balanceamento: altura da subárvore direita menos a da esquerda.'''
    if no is None:
        return 0
    return self.altura(no.direita) - self.altura(no.esquerda)

@adicionar_metodo(ArvoreAVL)
def rotacao_esquerda(self, no_desbalanceado):
    '''Rotação simples à ESQUERDA — corrige o caso RR.

    Recebe o nó desbalanceado (v1) e devolve a nova raiz da subárvore (v2).
    '''
    novo_topo = no_desbalanceado.direita          # v2 sobe e vira a raiz da subárvore
    subarvore_transferida = novo_topo.esquerda    # s2 muda de pai

    # Reorganiza os ponteiros
    novo_topo.esquerda = no_desbalanceado
    no_desbalanceado.direita = subarvore_transferida

    # As alturas mudaram: atualiza de baixo para cima
    self.atualizar_altura(no_desbalanceado)
    self.atualizar_altura(novo_topo)

    return novo_topo

@adicionar_metodo(ArvoreAVL)
def rotacao_direita(self, no_desbalanceado):
    '''Rotação simples à DIREITA — corrige o caso LL.

    Recebe o nó desbalanceado (v3) e devolve a nova raiz da subárvore (v2).
    '''
    novo_topo = no_desbalanceado.esquerda         # v2 sobe e vira a raiz da subárvore
    subarvore_transferida = novo_topo.direita     # s3 muda de pai

    # Reorganiza os ponteiros
    novo_topo.direita = no_desbalanceado
    no_desbalanceado.esquerda = subarvore_transferida

    # As alturas mudaram: atualiza de baixo para cima
    self.atualizar_altura(no_desbalanceado)
    self.atualizar_altura(novo_topo)

    return novo_topo

@adicionar_metodo(ArvoreAVL)
def rotacao_dupla_esquerda_direita(self, no_desbalanceado):
    '''Rotação DUPLA à esquerda e à direita — corrige o caso LR.

    Passo 1: rotação à esquerda no filho esquerdo (transforma LR em LL).
    Passo 2: rotação à direita no próprio nó desbalanceado.
    '''
    no_desbalanceado.esquerda = self.rotacao_esquerda(no_desbalanceado.esquerda)
    return self.rotacao_direita(no_desbalanceado)

@adicionar_metodo(ArvoreAVL)
def rotacao_dupla_direita_esquerda(self, no_desbalanceado):
    '''Rotação DUPLA à direita e à esquerda — corrige o caso RL.

    Passo 1: rotação à direita no filho direito (transforma RL em RR).
    Passo 2: rotação à esquerda no próprio nó desbalanceado.
    '''
    no_desbalanceado.direita = self.rotacao_direita(no_desbalanceado.direita)
    return self.rotacao_esquerda(no_desbalanceado)

@adicionar_metodo(ArvoreAVL)
def rebalancear(self, no):
    '''Atualiza a altura do nó e aplica a rotação necessária, se houver desbalanceio.

    Devolve a (possivelmente nova) raiz da subárvore.
    '''
    self.atualizar_altura(no)
    fator = self.fator_balanceamento(no)

    # Pesado à DIREITA
    if fator > 1:
        if self.fator_balanceamento(no.direita) >= 0:
            return self.rotacao_esquerda(no)                     # caso RR
        else:
            return self.rotacao_dupla_direita_esquerda(no)       # caso RL

    # Pesado à ESQUERDA
    if fator < -1:
        if self.fator_balanceamento(no.esquerda) <= 0:
            return self.rotacao_direita(no)                      # caso LL
        else:
            return self.rotacao_dupla_esquerda_direita(no)       # caso LR

    # Já está balanceado (fb em {-1, 0, +1})
    return no

@adicionar_metodo(ArvoreAVL)
def inserir(self, chave):
    '''Insere uma chave na árvore, mantendo-a balanceada. Chaves duplicadas são ignoradas.'''
    self.raiz = self.inserir_recursivo(self.raiz, chave)


@adicionar_metodo(ArvoreAVL)
def inserir_recursivo(self, no, chave):
    '''Função auxiliar recursiva da inserção. Devolve a raiz da subárvore atualizada.'''
    # 1) Caso base: encontramos a posição vazia -> cria o novo nó
    if no is None:
        self.quantidade_de_nos += 1
        return NoAVL(chave)

    # 2) Descida da árvore binária de busca
    if chave < no.chave:
        no.esquerda = self.inserir_recursivo(no.esquerda, chave)
    elif chave > no.chave:
        no.direita = self.inserir_recursivo(no.direita, chave)
    else:
        return no   # chave já existe: nada muda

    # 3) Na volta da recursão: atualiza altura e rebalanceia
    return self.rebalancear(no)

@adicionar_metodo(ArvoreAVL)
def buscar(self, chave):
    '''Procura uma chave e devolve o NoAVL correspondente, ou None se não existir.'''
    no_atual = self.raiz
    while no_atual is not None:
        if chave == no_atual.chave:
            return no_atual
        elif chave < no_atual.chave:
            no_atual = no_atual.esquerda
        else:
            no_atual = no_atual.direita
    return None


@adicionar_metodo(ArvoreAVL)
def contem(self, chave):
    '''Retorna True se a chave estiver presente na árvore.'''
    return self.buscar(chave) is not None

@adicionar_metodo(ArvoreAVL)
def menor_no(self, no):
    '''Devolve o nó de menor chave da subárvore (o mais à esquerda).'''
    no_atual = no
    while no_atual.esquerda is not None:
        no_atual = no_atual.esquerda
    return no_atual


@adicionar_metodo(ArvoreAVL)
def maior_no(self, no):
    '''Devolve o nó de maior chave da subárvore (o mais à direita).'''
    no_atual = no
    while no_atual.direita is not None:
        no_atual = no_atual.direita
    return no_atual

@adicionar_metodo(ArvoreAVL)
def remover(self, chave):
    '''Remove uma chave da árvore, mantendo-a balanceada.'''
    self.raiz = self.remover_recursivo(self.raiz, chave)


@adicionar_metodo(ArvoreAVL)
def remover_recursivo(self, no, chave):
    '''Função auxiliar recursiva da remoção. Devolve a raiz da subárvore atualizada.'''
    # 1) Chave não encontrada
    if no is None:
        return None

    # 2) Descida da árvore binária de busca
    if chave < no.chave:
        no.esquerda = self.remover_recursivo(no.esquerda, chave)
    elif chave > no.chave:
        no.direita = self.remover_recursivo(no.direita, chave)
    else:
        # 3) Encontrou o nó a ser removido

        # CASO 1 - vértice folha
        if no.esquerda is None and no.direita is None:
            self.quantidade_de_nos -= 1
            return None

        # CASO 2 - vértice com apenas um filho
        if no.esquerda is None:
            self.quantidade_de_nos -= 1
            return no.direita
        if no.direita is None:
            self.quantidade_de_nos -= 1
            return no.esquerda

        # CASO 3 - vértice com dois filhos:
        # copia a chave do sucessor em ordem e remove o sucessor da subárvore direita
        sucessor = self.menor_no(no.direita)
        no.chave = sucessor.chave
        no.direita = self.remover_recursivo(no.direita, sucessor.chave)

    # 4) Na volta da recursão: atualiza altura e rebalanceia
    return self.rebalancear(no)

@adicionar_metodo(ArvoreAVL)
def percorrer_em_ordem(self, no="__raiz__", resultado=None):
    '''Percurso EM ORDEM: esquerda -> raiz -> direita (devolve a lista ordenada).'''
    if isinstance(no, str) and no == "__raiz__":
        no = self.raiz
    if resultado is None:
        resultado = []
    if no is not None:
        self.percorrer_em_ordem(no.esquerda, resultado)
        resultado.append(no.chave)
        self.percorrer_em_ordem(no.direita, resultado)
    return resultado

@adicionar_metodo(ArvoreAVL)
def percorrer_pre_ordem(self, no="__raiz__", resultado=None):
    '''Percurso PRÉ-ORDEM: raiz -> esquerda -> direita.'''
    if isinstance(no, str) and no == "__raiz__":
        no = self.raiz
    if resultado is None:
        resultado = []
    if no is not None:
        resultado.append(no.chave)
        self.percorrer_pre_ordem(no.esquerda, resultado)
        self.percorrer_pre_ordem(no.direita, resultado)
    return resultado


@adicionar_metodo(ArvoreAVL)
def percorrer_pos_ordem(self, no="__raiz__", resultado=None):
    '''Percurso PÓS-ORDEM: esquerda -> direita -> raiz.'''
    if isinstance(no, str) and no == "__raiz__":
        no = self.raiz
    if resultado is None:
        resultado = []
    if no is not None:
        self.percorrer_pos_ordem(no.esquerda, resultado)
        self.percorrer_pos_ordem(no.direita, resultado)
        resultado.append(no.chave)
    return resultado

@adicionar_metodo(ArvoreAVL)
def percorrer_por_nivel(self):
    '''Percurso POR NÍVEL (busca em largura), usando uma fila.

    Devolve uma lista de listas: uma lista de chaves para cada nível da árvore.
    '''
    if self.raiz is None:
        return []

    niveis = []
    fila = deque([self.raiz])

    while fila:
        chaves_do_nivel = []
        for _ in range(len(fila)):          # processa exatamente um nível por vez
            no_atual = fila.popleft()
            chaves_do_nivel.append(no_atual.chave)
            if no_atual.esquerda is not None:
                fila.append(no_atual.esquerda)
            if no_atual.direita is not None:
                fila.append(no_atual.direita)
        niveis.append(chaves_do_nivel)

    return niveis

@adicionar_metodo(ArvoreAVL)
def imprimir_arvore(self, titulo=None):
    '''Imprime a árvore girada 90°: raiz à esquerda, subárvore direita acima.'''
    if titulo is not None:
        print(titulo)
        print("-" * len(titulo))
    if self.raiz is None:
        print("(árvore vazia)\n")
        return
    self.desenhar_no(self.raiz, "")
    print()


@adicionar_metodo(ArvoreAVL)
def desenhar_no(self, no, recuo):
    '''Função auxiliar recursiva do desenho da árvore.'''
    if no is None:
        return
    self.desenhar_no(no.direita, recuo + "        ")
    print(f"{recuo}{no.chave}  [h={no.altura}, fb={self.fator_balanceamento(no):+d}]")
    self.desenhar_no(no.esquerda, recuo + "        ")

@adicionar_metodo(ArvoreAVL)
def esta_balanceada(self):
    '''Verifica se a árvore respeita a propriedade AVL em todos os nós.'''
    def verificar(no):
        if no is None:
            return True
        if abs(self.fator_balanceamento(no)) > 1:
            return False
        return verificar(no.esquerda) and verificar(no.direita)
    return verificar(self.raiz)


@adicionar_metodo(ArvoreAVL)
def eh_arvore_de_busca_valida(self):
    '''Verifica se as chaves estão em ordem crescente no percurso em ordem.'''
    chaves = self.percorrer_em_ordem()
    return all(chaves[i] < chaves[i + 1] for i in range(len(chaves) - 1))

arvore_rr = ArvoreAVL()

for chave in [10, 20, 30]:
    arvore_rr.inserir(chave)
    print(f"Após inserir {chave}: {arvore_rr.percorrer_por_nivel()}")

print()
arvore_rr.imprimir_arvore("Resultado (caso RR -> rotação à esquerda)")
print("Raiz:", arvore_rr.raiz.chave, "| Balanceada?", arvore_rr.esta_balanceada())

arvore_ll = ArvoreAVL()

for chave in [30, 20, 10]:
    arvore_ll.inserir(chave)
    print(f"Após inserir {chave}: {arvore_ll.percorrer_por_nivel()}")

print()
arvore_ll.imprimir_arvore("Resultado (caso LL -> rotação à direita)")
print("Raiz:", arvore_ll.raiz.chave, "| Balanceada?", arvore_ll.esta_balanceada())

arvore_lr = ArvoreAVL()

for chave in [30, 10, 20]:
    arvore_lr.inserir(chave)
    print(f"Após inserir {chave}: {arvore_lr.percorrer_por_nivel()}")

print()
arvore_lr.imprimir_arvore("Resultado (caso LR -> rotação dupla esquerda/direita)")
print("Raiz:", arvore_lr.raiz.chave, "| Balanceada?", arvore_lr.esta_balanceada())

arvore_rl = ArvoreAVL()

for chave in [10, 30, 20]:
    arvore_rl.inserir(chave)
    print(f"Após inserir {chave}: {arvore_rl.percorrer_por_nivel()}")

print()
arvore_rl.imprimir_arvore("Resultado (caso RL -> rotação dupla direita/esquerda)")
print("Raiz:", arvore_rl.raiz.chave, "| Balanceada?", arvore_rl.esta_balanceada())

arvore = ArvoreAVL()
chaves_para_inserir = [50, 25, 75, 10, 35, 60, 90, 5, 15, 30, 40, 1]

for chave in chaves_para_inserir:
    arvore.inserir(chave)
    print(f"Inserida a chave {chave:>3} | altura da árvore = {arvore.altura(arvore.raiz)} "
          f"| níveis = {arvore.percorrer_por_nivel()}")

print()
arvore.imprimir_arvore("Árvore final")

print("Em ordem  :", arvore.percorrer_em_ordem())
print("Pré-ordem :", arvore.percorrer_pre_ordem())
print("Pós-ordem :", arvore.percorrer_pos_ordem())
print("Por nível :", arvore.percorrer_por_nivel())
print()

for chave_procurada in [35, 99]:
    encontrado = arvore.buscar(chave_procurada)
    if encontrado is not None:
        print(f"Chave {chave_procurada}: ENCONTRADA -> {encontrado}")
    else:
        print(f"Chave {chave_procurada}: não encontrada")

print()
print("Total de nós:", len(arvore))
print("Ordem válida?", arvore.eh_arvore_de_busca_valida(), "| Balanceada?", arvore.esta_balanceada())

arvore_exemplo = ArvoreAVL()
for chave in [4, 2, 6, 7]:
    arvore_exemplo.inserir(chave)

arvore_exemplo.imprimir_arvore("Antes da remoção")

arvore_exemplo.remover(2)
arvore_exemplo.imprimir_arvore('Depois de remover o nó "2" (já rebalanceada)')

print("Por nível:", arvore_exemplo.percorrer_por_nivel())
print("Balanceada?", arvore_exemplo.esta_balanceada())

for chave_removida in [1, 5, 25]:
    quantidade_de_filhos = arvore.buscar(chave_removida).quantidade_de_filhos()
    arvore.remover(chave_removida)
    print(f"Removida a chave {chave_removida:>3} (tinha {quantidade_de_filhos} filho(s)) "
          f"| altura = {arvore.altura(arvore.raiz)} | balanceada = {arvore.esta_balanceada()}")

print()
arvore.imprimir_arvore("Árvore após as remoções")
print("Em ordem:", arvore.percorrer_em_ordem())

arvore_grande = ArvoreAVL()
quantidade = 1000

for chave in range(1, quantidade + 1):   # inserção em ordem crescente = pior caso
    arvore_grande.inserir(chave)

altura_avl = arvore_grande.altura(arvore_grande.raiz)
altura_bst_degenerada = quantidade - 1

print(f"Chaves inseridas (em ordem crescente): {quantidade}")
print(f"Altura da AVL...................: {altura_avl}")
print(f"Altura de uma BST degenerada....: {altura_bst_degenerada}")
print(f"Referência log2({quantidade}).............: {math.log2(quantidade):.2f}")
print(f"Ainda balanceada?...............: {arvore_grande.esta_balanceada()}")
print()
print(f"Comparações no pior caso -> AVL: ~{altura_avl + 1} | BST degenerada: ~{quantidade}")

# Espaço para os exercícios
# Exercício 1 - confira aqui a sua resposta feita no papel:

arvore_exercicio = ArvoreAVL()
for chave in [15, 10, 20, 8, 12, 5]:
    arvore_exercicio.inserir(chave)
    print(f"Após inserir {chave:>2}: {arvore_exercicio.percorrer_por_nivel()}")

print()
arvore_exercicio.imprimir_arvore("Sua árvore")