Arvore Binaria de Busca com Persistencia Parcial (Node Copying)

Linguagem

C++ (C++11 ou superior)

Como compilar e executar

make build
make run
# Ou com outro arquivo de entrada:
make run INPUT="outro_arquivo.txt"

Ou manualmente:

g++ -o programa.exe ABB.cpp
./programa.exe entrada.txt

Estruturas

Todas as estruturas e funcoes estao no arquivo ABB.cpp.

struct No

Representa um no da arvore binaria de busca.

• valor — valor inteiro armazenado no no
• prof — profundidade do no (raiz = 0)
• esq — ponteiro para o filho esquerdo
• dir — ponteiro para o filho direito

class ABB

Implementa a arvore binaria de busca persistente com node copying.

Metodos publicos:

• inserir(int valor) — insere um valor na ABB, criando uma nova versao por node copying
• remover(int valor) — remove um no com o valor dado, criando uma nova versao por node copying
• sucessorMaior(int valor, int versao) — retorna o menor valor estritamente maior que o valor dado na versao indicada
• imprimir(int versao, ofstream& saida) — imprime os elementos da versao em ordem crescente no formato valor,profundidade
• getRaiz(int versao) — retorna a raiz da versao indicada
• liberar() — desaloca todos os nos de todas as versoes (usa um conjunto para evitar double-free de nos compartilhados)

Metodos privados (auxiliares):

• novoNo(int valor, int prof) — cria um novo no
• copiarNo(No* original, int prof) — cria uma copia rasa de um no (shallow copy para node copying)
• inserirNC(No* raiz, int valor, int prof) — insercao recursiva com node copying
• removerNC(No* raiz, int valor) — remocao recursiva com node copying
• minNo(No* no) — encontra o menor no de uma subarvore
• imprimirRec(No* no, bool& primeiro, ofstream& saida) — impressao recursiva em ordem
• coletarNos(No* no, set<No*>& todos) — coleta todos os ponteiros de nos para liberacao segura

main

Le o arquivo de entrada passado como argumento e processa os comandos:

• INC x — insere x na versao atual, criando nova versao por node copying
• REM x — remove x da versao atual, criando nova versao por node copying
• SUC x v — imprime o sucessor estritamente maior que x na versao v
• IMP v — imprime todos os elementos da versao v no formato valor,profundidade

O vetor roots[100] dentro da classe armazena ate 100 raizes de versoes. Nos compartilhados entre versoes nao sao duplicados (persistencia por node copying).