\documentclass{article} \usepackage{me} \setlength{\parindent}{0pt}
This material takes 1 hour.

Persistent Data Structures

Sarnak and Tarjan, "Planar Point Location using persistent trees", Communications of the ACM 29 (1986) 669--679

"Making Data Structures Persistent" by Driscoll, Sarnak, Sleator and Tarjan Journal of Computer and System Sciences 38(1) 1989

Idea: be able to query and/or modify past versions of data structure.

Goal: general technique that can be applied to any data structure.

Persistent Trees

Many data structures

Our goal: use simulation to transform any ephemeral data structure into a persistent one

Key principles:

Lazy approach:


Full copy bad.

Fat nodes method:

Path copying:

Combined Solution (trees only):

Analysis idea: adversary has to do many changes to make copying expensive.



remind about hash table survey

Talk about splay tree inserts and deletes

Make point about all at once

Remind about $O(1)$ persistent pointer changes

Application: planar point location.

Persistent sorted sets:

Method: persistent red-black trees

Red black trees

Add persistence


Result: $O(n)$ space, $O(\log n)$ query time for planar point location.