Home

This is the Wiki for the open data structures project. It currently acts mainly as a to-do list for future editions of the book.

Advanced Topics

The following is a list of advanced topics I would like to include in Part II of the book

• Biased search trees

  • Entropy and the entropy lower bound
  • Mehlhorn's construction
  • Biased treaps
  • Big literature review section

• Splay trees

  • Access lemma
  • Uniform access theorem
  • Static tree optimality result
    • Uniform access theorem
    • Static optimality theorem
    • Static finger theorem
  • Working-set theorem

• Data structures for strings

  • Null-terminated versus pointer/length representation
  • Ropes/cords
  • Tries
  • PATRICIA trees
  • Suffix trees
  • Suffix arrays
    • Karkainnen and Sanders O(n) time construction algorithm
    • Kasai et al's O(n) LCP array construction algorithm
  • Linear-time construction of suffix trees
  • Ternary trees and string quicksort

• Fractional cascading

  • Iterated search
  • Application: Half-plane range searching

• Persistence

  • Path copying (with treaps as an example)
  • Persistent graphs
  • Application: Planar point location

• Multidimensional searching

  • k-d trees
  • Range trees
  • Quad trees

Topic Requests

If you have a request for a specific topic that you would like to see included in an upcoming version of the book, you can request it here. Be sure to add your name so that the author has some idea of how popular this request is.

• Graham's scan as an application of stacks and deques - requested by Pat Morin
• Plane sweep as an application of priority queues and dictionaries - requested by Pat Morin
• Quadtrees and Kd-trees - requested by [Dan Minor] (https://github.com/dminor) and [Darcy Quesnel] (https://github.com/dlq)
• Union-find structures - requested by Kevin Wortman
• Bloom filters - requested by Kevin Wortman

Clarification Requests

If you feel that some section of the book is not precise enough, or leaves too much to the reader, add a clarification request here. Please be as specific as possible:

• Implementation of AVL trees (example) - requested by Pat Morin

Errata

If you would like to point out, and possibly correct, an error in the book, you can do so here. You should also consider reporting an issue.

• Author's name is misspelled in the title page (example)
• List implementations that support random access should implement the RandomAccess marker interface (Java version)