Persistent Binary Search Trees and their Practical Applications
Ephemeral data structures retain only the most recent version of the data structures, while persistent data structures maintain a full history of the data structures. Fortunately, several methods can be employed to make any pointer-based ephemeral data structure persistent. This thesis aims to clarify and analyse classical approaches and apply them to the implementation of persistent binary search trees. Subsequently, we evaluate the efficiency of these approaches by conducting several benchmark tests. Furthermore, a partially persistent binary search tree is employed to address the traditional planar point location problem. This approach offers a solution with O(n) space cost, O(logn) query time, and O(nlogn) preprocessing time.