Implementei todas as estruturas de dados discutidas na minha tese de mestrado. As implementações foram feitas em C++, e tentam ser o mais fiel possível ao pseudocódigo apresentado na tese, destacando as diferenças quando estas existem.
Implementações Persistentes
Pilha
A pilha é a estrutura de dados mais simples, e, implementada usando lista ligada, já é automaticamente persistente. Para acessar o k-ésimo elemento usando esta implementação, porém, é necessário usar técnicas mais avançadas [3] .
Fila
Como a implementação de pilha possui acesso ao k-ésimo elemento, é possível implementar uma fila usando apenas essa implementação e um inteiro indicando o tamanho atual da fila.
Deque
A deque é uma lista na qual é possível inserir e remover elementos das duas pontas. Damos 3 implementações para uma deque persistente. A primeira é similar à implementação das pilhas e filas, usando a mesma técnica. A segunda tem o mesmo consumo de tempo que a primeira, apesar de ter mais casos a ser tratados. A terceira implementação é uma expansão da segunda, e melhora o tempo consumido por operação.
Árvore Rubro-Negra
Uma árvore rubro-negra é uma árvore de busca binária balanceada. A implementação é parcialmente persistente, e é feita usando o método de Node copying [1] . Por ser uma implementação parcialmente persistente, e como as cores dos nós servem apenas para auxiliar em seu balanceamento, estas não são armazenadas de forma persistente e conseguimos assim consumir espaço constante por operação de modificação.
Implementações Retroativas
Nestas implementações, apresentadas na Parte III, usamos que o tempo é indicado por um inteiro.
Fila
A fila é a estrutura mais simples de ser implementada de forma persistente. Para ser implementada desta forma, é preciso utilizar uma ED auxiliar que pode ser implementada com uma ABB.
