A Textbook of Data Structures and Algorithms, Volume 1

Summary of Volume 3

1. Preface
2. Acknowledgments
3. Chapter 13. Hash Tables
   1. 13.1. Introduction
      1. 13.1.1. Dictionaries
   2. 13.2. Hash table structure
   3. 13.3. Hash functions
      1. 13.3.1. Building hash functions
   4. 13.4. Linear open addressing
      1. 13.4.1. Operations on linear open addressed hash tables
      2. 13.4.2. Performance analysis
      3. 13.4.3. Other collision resolution techniques with open addressing
   5. 13.5. Chaining
      1. 13.5.1. Operations on chained hash tables
      2. 13.5.2. Performance analysis
   6. 13.6. Applications
      1. 13.6.1. Representation of a keyword table in a compiler
      2. 13.6.2. Hash tables in the evaluation of a join operation on relational databases
      3. 13.6.3. Hash tables in a direct file organization
   7. 13.7. Illustrative problems
4. Chapter 14. File Organizations
   1. 14.1. Introduction
   2. 14.2. Files
   3. 14.3. Keys
   4. 14.4. Basic file operations
   5. 14.5. Heap or pile organization
      1. 14.5.1. Insert, delete and update operations
   6. 14.6. Sequential file organization
      1. 14.6.1. Insert, delete and update operations
      2. 14.6.2. Making use of overflow blocks
   7. 14.7. Indexed sequential file organization
      1. 14.7.1. Structure of the ISAM files
      2. 14.7.2. Insert, delete and update operations for a naïve ISAM file
      3. 14.7.3. Types of indexing
   8. 14.8. Direct file organization
   9. 14.9. Illustrative problems
5. Chapter 15. k-d Trees and Treaps
   1. 15.1. Introduction
   2. 15.2. k-d trees: structure and operations
      1. 15.2.1. Construction of a k-d tree
      2. 15.2.2. Insert operation on k-d trees
      3. 15.2.3. Find minimum operation on k-d trees
      4. 15.2.4. Delete operation on k-d trees
      5. 15.2.5. Complexity ...