[Home]

[Previous Chapter]

[Next Chapter]


3. Searching Algorithms

  1. Sequential search

    1. Basic sequential search
    2. Self-organizing sequential search: move-to-front method
    3. Self-organizing sequential search: transpose method
    4. Optimal sequential search
    5. Jump search

  2. Sorted array search

    1. Binary search
    2. Interpolation search
    3. Interpolation-sequential search

  3. Hashing

    1. Practical hashing functions
    2. Uniform probing hashing
    3. Random probing hashing
    4. Linear probing hashing
    5. Double hashing
    6. Quadratic hashing
    7. Ordered and split-sequence hashing
    8. Reorganization schemes
      1. Brent's algorithm
      2. Binary tree hashing
      3. Last-come-first-served hashing
      4. Robin Hood hashing
      5. Self-adjusting hashing
    9. Optimal hashing
    10. Direct chaining hashing
    11. Separate chaining hashing
    12. Coalesced hashing
    13. Extendible hashing
    14. Linear hashing
    15. External hashing using minimal internal storage
    16. Perfect hashing
    17. Summary

  4. Recursive structures search

    1. Binary tree search
      1. Randomly generated binary trees
      2. Random binary trees
      3. Height-balanced trees
      4. Weight-balanced trees
      5. Balancing by internal path reduction
      6. Heuristic organization schemes on binary trees
      7. Optimal binary tree search
      8. Rotations in binary trees
      9. Deletions in binary trees (see Weight-balanced trees)
      10. m-ary search trees
    2. B-trees
      1. 2-3 trees
      2. Symmetric binary B-trees
      3. 1-2 trees
      4. 2-3-4 trees
      5. B-tree variations
    3. Index and indexed sequential files
      1. Index sequential access method
    4. Digital trees
      1. Hybrid tries
      2. Tries for word-dictionaries
      3. Digital search trees
      4. Compressed tries
      5. Patricia trees

  5. Multidimensional search

    1. Quad trees
      1. Quad tries
    2. K-dimensional trees



© Addison-Wesley Publishing Co. Inc.