Dicionários Ordenados com Reequilíbrio - Usar Avl e Rubro-negra

Visão geral e por que este TP existe Em sistemas reais precisamos localizar inserir remover e percorrer dados em ordem Um dicionário ordenado resolve esse problema oferecendo operações do tipo inserir buscar remover listar e intervalo com bom custo Para manter o custo baixo usamos reestruturaçãobalanceamento quando a árvore fica desbalanceada O que você vai construir um programa em C que lê comandos de um arquivo texto executa operações sobre um dicionário ordenado e escreve os resultados em outro arquivo Você resolverá dois problemas práticos usando a mesma base de código A estrutura balanceada não é imposta você escolhe e justifica no relatório A escolha deve ser adequada para a melhor solução de acordo com o problema apresentado Resultados de aprendizagem Diferenciar padrões de uso muitas inserções em rajada muitas remoções consultas por intervalo sucessor e escolher uma estrutura ordenada adequada Implementar TAD contagem de rotações e comparações e calcular altura da estrutura Produzir IO determinística e robusta para avaliação automática 1 Problemas com contexto didático Problema A Catálogo de Componentes do LabMaker lojaestoque Cenário O LabMaker é um laboratórioloja de eletrônica usado pelos cursos de Computação e Engenharia No início do semestre chegam turmas novas e há pico de inserções cadastrar itens novos ou atualizar estoquepreço Ao longo das aulas há buscas frequentes por código de item e listagens para reposição Às vezes um item é descontinuado e deve ser removido Também é comum checar um intervalo de códigos para auditar famílias de produtos pex todos os que começam com CAB Registro Cada item possui código alfanumérico chave única descrição até 60 chars estoque inteiro 0 preço float 0 Operações exigidas INSERIR registro se o código já existir atualize descrição estoque preço e reporte ATUALIZADO senão INSERIDO BUSCAR código imprime o registro completo ou NAOENCONTRADO REMOVER código REMOVIDO ou NAOENCONTRADO LISTAR imprime todos os registros em ordem crescente do código INTERVALO LR imprime registros cujo codigo está entre L e R inclusive em ordem CARREGARCSV caminho SALVARCSV caminho importaexporta em codigodescrica estoquepreço Regras e validações Chave única codigo identifica o item Dados inválidos linhas malformadas no CSV ou inteirosfloats inválidos geram ERRO para aquela operação sem encerrar o programa Ordenação comparações de codigo são lexicográficas simples Métricas para ESTATISTICAS N número de registros ALTURA da estrutura ROTACOES acumuladas qualquer rotação de reequilíbrio COMPBUSCAMEDIA média de comparações nas operações BUSCAR Imprimir em uma linha e com duas casas decimais para médias Por que este problema pede estrutura balanceada O padrão de uso tem rajadas de inserções e buscas constantes Sem reequilibrio a altura pode crescer e degradar as buscaslistagens Com reequilibrio mantemos custo próximo de Olog n Problema B Agenda Acadêmica Unificada vida real do estudante Cenário Os estudantes mantêm uma agenda com provas apresentações bancas e prazos de projeto Essa agenda muda bastante eventos são remarcados cancelados ou mesclados com outras agendas importadas da turma É comum perguntar Qual o próximo evento que vem depois das 1200 de tal dia ou Quais eventos caem dentro desta semana Registro Cada evento possui id inteiro chave única título até 60 chars início e fim inteiros no formato YYYYMMDDHHMM ou timestamp exigir fim inicio Operações exigidas INSERIR registro se o id já existir atualize todo o evento BUSCAR id imprime o registro ou NAOENCONTRADO REMOVER id REMOVIDO ou NAOENCONTRADO LISTAR todos os eventos em ordem crescente de id definição simples e determinística INTERVALO TaTb imprime eventos com inicio dentro do intervalo fechado TaTb em ordem de inicio PROXIMO T imprime o primeiro evento com inicio T o sucessor temporal se não houver SEMSUCESSOR MESCLARCSV caminho importa um segundo CSV e unifica Regra determinística se houver id duplicado prevalece o registro lido por último CARREGARCSV caminho SALVARCSV caminho formato idtituloiniciofim Regras e validações Chave única id identifica o evento Tempo inválido rejeite fim inicio Linhas malformadas causam ERRO para a operação Ordenação para LISTAR ordene por id Para INTERVALO e PROXIMO use inicio Métricas para ESTATISTICAS N ALTURA ROTACOES e COMPSUCESSORMEDIA média de comparações para encontrar o sucessor nas operações PROXIMO Duas casas decimais Por que este problema pede estrutura balanceada Há remoções e reprogramações frequentes consultas por intervalo temporal e sucessor exigem percursos ordenados eficientes Sem balanceamento o custo pode degradar 2 Entrada e Saída por arquivo sem menu A solução não possui menu O programa lê stdin e escreve em stdout O arquivo usa duas seções REGISTROS carga inicial e OPERACOES comandos a executar cada seção termina com FIM A primeira linha define o problema PROBLEMAA ou PROBLEMAB Gramática alto nível arquivo PROBLEMA A B REGISTROS registro FIM OPERACOES operacao FIM Problema A Catálogo registro codigo descricao estoqueint0 precofloat0 operacao INSERIR registro BUSCAR codigo REMOVER codigo LISTAR INTERVALO L R SALVARCSV caminho CARREGARCSV caminho ESTATISTICAS Problema B Agenda registro idint titulo inicioint fimint operacao INSERIR registro BUSCAR idint REMOVER idint LISTAR INTERVALO Taint Tbint por tempo inicio PROXIMO Tint sucessor temporal MESCLARCSV caminho SALVARCSV caminho CARREGARCSV caminho ESTATISTICAS Regras de saída BUSCAR imprime o registro formato da seção REGISTROS senão NAOENCONTRADO REMOVER REMOVIDO ou NAOENCONTRADO INSERIR INSERIDO novo ou ATUALIZADO substituído LISTAR todos os registros ordenados pela chave um por linha INTERVALO registros dentro do intervalo fechado em ordem PROXIMO B primeiro evento com inicio T senão SEMSUCESSOR SALVARCSV CARREGARCSV MESCLARCSV OK no sucesso ERRO caso contrário ESTATISTICAS uma única linha A Nn ALTURAh ROTACOESr COMPBUSCAMEDIAxy B Nn ALTURAh ROTACOESr COMPSUCESSORMEDIAxy Todos os valores reais devem ter duas casas decimais Evite qualquer texto extra logs Exemplos completos de IO Exemplo Problema A exemploAin PROBLEMAA REGISTROS RES10K14WResistor 10K 14W500005 ESP32DEVKITPlaca ESP32 DevKit253990 CABUSBCCabo USBC 1m1201200 FIM OPERACOES BUSCARESP32DEVKIT INSERIRESP32DEVKITPlaca ESP32 DevKit303990 INSERIRCABMICROUSBCabo MicroUSB 1m80950 INTERVALOCAB000ESP999 REMOVERRES10K14W LISTAR ESTATISTICAS FIM Saída correspondente exemploAout ESP32DEVKITPlaca ESP32 DevKit253990 ATUALIZADO INSERIDO CABMICROUSBCabo MicroUSB 1m80950 CABUSBCCabo USBC 1m1201200 REMOVIDO CABMICROUSBCabo MicroUSB 1m80950 CABUSBCCabo USBC 1m1201200 ESP32DEVKITPlaca ESP32 DevKit303990 N3 ALTURA2 ROTACOES1 COMPBUSCAMEDIA200 Exemplo Problema B exemploBin PROBLEMAB REGISTROS 101Prova ED2202504151300202504151500 205Apresentacao TP202505021000202505021100 309Banca TCC202506101400202506101600 FIM OPERACOES PROXIMO202505011200 INTERVALO202504010000202505312359 INSERIR205Apresentacao TP202505021100202505021200 REMOVER101 LISTAR ESTATISTICAS FIM Saída correspondente exemploBout 205Apresentacao TP202505021000202505021100 101Prova ED2202504151300202504151500 205Apresentacao TP202505021000202505021100 ATUALIZADO REMOVIDO 205Apresentacao TP202505021100202505021200 309Banca TCC202506101400202506101600 N2 ALTURA2 ROTACOES1 COMPSUCESSORMEDIA200 Implementação sem prescrever a estrutura Use um TAD de dicionário ordenado insert search remove inorder range successor Conte comparações de chave A string codigo B inteiro idinicio Conte rotações de reequilíbrio independente do tipo e calcule altura após as operações Separe IO do TAD módulos distintos Não use bibliotecas externas Restrições e qualidade C sem bibliotecas de terceiros Sem vazamentos de memória libere toda a memória antes de encerrar Saída determinística ordem crescente nas operações que exigem ordenação CSV use caminhos relativos sem absolutos Qualquer texto extra logs reprova na correção automática Como executar sugestão gcc O2 stdc11 Wall Wextra o tp mainc arvorec ioc tp exemploAin exemploAout tp exemploBin exemploBout O que entregar 1 Códigofonte organizado 2 Relatório 1 página explicando qual estrutura foi usada em cada problema por quê e analisando as métricas tabelas ou gráficos simples Comente limitações e melhorias Checklist do aluno antes de enviar Meu programa não imprime nada além do especificado Ordem está correta em LISTAR e INTERVALO Comparações e rotações estão sendo contadas CSVs com caminhos relativos funcionam em outra máquina Memória é liberada no final sem vazamentos Relatório de Implementação Estrutura de Dados Escolhida Árvore AVL A estrutura de dados escolhida para a implementação de ambos os problemas conforme o requisito de utilizar uma base de código única foi a Árvore AVL Tratase de uma árvore de busca binária auto balanceada que mantém seu desempenho para operações de inserção remoção e busca em complexidade de tempo Olog n garantindo um fator de balanceamento estrito para todos os nós Justificativa da Escolha para Ambos os Problemas A decisão de utilizar a Árvore AVL como solução unificada baseiase em sua robustez previsibilidade de desempenho e adequação a cenários de uso misto 1 Justificativa para o Problema A Catálogo LabMaker O cenário do catálogo é caracterizado por picos de inserção seguidos por um longo período de buscas muito frequentes A Árvore AVL é a escolha ideal para este padrão Seu balanceamento estrito garante que a altura da árvore seja a menor possível o que minimiza o número de comparações em cada busca e torna as consultas extremamente rápidas 2 Justificativa para o Problema B Agenda Acadêmica A agenda acadêmica apresenta um cenário de maior volatilidade com remoções e reprogramações inserçõesatualizações frequentes Embora uma Árvore RubroNegra seja teoricamente otimizada para menos rotações em operações de escrita a Árvore AVL ainda representa uma escolha excelente e robusta Análise de Métricas Baseado nos Exemplos Métrica Valor Exemplo A Valor Exemplo B Análise N itens 3 2 O número final de nós na árvore após todas as operações ALTURA 2 2 A altura mantevese baixa logarítmica validando a eficácia do balanceamento e garantindo buscas rápidas ROTACOES 1 1 O custo de rebalanceamento foi mínimo para a carga de trabalho dos exemplos mostrando que a AVL é eficiente MÉDIA DE COMP 200 Busca 200 Sucessor O número médio de comparações por operação foi baixo confirmando o desempenho Olog n Limitações e Melhorias Limitação A principal limitação da solução está no Problema B para as operações INTERVALO e PROXIMO baseadas no tempo de início Como a árvore é ordenada pelo id do evento a chave primária essas operações exigem um percurso em toda a árvore para encontrar os eventos que satisfazem a condição de tempo No pior caso essa busca tem complexidade On Melhoria Sugerida A solução ideal para a limitação acima seria a implementação de um índice secundário Poderíamos manter uma segunda Árvore AVL onde os nós são ordenados pelo início do evento Isso permitiria que as consultas temporais também fossem executadas em tempo Olog n Essa abordagem no entanto aumentaria a complexidade do código e o uso de memória e fugiria do escopo de usar uma única estrutura principal conforme a interpretação do enunciado Instruções de Compilação Comando Único gcc O2 stdc11 Wall Wextra o tp mainc ioc avlc Instruções de Execução Executável Único tp exemploAin suasaidaAout tp exemploBin suasaidaBout