##

###

##
3. Searching Algorithms
###

- Sequential search
####

- Basic sequential search
- Self-organizing sequential search:
move-to-front method
- Self-organizing sequential search:
transpose method
- Optimal sequential search
- Jump search

- Sorted array search
####

- Binary search
- Interpolation search
- Interpolation-sequential search

- Hashing
####

- Practical hashing functions
- Uniform probing hashing
- Random probing hashing
- Linear probing hashing
- Double hashing
- Quadratic hashing
- Ordered and split-sequence hashing
- Reorganization schemes
#####

- Brent's algorithm
- Binary tree hashing
- Last-come-first-served hashing
- Robin Hood hashing
- Self-adjusting hashing

- Optimal hashing
- Direct chaining hashing
- Separate chaining hashing
- Coalesced hashing
- Extendible hashing
- Linear hashing
- External hashing using minimal internal storage
- Perfect hashing
- Summary

- Recursive structures search
####

- Binary tree search
#####

- Randomly generated binary trees
- Random binary trees
- Height-balanced trees
- Weight-balanced trees
- Balancing by internal path reduction
- Heuristic organization schemes on binary trees
- Optimal binary tree search
- Rotations in binary trees
- Deletions in binary trees (see Weight-balanced trees)
- m-ary search trees

- B-trees
#####

- 2-3 trees
- Symmetric binary B-trees
- 1-2 trees
- 2-3-4 trees
- B-tree variations

- Index and indexed sequential files
#####

- Index sequential access method

- Digital trees
#####

- Hybrid tries
- Tries for word-dictionaries
- Digital search trees
- Compressed tries
- Patricia trees

- Multidimensional search
####

- Quad trees
#####

- Quad tries

- K-dimensional trees

####