Chapter 24 Further Reading: Trees and Graphs

Books

  • Wirth, N. (1976). Algorithms + Data Structures = Programs. Prentice-Hall. Chapters 4-5 cover trees and graphs in Pascal with Wirth's characteristic precision. The BST implementation in this chapter follows Wirth's approach.

  • Sedgewick, R. (2011). Algorithms, 4th ed. Addison-Wesley. Chapters 3-4 cover BSTs, balanced trees (red-black), and graph algorithms with excellent visualizations.

  • Cormen, T. H., et al. (2022). Introduction to Algorithms, 4th ed. MIT Press. Chapters 12-13 cover BSTs and red-black trees; Chapters 22-25 cover graph algorithms including BFS, DFS, Dijkstra, and more advanced topics.

  • Skiena, S. S. (2020). The Algorithm Design Manual, 3rd ed. Springer. An approachable guide that emphasizes practical algorithm design with extensive "war stories" from real applications.

Online Resources

  • Visualgo: BST and Graph Visualizations. visualgo.net. Interactive animations for BST operations, graph traversals, and shortest-path algorithms.

  • Free Pascal AVL Tree Documentation. The AVL_Tree unit provides a production-ready balanced BST implementation. Consult the Free Pascal documentation for usage.

Historical Context

  • Dijkstra, E. W. (1959). "A Note on Two Problems in Connexion with Graphs." Numerische Mathematik 1(1), 269-271. The original two-page paper introducing Dijkstra's shortest-path algorithm. Remarkably concise.

  • Adelson-Velsky, G. M. & Landis, E. M. (1962). "An Algorithm for the Organization of Information." Proceedings of the USSR Academy of Sciences 146, 263-266. The original AVL tree paper, introducing the first self-balancing BST.

Topics for Further Exploration

  • Red-Black Trees: An alternative to AVL trees with slightly relaxed balance requirements but simpler rotations. Used in Java's TreeMap and C++'s std::map.

  • B-Trees: Multi-way search trees designed for disk-based storage. The foundation of database indexes and file systems.

  • Minimum Spanning Trees: Prim's and Kruskal's algorithms find the cheapest way to connect all vertices in a weighted graph. Applications in network design and clustering.

  • A* Search: An extension of Dijkstra's algorithm that uses a heuristic to guide the search toward the goal. Widely used in game AI and robotics for pathfinding.

  • Network Flow: Max-flow/min-cut algorithms solve problems in transportation, matching, and resource allocation. A deep topic in graph theory with broad applications.