Binary Search Trees (BSTs): Insertion, Deletion, and Searching
Binary Search Trees (BSTs) are a fundamental data structure in computer science, crucial for efficient searching, insertion, and deletion operations. They are a type of binary tree where each node has at most two children, referred to as the left child and the right child. The key property of a BST is that for any given node, 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 ordering allows for logarithmic time complexity for these operations on average.
Searching in a BST
Searching for a value in a BST is a straightforward process. Starting from the root, we compare the target value with the current node's value. If they match, we've found the value. If the target value is less than the current node's value, we move to the left child. If it's greater, we move to the right child. This process continues until the value is found or we reach a null node, indicating the value is not present in the tree.
For any node, 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.
Insertion into a BST
To insert a new value into a BST, we follow a similar logic to searching. We start at the root and compare the new value with the current node's value. If the new value is less than the current node, we move to the left child. If it's greater, we move to the right child. We continue this traversal until we reach an empty spot (a null child pointer), where we then insert the new node. If the tree is empty, the new value becomes the root.
Duplicate values are typically handled by either disallowing them or placing them in the right subtree (or left, consistently). For GATE CS, assume duplicates are handled by placing them in the right subtree unless specified otherwise.
Deletion from a BST
Deleting a node from a BST is the most complex operation, with three main cases:
- Node to be deleted is a leaf node (has no children): Simply remove the node.
- Node to be deleted has one child: Replace the node with its child.
- Node to be deleted has two children: This is the trickiest case. We find either the inorder successor (the smallest node in the right subtree) or the inorder predecessor (the largest node in the left subtree). We then replace the node to be deleted with its inorder successor (or predecessor) and then delete the inorder successor (or predecessor) from its original position. The inorder successor is guaranteed to have at most one child, simplifying its deletion.
Visualizing the deletion of a node with two children is key. Imagine replacing the node with its inorder successor. The inorder successor is the smallest value greater than the deleted node. It will always be found in the right subtree and will have no left child, making its removal straightforward.
Text-based content
Library pages focus on text content
Leaf node, node with one child, and node with two children.
Time Complexity
In a balanced BST, searching, insertion, and deletion operations have an average time complexity of O(log n), where 'n' is the number of nodes. However, in the worst-case scenario (e.g., a skewed tree resembling a linked list), these operations can degrade to O(n).
| Operation | Average Time Complexity | Worst-Case Time Complexity |
|---|---|---|
| Search | O(log n) | O(n) |
| Insertion | O(log n) | O(n) |
| Deletion | O(log n) | O(n) |
Learning Resources
A comprehensive explanation of BSTs, including their properties, operations, and C++ implementations.
Provides a clear explanation and visual examples of how to insert nodes into a Binary Search Tree.
Details the different cases of node deletion in a BST with illustrative examples.
A visual and intuitive explanation of BSTs, covering their structure and basic operations.
Focuses on the search operation in BSTs with interactive examples and explanations.
A detailed overview of binary search trees, their history, properties, and applications.
A blog post that breaks down the complexities of BST deletion with clear explanations and code snippets.
A lecture segment from a popular data structures course explaining BSTs and their operations.
An interactive visualization tool that allows you to see BST operations like insertion and deletion in action.
Official syllabus for GATE Computer Science, which includes Data Structures as a key topic.