Data Structures

• To some extent, all data structures are just graphs in some manner with additional constraints and invariants.

Set-Based Data Structures §

Graph-Based §

• Graphs
  • Trails, Walks, Paths and Cycles
• Tree-based:
  • Binary Search Tree
  • Heap Data Structure
  • B Tree
  • Trie

Augmented §

• In general, data structures can be augmented beyond their original use case if their structure and operations can help solve another problem with more data.

  Augmenting follows these general steps

  • Choose a data structure
  • Determine additional information to maintain in the underlying data structure
  • Verify that we can maintain the additional information for the basic modifying operations on the underlying data structure.
  • Develop new operations.

• While the steps are outlined above, it is important to note that designing may not follow these steps.

Links §

• Cormen, Leiserson, Rivest, and Stein - Part III.
• Algorithms