Árvore Binária de Busca com Persistência Parcial

Este projeto implementa uma Árvore Binária de Busca (BST) utilizando o método de persistência parcial. A estrutura permite realizar inserções e remoções que geram novas versões da árvore, além de possibilitar consultas (sucessor e impressão) em qualquer versão anterior ou na mais atual.

🛠 Linguagem e Requisitos

• Linguagem: C
• Compilador: GCC
• Ferramentas: make para automação de build e execução

🚀 Como Rodar

O projeto utiliza um makefile para facilitar o processo de compilação e execução.

1. Compilação

Para compilar o código e gerar o executável main, utilize o comando:

make build

2. Execução

Para executar o programa passando um arquivo de entrada (por padrão input_files/input_file.txt), utilize:

make run

Caso deseje utilizar um arquivo de entrada específico, utilize a variável INPUT:

make run INPUT=caminho/do/seu/arquivo.txt

📂 Estrutura de Arquivos

• main.c: Contém a função principal, a lógica de leitura do arquivo de entrada e o processamento dos comandos (INC, REM, SUC, IMP).
• persistent_bst.c: Contém a implementação de todas as funções da árvore persistente.
• persistent_bst.h: Contém as definições das estruturas de dados e os protótipos das funções.
• makefile: Scripts para compilação e execução automatizada.

📊 Descrição das Estruturas e Funções

As seguintes estruturas e funções foram utilizadas para implementar a persistência parcial:

Estruturas (persistent_bst.h)

• struct modification: Armazena uma modificação específica em um nó (versão, novo valor e novos ponteiros para filhos).
• struct persistent_bst_node: O nó da árvore. Contém o valor original, ponteiros para filhos e pai (utilizado como ponteiro de retorno), um array de modificações (mods) e um contador de modificações.
• struct persistent_bst: Estrutura principal que mantém o ponteiro para a raiz atual, a versão mais recente e um vetor (root_versions) que armazena os ponteiros das raízes de cada versão (máximo de 100 versões).

Funções (persistent_bst.c)

• create_persistent_bst: Inicializa a árvore e configura a versão 0.
• include_new_node: Insere um novo valor na árvore, criando uma nova versão.
• remove_node: Remove um valor da árvore. Mesmo que o valor não exista, uma nova versão é criada conforme a especificação.
• modify_node: Função auxiliar que aplica modificações em um nó. Se o nó já estiver cheio (2 modificações), cria um novo nó e propaga a mudança para o pai.
• get_sucessor_value_by_version: Busca o sucessor de um valor em uma versão específica.
• print_tree: Imprime a árvore de uma versão específica em ordem crescente, exibindo o valor e a profundidade de cada nó.
• get_root_by_node / get_successor_node: Funções auxiliares para navegação e manutenção da estrutura da árvo