Estrutura de Dados — Atividade Proposta

import random
import math

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

print("Ambiente pronto.")

class Pokemon:
    '''Representa um Pokemon do jogo: nome e valor de forca (inteiro).'''

    def __init__(self, nome, forca):
        self.nome = nome
        self.forca = int(forca)

    def chave_nome(self):
        '''Chave usada na arvore indexada por nome (normalizada, sem diferenciar maiusculas).'''
        return self.nome.casefold()

    def chave_forca(self):
        '''Chave composta usada na arvore indexada por forca; o nome desempata forcas iguais.'''
        return (self.forca, self.chave_nome())

    def __repr__(self):
        return f"{self.nome} (forca {self.forca})"

# Teste rapido da entidade
pikachu = Pokemon("Pikachu", 55)

print(pikachu)
print("Chave para o indice por nome :", pikachu.chave_nome())
print("Chave para o indice por forca:", pikachu.chave_forca())

# Tuplas sao comparadas elemento a elemento: primeiro a forca, depois o nome
print("(55,'eevee') < (55,'pikachu') ?", (55, "eevee") < (55, "pikachu"))
print("(55,'pikachu') < (84,'charizard') ?", (55, "pikachu") < (84, "charizard"))

class NoAVL:
    '''Vertice da arvore AVL: guarda a chave de ordenacao e o valor (o Pokemon) associado.'''

    def __init__(self, chave, valor):
        self.chave = chave        # o que ordena a arvore
        self.valor = valor        # o objeto Pokemon
        self.esquerda = None
        self.direita = None
        self.altura = 0           # folha tem altura 0 (contagem por arestas)

    def eh_folha(self):
        return self.esquerda is None and self.direita is None

    def quantidade_de_filhos(self):
        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!r}, valor={self.valor!r})"

class ArvoreAVL:
    '''Arvore binaria de busca balanceada (AVL), generica em chave e valor.'''

    def __init__(self):
        self.raiz = None
        self.quantidade_de_nos = 0

    def esta_vazia(self):
        return self.raiz is None

    def __len__(self):
        return self.quantidade_de_nos

@adicionar_metodo(ArvoreAVL)
def altura(self, no):
    '''Altura da subarvore; subarvore 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 no a partir das alturas dos filhos.'''
    no.altura = 1 + max(self.altura(no.esquerda), self.altura(no.direita))


@adicionar_metodo(ArvoreAVL)
def fator_balanceamento(self, no):
    '''fb = altura(subarvore direita) - altura(subarvore esquerda).'''
    if no is None:
        return 0
    return self.altura(no.direita) - self.altura(no.esquerda)

@adicionar_metodo(ArvoreAVL)
def rotacao_esquerda(self, no):
    '''Rotacao simples a ESQUERDA - corrige o caso RR. Devolve a nova raiz da subarvore.'''
    novo_topo = no.direita
    no.direita = novo_topo.esquerda      # a subarvore do meio troca de pai
    novo_topo.esquerda = no
    self.atualizar_altura(no)
    self.atualizar_altura(novo_topo)
    return novo_topo


@adicionar_metodo(ArvoreAVL)
def rotacao_direita(self, no):
    '''Rotacao simples a DIREITA - corrige o caso LL. Devolve a nova raiz da subarvore.'''
    novo_topo = no.esquerda
    no.esquerda = novo_topo.direita      # a subarvore do meio troca de pai
    novo_topo.direita = no
    self.atualizar_altura(no)
    self.atualizar_altura(novo_topo)
    return novo_topo

@adicionar_metodo(ArvoreAVL)
def rotacao_dupla_esquerda_direita(self, no):
    '''Rotacao DUPLA - corrige o caso LR (transforma LR em LL e resolve).'''
    no.esquerda = self.rotacao_esquerda(no.esquerda)
    return self.rotacao_direita(no)


@adicionar_metodo(ArvoreAVL)
def rotacao_dupla_direita_esquerda(self, no):
    '''Rotacao DUPLA - corrige o caso RL (transforma RL em RR e resolve).'''
    no.direita = self.rotacao_direita(no.direita)
    return self.rotacao_esquerda(no)

@adicionar_metodo(ArvoreAVL)
def rebalancear(self, no):
    '''Atualiza a altura e aplica a rotacao necessaria, se houver desbalanceio.'''
    self.atualizar_altura(no)
    fator = self.fator_balanceamento(no)

    if fator > 1:                                            # pesado a direita
        if self.fator_balanceamento(no.direita) >= 0:
            return self.rotacao_esquerda(no)                 # caso RR
        return self.rotacao_dupla_direita_esquerda(no)       # caso RL

    if fator < -1:                                           # pesado a esquerda
        if self.fator_balanceamento(no.esquerda) <= 0:
            return self.rotacao_direita(no)                  # caso LL
        return self.rotacao_dupla_esquerda_direita(no)       # caso LR

    return no

@adicionar_metodo(ArvoreAVL)
def inserir(self, chave, valor):
    '''Insere (ou atualiza) um par chave/valor. Custo O(log n).'''
    self.raiz = self.inserir_recursivo(self.raiz, chave, valor)


@adicionar_metodo(ArvoreAVL)
def inserir_recursivo(self, no, chave, valor):
    if no is None:                                   # posicao vazia encontrada
        self.quantidade_de_nos += 1
        return NoAVL(chave, valor)

    if chave < no.chave:
        no.esquerda = self.inserir_recursivo(no.esquerda, chave, valor)
    elif chave > no.chave:
        no.direita = self.inserir_recursivo(no.direita, chave, valor)
    else:
        no.valor = valor                             # chave ja existe: atualiza
        return no

    return self.rebalancear(no)                      # na volta da recursao

@adicionar_metodo(ArvoreAVL)
def buscar_no(self, chave):
    '''Devolve o NoAVL correspondente a chave, ou None. Custo O(log n).'''
    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 buscar(self, chave):
    '''Devolve o valor (o Pokemon) associado a chave, ou None.'''
    no_encontrado = self.buscar_no(chave)
    return None if no_encontrado is None else no_encontrado.valor

@adicionar_metodo(ArvoreAVL)
def menor_no(self, no):
    '''Sucessor em ordem: o no mais a esquerda da subarvore.'''
    while no.esquerda is not None:
        no = no.esquerda
    return no


@adicionar_metodo(ArvoreAVL)
def remover(self, chave):
    '''Remove a chave; devolve True se ela existia. Custo O(log n).'''
    if self.buscar_no(chave) is None:
        return False
    self.raiz = self.remover_recursivo(self.raiz, chave)
    return True

@adicionar_metodo(ArvoreAVL)
def remover_recursivo(self, no, chave):
    if no is None:
        return None

    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:
        # CASO 1 - vertice folha
        if no.esquerda is None and no.direita is None:
            self.quantidade_de_nos -= 1
            return None

        # CASO 2 - vertice 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 - vertice com dois filhos (copia chave E valor do sucessor)
        sucessor = self.menor_no(no.direita)
        no.chave = sucessor.chave
        no.valor = sucessor.valor
        no.direita = self.remover_recursivo(no.direita, sucessor.chave)

    return self.rebalancear(no)

@adicionar_metodo(ArvoreAVL)
def em_ordem(self, no="__raiz__", resultado=None):
    '''Percurso em ordem CRESCENTE de chave. Custo O(n).'''
    if isinstance(no, str):
        no = self.raiz
    if resultado is None:
        resultado = []
    if no is not None:
        self.em_ordem(no.esquerda, resultado)
        resultado.append(no.valor)
        self.em_ordem(no.direita, resultado)
    return resultado


@adicionar_metodo(ArvoreAVL)
def em_ordem_inversa(self, no="__raiz__", resultado=None):
    '''Percurso em ordem DECRESCENTE de chave: direita -> raiz -> esquerda. Custo O(n).'''
    if isinstance(no, str):
        no = self.raiz
    if resultado is None:
        resultado = []
    if no is not None:
        self.em_ordem_inversa(no.direita, resultado)
        resultado.append(no.valor)
        self.em_ordem_inversa(no.esquerda, resultado)
    return resultado

@adicionar_metodo(ArvoreAVL)
def esta_balanceada(self, no="__raiz__"):
    '''Verifica se |fb| <= 1 em todos os nos.'''
    if isinstance(no, str):
        no = self.raiz
    if no is None:
        return True
    if abs(self.fator_balanceamento(no)) > 1:
        return False
    return self.esta_balanceada(no.esquerda) and self.esta_balanceada(no.direita)


@adicionar_metodo(ArvoreAVL)
def imprimir_arvore(self, titulo=None):
    '''Desenha a arvore girada 90 graus: raiz a esquerda, subarvore direita acima.'''
    if titulo is not None:
        print(titulo)
        print("-" * len(titulo))
    if self.raiz is None:
        print("(arvore vazia)\n")
        return
    self.desenhar_no(self.raiz, "")
    print()


@adicionar_metodo(ArvoreAVL)
def desenhar_no(self, no, recuo):
    if no is None:
        return
    self.desenhar_no(no.direita, recuo + "        ")
    print(f"{recuo}{no.valor}  [h={no.altura}, fb={self.fator_balanceamento(no):+d}]")
    self.desenhar_no(no.esquerda, recuo + "        ")

class GerenciadorPokemon:
    '''Sistema de gerenciamento de Pokemon apoiado em duas Arvores AVL.'''

    def __init__(self):
        self.arvore_por_nome = ArvoreAVL()    # chave: nome normalizado
        self.arvore_por_forca = ArvoreAVL()   # chave: (forca, nome normalizado)

    def __len__(self):
        return len(self.arvore_por_nome)

@adicionar_metodo(GerenciadorPokemon)
def inserir_pokemon(self, nome, forca):
    '''Cadastra um Pokemon novo ou atualiza a forca de um ja existente. Custo O(log n).'''
    ja_cadastrado = self.arvore_por_nome.buscar(nome.casefold())

    if ja_cadastrado is not None:
        # a chave do indice por forca vai mudar: remove com a chave antiga...
        self.arvore_por_forca.remover(ja_cadastrado.chave_forca())
        ja_cadastrado.forca = int(forca)
        # ...e reinsere com a nova
        self.arvore_por_forca.inserir(ja_cadastrado.chave_forca(), ja_cadastrado)
        return ja_cadastrado

    pokemon = Pokemon(nome, forca)
    self.arvore_por_nome.inserir(pokemon.chave_nome(), pokemon)
    self.arvore_por_forca.inserir(pokemon.chave_forca(), pokemon)
    return pokemon

@adicionar_metodo(GerenciadorPokemon)
def buscar_por_nome(self, nome):
    '''Devolve o Pokemon com esse nome (com seu valor de forca), ou None. Custo O(log n).'''
    return self.arvore_por_nome.buscar(nome.casefold())

@adicionar_metodo(GerenciadorPokemon)
def remover_por_nome(self, nome):
    '''Remove o Pokemon dos dois indices. Devolve True se ele existia. Custo O(log n).'''
    pokemon = self.arvore_por_nome.buscar(nome.casefold())
    if pokemon is None:
        return False
    self.arvore_por_nome.remover(pokemon.chave_nome())
    self.arvore_por_forca.remover(pokemon.chave_forca())
    return True

@adicionar_metodo(GerenciadorPokemon)
def listar_por_forca_decrescente(self):
    '''Lista todos os Pokemon do mais forte para o mais fraco. Custo O(n).'''
    return self.arvore_por_forca.em_ordem_inversa()


@adicionar_metodo(GerenciadorPokemon)
def listar_por_nome(self):
    '''Lista todos os Pokemon em ordem alfabetica. Custo O(n).'''
    return self.arvore_por_nome.em_ordem()


@adicionar_metodo(GerenciadorPokemon)
def indices_balanceados(self):
    '''Confere se os dois indices continuam respeitando a propriedade AVL.'''
    return self.arvore_por_nome.esta_balanceada() and self.arvore_por_forca.esta_balanceada()

gerenciador = GerenciadorPokemon()

equipe = [
    ("Pikachu", 55), ("Charizard", 84), ("Bulbasaur", 49), ("Squirtle", 48),
    ("Mewtwo", 110), ("Snorlax", 110), ("Gengar", 65), ("Eevee", 55),
    ("Dragonite", 134), ("Machamp", 130), ("Alakazam", 50), ("Onix", 45),
]

for nome, forca in equipe:
    gerenciador.inserir_pokemon(nome, forca)

print(f"Pokemon cadastrados: {len(gerenciador)}")
print(f"Altura do indice por nome .: {gerenciador.arvore_por_nome.altura(gerenciador.arvore_por_nome.raiz)}")
print(f"Altura do indice por forca : {gerenciador.arvore_por_forca.altura(gerenciador.arvore_por_forca.raiz)}")
print(f"Altura minima teorica (log2 de 12): {math.log2(12):.2f}")
print(f"Indices balanceados? {gerenciador.indices_balanceados()}")

gerenciador.arvore_por_nome.imprimir_arvore("INDICE POR NOME (ordem alfabetica)")

gerenciador.arvore_por_forca.imprimir_arvore("INDICE POR FORCA (ordem crescente de forca)")

for nome_procurado in ["Gengar", "pikachu", "MEWTWO", "Dragonite", "Ditto"]:
    encontrado = gerenciador.buscar_por_nome(nome_procurado)
    if encontrado is None:
        print(f"  {nome_procurado:<12} -> nao encontrado na arvore")
    else:
        print(f"  {nome_procurado:<12} -> ENCONTRADO: nome={encontrado.nome}, forca={encontrado.forca}")

ranking = gerenciador.listar_por_forca_decrescente()

print("RANKING - do mais forte ao mais fraco")
print("-" * 38)
for posicao, pokemon in enumerate(ranking, start=1):
    barra = "#" * (pokemon.forca // 5)
    print(f"  {posicao:>2}. {pokemon.nome:<12} {pokemon.forca:>4}  {barra}")

# Verificacao automatica da ordem
forcas = [pokemon.forca for pokemon in ranking]
print("\nOrdem decrescente correta?", forcas == sorted(forcas, reverse=True))
print("Todos os Pokemon aparecem?", len(ranking) == len(gerenciador))

print(f"{'Pokemon':<12} {'caso':<24} {'resultado':<12} {'restam':<7} balanceado")
print("-" * 70)

descricao_do_caso = {0: "vertice folha", 1: "vertice com um filho", 2: "vertice com dois filhos"}

for nome_removido in ["Squirtle", "Onix", "Charizard", "Ditto"]:
    no_do_indice = gerenciador.arvore_por_nome.buscar_no(nome_removido.casefold())
    caso = descricao_do_caso[no_do_indice.quantidade_de_filhos()] if no_do_indice else "nao cadastrado"

    foi_removido = gerenciador.remover_por_nome(nome_removido)

    print(f"{nome_removido:<12} {caso:<24} {('removido' if foi_removido else 'inexistente'):<12} "
          f"{len(gerenciador):<7} {gerenciador.indices_balanceados()}")

gerenciador.arvore_por_nome.imprimir_arvore("INDICE POR NOME apos as remocoes")
print("Ranking atualizado:", [f"{p.nome} ({p.forca})" for p in gerenciador.listar_por_forca_decrescente()])

nomes_no_indice_de_nome = sorted(p.nome for p in gerenciador.listar_por_nome())
nomes_no_indice_de_forca = sorted(p.nome for p in gerenciador.listar_por_forca_decrescente())

print("Indice por nome :", nomes_no_indice_de_nome)
print("Indice por forca:", nomes_no_indice_de_forca)
print("\nOs dois indices contem o mesmo conjunto?", nomes_no_indice_de_nome == nomes_no_indice_de_forca)
print("Mesma quantidade de nos?",
      len(gerenciador.arvore_por_nome) == len(gerenciador.arvore_por_forca))

print("Antes :", [f"{p.nome}({p.forca})" for p in gerenciador.listar_por_forca_decrescente()])

gerenciador.inserir_pokemon("Pikachu", 150)   # Pikachu treinou muito

print("Depois:", [f"{p.nome}({p.forca})" for p in gerenciador.listar_por_forca_decrescente()])
print()
print("Total de Pokemon (nao pode ter duplicado):", len(gerenciador))
print("Busca por nome ainda funciona:", gerenciador.buscar_por_nome("pikachu"))
print("Indices balanceados?", gerenciador.indices_balanceados())

random.seed(42)

pokedex = GerenciadorPokemon()
quantidade = 2000

for indice in range(quantidade):
    pokedex.inserir_pokemon(f"pokemon_{indice:05d}", random.randint(1, 300))

altura_avl = pokedex.arvore_por_nome.altura(pokedex.arvore_por_nome.raiz)

print(f"Pokemon cadastrados .............: {len(pokedex)}")
print(f"Altura do indice AVL ............: {altura_avl}")
print(f"Altura de uma BST degenerada ....: {quantidade - 1}")
print(f"Referencia log2({quantidade}) ...........: {math.log2(quantidade):.2f}")
print(f"Comparacoes na busca (pior caso) : ~{altura_avl + 1} em vez de ~{quantidade}")
print(f"Indices balanceados? {pokedex.indices_balanceados()}")

ranking_completo = pokedex.listar_por_forca_decrescente()
forcas = [p.forca for p in ranking_completo]
print(f"\nListagem com {len(ranking_completo)} Pokemon em ordem decrescente correta? "
      f"{forcas == sorted(forcas, reverse=True)}")
print("Top 5:", [f"{p.nome}({p.forca})" for p in ranking_completo[:5]])

verificacoes = {
    "Objetivo 1 - arvore mantem-se balanceada": pokedex.indices_balanceados(),
    "Objetivo 2 - busca encontra um Pokemon existente": pokedex.buscar_por_nome("pokemon_00042") is not None,
    "Objetivo 2 - busca devolve None para inexistente": pokedex.buscar_por_nome("mewthree") is None,
    "Objetivo 3 - listagem em ordem decrescente": forcas == sorted(forcas, reverse=True),
    "Objetivo 4 - remocao de existente devolve True": pokedex.remover_por_nome("pokemon_00042") is True,
    "Objetivo 4 - remocao de inexistente devolve False": pokedex.remover_por_nome("mewthree") is False,
    "Objetivo 4 - Pokemon removido nao e mais encontrado": pokedex.buscar_por_nome("pokemon_00042") is None,
    "Consistencia - indices com o mesmo tamanho": len(pokedex.arvore_por_nome) == len(pokedex.arvore_por_forca),
    "Consistencia - arvore balanceada apos remocoes": pokedex.indices_balanceados(),
}

for descricao, resultado in verificacoes.items():
    print(f"  [{'OK ' if resultado else 'FALHOU'}] {descricao}")

print("\nTodos os testes passaram!" if all(verificacoes.values()) else "\nHa testes falhando.")