What are the thresholds where the complicated solution is superior to the rollback solution?

In this portfolio project, retroactive search trees will be
implemented – both partially and fully retroactive search trees. The
update operations to the (non-retroactive) search tree should be
Insert(x) and Delete(x), and the query operation should be Pred(x) that
returns the largest element stored in the subtree ≤x. The tasks of the
project are to:
Define an appropriate interface to a partially and a fully retroactive search tree.
Implement a search tree, a partially retroactive search tree, and a fully retroactive search tree.
Test if your retroactive solutions are correct by comparing them with simple rollback solutions.
Compare the performance of the different data structures. Compare the
performance of the fully retroactive search tree with a simple rollback
solution. What are the thresholds where the complicated solution is
superior to the rollback solution?
You will present your findings in a well-organized research paper
that resembles the structure of a manuscript for publication in a
computer science journal.

Last Completed Projects