A Binary Search Tree (BST) is a specialized hierarchical data structure where each node has at most two children, referred to as the left child and the right child. In a BST, the value of each node is greater than all values in its left subtree and less than all values in its right subtree. This property makes BSTs highly efficient for search, insertion, and deletion operations.
Core Characteristics
- Each node has at most two children: left and right
- Values in the left subtree are less than the node's value
- Values in the right subtree are greater than the node's value
- Efficient for search, insertion, and deletion operations
Key Operations
-
Insert() This operation adds a new node to the binary search tree. The node is placed in the correct position based on its value, ensuring the BST property is maintained. Complexity: O(log n) - Logarithmic time operation
-
Delete() This operation removes a node from the binary search tree. There are three cases: deleting a leaf node, deleting a node with one child, and deleting a node with two children. The BST property must be preserved after deletion. Complexity: O(log n) - Logarithmic time operation
-
Search() This operation finds a node with a specific value in the binary search tree. It starts at the root and recursively compares the target value with the current node, moving left or right based on the comparison. Complexity: O(log n) - Logarithmic time operation
-
Depth-First Search (DFS)() This operation visits all nodes in the binary search tree by exploring as far as possible along each branch before backtracking. This includes: - In-order Traversal: Visits nodes in the order of left, root, right. Commonly used to retrieve nodes in non-decreasing order. - Pre-order Traversal: Visits nodes in the order of root, left, right. Useful for creating a copy of the tree. - Post-order Traversal: Visits nodes in the order of left, right, root. Often used to delete the tree. . Complexity: O(n) - Linear time operation
-
Breadth-First Search (BFS)() This operation visits all nodes in the binary search tree level by level, starting from the root. This traversal method is useful for creating a level-order traversal of the tree and is often used in scenarios where the shortest path is required.. Complexity: O(n) - Linear time operation
Common Applications
- Efficient searching, insertion, and deletion operations
- Used in applications requiring dynamic data storage
- Ideal for implementing associative arrays and priority queues
- Commonly used in database indexing and memory management