Search, Insertion, and Deletion Operations in a Binary Search Tree (BST)

Search, Insertion, and Deletion Operations in a Binary Search Tree (BST)

A Binary Search Tree is a special type of binary tree that satisfies the following property: for any node in the tree, all values in its left subtree are less than the node's value, and all values in its right subtree are greater than the node's value. This property makes Binary Search Trees highly efficient for search, insertion, and deletion operations.

1. Search Operation

Goal: Find a specific value within the Binary Search Tree.
Process: Utilizing the BST property, we can quickly narrow down the search scope.
1. Start from the root node: Compare the target value with the root node's value.
2. If they are equal: Congratulations, the search is successful.
3. If the target value is less than the root node's value: This indicates the target value can only exist in the root's left subtree (if it exists). Therefore, we recursively continue the search in the left subtree.
4. If the target value is greater than the root node's value: This indicates the target value can only exist in the root's right subtree. Therefore, we recursively continue the search in the right subtree.
5. Encountering a null node: If during the search, based on the comparison result, we need to proceed to a child node, but that child node is empty (null), it means the value we are looking for does not exist in the tree, and the search fails.
Example: Searching for the value 8 in the BST shown in the diagram below.
```
      10
    /    \
   5      15
  / \    /  \
 3   7  12  18
    /
   8
```
- Start from the root node 10. Since 8 < 10, go to the left subtree.
- The current node is 5. Since 8 > 5, go to the right subtree.
- The current node is 7. Since 8 > 7, go to the right subtree.
- The current node is 8. They are equal, the search is successful.

2. Insertion Operation

Goal: Insert a new value that does not exist in the tree into the correct position in the BST while maintaining the BST property.
Process: The insertion operation is very similar to the search operation. First, we must find the position where the new node should be placed. This position is necessarily an empty child node location of some leaf node.
1. Start comparing from the root node: Compare the new node's value with the current node.
2. If the new value is less than the current node's value:
  - If the current node's left child is empty, insert the new node as the left child.
  - If the left child is not empty, recursively perform the insertion operation in the left subtree.
3. If the new value is greater than the current node's value:
  - If the current node's right child is empty, insert the new node as the right child.
  - If the right child is not empty, recursively perform the insertion operation in the right subtree.
4. Note: If the new value equals the current node's value, depending on the specific implementation, one can choose to disallow duplicate values (ignore the insertion) or insert the new node as the right child (or left child), etc. Typically, BSTs do not contain duplicate values.
Example: Insert 10, 5, 15, 3, 7, 12, 18, 8 sequentially into an empty tree. The final tree formed is the one shown in the example above.

3. Deletion Operation

Goal: Remove a specified node from the BST while maintaining the BST property. This is the most complex of the three operations because the node to be deleted may have zero, one, or two children. We need to discuss three cases.
Process:
1. Locate the node to delete: First, use the search algorithm to find the node to be deleted, denoted as node.
2. Handle based on the number of children of node:
  - Case 1: node is a leaf node (has no children)
    - This is the simplest case. Simply set the pointer from its parent node to null.
    - Example: Delete node 3. Just set the left pointer of node 5 to null.
  - Case 2: node has only one child
    - Make node's parent node bypass node and point directly to node's only child.
    - Example: Delete node 7 (which has a left child 8).
      - Find the parent node of 7, which is 5.
      - Change 5's right pointer (originally pointing to 7) to point to 7's left child 8.
      - This way, node 7 is removed from the tree, and its child 8 takes its place.
  - Case 3: node has two children
    - This is the most complex case. We cannot simply delete it because two subtrees would need to be reconnected. Our strategy is:
      a. Find a replacement: In node's right subtree, find the node with the minimum value (this node is called node's in-order successor). According to the BST property, this node is the smallest node greater than node's value. Alternatively, you can choose the node with the maximum value in node's left subtree (in-order predecessor).
      b. Copy the value: Copy the value of this found successor node (or predecessor node) into node, overwriting node's original value.
      c. Delete the successor node: Now, the problem transforms into deleting that successor node (or predecessor node). This node has at most one child (because it is the minimum node in the right subtree, so it cannot have a left child; similarly, the maximum node in the left subtree cannot have a right child). This brings us back to Case 1 or Case 2, allowing us to delete it easily.
    - Example: Delete the root node 10.
      - Node 10 has two children.
      - Find the node with the minimum value in its right subtree (rooted at 15). This node is 12 (it has no left child).
      - Replace the value of 10 with 12.
      - Now, there are two 12s in the original tree. We need to delete the original 12 in the right subtree. This node has only one right child (or none, as in this example). Delete it according to Case 2. Finally, the tree structure still satisfies the BST property.

By mastering the three core operations of search, insertion, and deletion, you have grasped the fundamental working principles of a Binary Search Tree. The average time complexity of these operations is O(log n), where n is the number of nodes in the tree, making BST a very practical data structure.