15. Trees and associative data structures

This section introduces what the standard library refers to as "associative data structures" - non-sequential data structures.

• 15.1. Tree ADT concepts
  • 15.1.1. The tree ADT
• 15.2. Binary Search Trees
  • 15.2.1. The Binary Search Tree ADT
  • 15.2.2. Searching binary trees
  • 15.2.3. Inserting into binary trees
  • 15.2.4. Erasing binary tree nodes
• 15.3. Binary Search Tree iterators
  • 15.3.1. BST iterator begin() and end()
  • 15.3.2. BST iterator operator++()
  • 15.3.3. Implementing BST iterators
• 15.4. Using parent pointers
• 15.5. Priority queues
  • 15.5.1. Heaps
  • 15.5.2. Percolate up
  • 15.5.3. Percolate down
• 15.6. The set class
  • 15.6.1. Variations on std::set
• 15.7. The map class
  • 15.7.1. Selected map functions
  • 15.7.2. Map structure
  • 15.7.3. Variations on std::map