Algorithm Chapter 3 Searching Notes, Polytechnic 3rd Sem Algorithm Notes

3. Searching

Searching is a fundamental operation in computer science where we aim to locate a specific element within a collection of elements (like an array, list, or database). Efficient search algorithms are crucial for managing large datasets and ensuring fast access to data. There are various data structures that aid in performing search operations, each with its unique properties and advantages.

3.1. Symbol Tables

A Symbol Table is a data structure used to store and retrieve key-value pairs efficiently. Symbol tables are widely used in compilers, databases, and other systems where associations between keys (such as variable names, words, or items) and their values (like memory locations, definitions, or data) are required.

Key Operations of a Symbol Table:

1. Insert (put): Inserts a key-value pair into the table.
2. Search (get): Retrieves the value associated with a given key.
3. Delete: Removes a key-value pair from the table.
4. Update: Modifies the value associated with a given key.

Types of Symbol Tables:

• Unordered Symbol Tables: No specific order is maintained between the keys. The search operation is often slower due to linear search requirements.
• Ordered Symbol Tables: Keys are stored in a specific order (e.g., sorted by value), making search operations faster using binary search.

Applications of Symbol Tables:

• Compilers: Used to store variables, functions, and constants during the compilation process.
• Databases: To store and manage records using key-value pairings.

Symbol tables can be implemented using various data structures like arrays, linked lists, binary search trees, or hash tables, depending on the need for fast insertions, deletions, and lookups.

3.2. Binary Search Trees (BSTs)

A Binary Search Tree (BST) is a binary tree-based data structure that stores elements (usually keys or key-value pairs) in such a way that for every node:

• The left subtree contains values less than the node’s key.
• The right subtree contains values greater than the node’s key.

Properties of a Binary Search Tree:

• Search: The search operation in a BST can be performed in $O(h)$ time, where $h$ is the height of the tree. In a balanced BST, the height is $O(\log n)$, leading to efficient searching.
• Insertion and Deletion: Like search, insertion and deletion in a BST are also $O(h)$ operations. They require the tree to maintain its structure by inserting/deleting nodes in such a way that the binary search property holds.

Example of BST:

Consider the following binary search tree:

markdown

        15
       /  \
      10  20
     /  \   \
    5   13  25

• Search for 13: Start at the root (15), move left (10), then right (13). Found.
• Insert 17: Start at the root (15), move right (20), and insert 17 in the left subtree of 20.

Advantages of BSTs:

• Sorted Data: The in-order traversal of a BST gives elements in a sorted order.
• Dynamic Set Operations: Insertion and deletion can be performed efficiently while maintaining the sorted property.

Drawbacks of BSTs:

• If the tree becomes unbalanced (i.e., skewed), the performance can degrade to $O(n)$ for search, insertion, and deletion. To overcome this, balanced search trees are used.

3.3. Balanced Search Trees

A Balanced Search Tree is a variation of the binary search tree that ensures the tree remains balanced, i.e., the height of the tree is kept as small as possible relative to the number of nodes. This balancing ensures that search, insertion, and deletion operations can all be performed in $O(\log n)$ time.

Types of Balanced Search Trees:

1. AVL Trees: An AVL tree is a self-balancing binary search tree where the difference in height between the left and right subtrees (called the balance factor) is at most 1 for every node.

   • Rotation: To maintain balance, AVL trees use rotations (left or right) during insertions or deletions.
   • Time Complexity: $O(\log n)$ for search, insertion, and deletion.

2. Red-Black Trees: Another self-balancing binary search tree where nodes are colored red or black, and the tree is balanced based on specific rules about node colors and their relationships.

   • The tree's height is maintained as approximately $\log n$.
   • Advantages: Red-black trees are used in many libraries because they are easier to implement than AVL trees and maintain relatively good balance.

3. 2-3 Trees: A 2-3 tree is a balanced search tree where each node has either 2 or 3 children. It is always perfectly balanced, meaning all leaf nodes are at the same level.

   • Advantages: 2-3 trees provide excellent balance, making searches, insertions, and deletions uniformly fast.

Advantages of Balanced Search Trees:

• Fast Access: Since the tree remains balanced, search, insertion, and deletion operations are all guaranteed to run in $O(\log n)$.
• Efficient Sorting: As with regular BSTs, in-order traversal of balanced trees provides sorted data.

Applications of Balanced Search Trees:

• Databases: Balanced search trees are used in database indexing to allow for fast searching and retrieval of records.
• File Systems: Many file systems use balanced trees (like B-trees) to manage and locate files efficiently.

3.4. Hash Tables

A Hash Table is a data structure that maps keys to values using a hash function. A hash function takes an input (the key) and returns an index (the hash) that corresponds to the position in an array where the value associated with the key is stored.

Operations in Hash Tables:

1. Insert (put): A key-value pair is inserted by computing the hash of the key and placing the value at the corresponding index in the table.
2. Search (get): The key is hashed, and the value stored at the corresponding index is returned.
3. Delete: The key is hashed, and the entry at the computed index is removed from the table.

Example of Hash Table:

If we have the following keys: 12, 44, 13, and 88, and the hash function is $h(x) = x \% 10$, the hash table would look like this:

Index   Value
  0     10
  1     
  2     12
  3     13
  4     44
  5     
  6     
  7     
  8     88
  9     

Collisions in Hash Tables:

A collision occurs when two keys hash to the same index. Hash tables resolve collisions using different techniques:

1. Chaining: Store multiple key-value pairs at the same index using a linked list.
2. Open Addressing: When a collision occurs, search for the next available index in the table. Common open addressing techniques include:
   • Linear Probing: If a collision occurs at index $i$, try $i+1, i+2, \dots$ until an open slot is found.
   • Quadratic Probing: Instead of probing linearly, this method probes at intervals that grow quadratically (e.g., $i+1, i+4, i+9, \dots$).
   • Double Hashing: Use a second hash function to compute the probe sequence.

Time Complexity of Hash Tables:

• Average case: $O(1)$ for insert, search, and delete operations if the hash function distributes keys uniformly and collisions are minimal.
• Worst case: $O(n)$, which can occur if all keys collide and are stored in the same bucket.

Advantages of Hash Tables:

• Fast Lookup: Hash tables provide constant-time complexity on average for search, insert, and delete operations.
• Flexible Data Storage: Hash tables can store and retrieve both numerical and non-numerical data, as long as a proper hash function is defined.

Disadvantages of Hash Tables:

• Collisions: When too many collisions occur, the performance can degrade significantly.
• Space Complexity: Hash tables can be space-inefficient if the table size is much larger than the number of keys.

Applications of Hash Tables:

• Databases: Hash tables are used to implement hash-based indexing for fast data retrieval.
• Compilers: Symbol tables in compilers are often implemented as hash tables for quick lookup of variables and functions.
• Caching: Hash tables are frequently used in caching mechanisms to quickly access previously computed results.

---

Each of these data structures—symbol tables, binary search trees, balanced search trees, and hash tables—plays a crucial role in optimizing search operations across various applications, from database indexing to network routing. The choice of which structure to use depends on the specific requirements for speed, memory usage, and the nature of the data being managed.