Persistent BST: path copying

Idea:
  • share as much structure as possible
  • e.g. if we insert a new node, we also need to add a new version of its parent (it has a new child), and a new version of its grand-parent (it has a new grand-child), etc. — we need to add a new version of every ancestor
  • however, a change only happens in one subtree; the other subtree is unchanged ⇒ it can be shared
Advantages:
  • conceptually simple — no bookkeeping beyond the copies; queries in any version run like in a plain BST
  • fully functional style: versions are immutable values
Disadvantages:
  • each update adds \(O(h)\) new nodes (this may be \(O(\log n)\) if using a balanced tree)

References

  • J.R. Driscoll, N. Sarnak, D.D. Sleator, R.E. Tarjan. Making data structures persistent. Journal of Computer and System Sciences, 38(1):86-124, 1989.