Binary search and binary search trees are fundamental concepts in computer science, both utilized for efficient searching and organization of data. Despite their similar nomenclature, they operate differently and are used in varied scenarios. In this article, we delve into the definitions, workings, applications, and contrasts between binary search and binary search trees.

Binary Search

Binary search is an efficient algorithm used to find a specific element within a sorted array or list. The key principle behind binary search is the divide-and-conquer strategy, which significantly reduces the time complexity compared to linear search.

How it Works:

1. Initial Setup: Begin with two pointers, `low` and `high`, marking the start and end of the list.
2. Finding the Midpoint: Calculate the midpoint, `mid = (low + high) / 2`.
3. Compare and Narrow Down:
   • If the element at `mid` is the target, the search is successful.
   • If the element at `mid` is greater than the target, continue the search in the lower half, adjusting `high = mid - 1`.
   • If the element at `mid` is less than the target, continue the search in the upper half, adjusting `low = mid + 1`.
4. Repeat: Continue the process until either the element is found or `low` exceeds `high`, indicating the element is not present.

Time Complexity:

• Best, Average, and Worst Case: $O(\log n)$.

Example:

Consider the sorted array `[1, 3, 5, 7, 9, 11]` and the target value `7`.

• First Iteration: `low = 0`, `high = 5`, `mid = (0 + 5) / 2 = 2`, element at `mid` is `5`.
• Second Iteration: Since `5 < 7`, adjust `low = 3`.
• Third Iteration: `mid = (3 + 5) / 2 = 4`, element at `mid` is `9`.
• Fourth Iteration: Since `9 > 7`, adjust `high = 3`.
• Fifth Iteration: `mid = (3 + 3) / 2 = 3`, element at `mid` is `7`. The target is found.

Binary Search Tree (BST)

A Binary Search Tree (BST) is a tree data structure where each node has at most two children referred to as the left and right child. For each parent node:

• The left child's key is less than the parent's key.
• The right child's key is greater than the parent's key.

Properties:

• Dynamic Structure: Unlike arrays, BSTs can dynamically adjust their size.
• In-Order Traversal: This traversal visits nodes in ascending order, which is useful for retrieving sorted data.
• Balance: Balanced trees, like AVL or Red-Black trees, help maintain $O(\log n)$ time complexity for operations.

Operations:

1. Insertion: Traverse down the tree starting from the root to find the appropriate leaf position, ensuring the BST property is maintained.
2. Deletion: More complex, involves three cases:
   • Node with no child (leaf node): Direct removal.
   • Node with one child: Replace the node with its child.
   • Node with two children: Find the in-order successor (smallest node in the right subtree) or in-order predecessor (largest node in the left subtree) to replace the node.
3. Search: Similar to insertion, traverse the tree based on comparisons to locate the desired key.

Time Complexity:

• Average: $O(\log n)$ for balanced trees; $O(n)$ for skewed trees (like linked lists).

Example:

Consider inserting the numbers `[5, 3, 7, 1, 4, 6, 8]` into a BST:

3 7 1 4 6 8

• Binary Search: Ideal for static datasets where the data doesn't change frequently and retrieval speed is paramount.
• Binary Search Tree: Suitable for dynamic datasets where insertions and deletions are prevalent alongside searching.
• AVL Trees: Automatically balance themselves after each insertion or deletion, maintaining a strict sorting order.
• Red-Black Trees: Guarantee $O(\log n)$ time complexity with a looser balancing condition than AVL trees, typically used for implementing associative arrays and priority queues.