A Binary Search Tree (BST) is a specific type of binary tree that maintains a sorted order of its elements.
In a BST, the left child of a node contains elements smaller than the node, and the right child contains elements greater than the node.
This property holds for every node in the tree.
Binary Search Tree Implementation in Java
Here’s a basic Java implementation of a BST:
class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree {
Node root;
// Insert a Node
public void add(int data) {
root = addRecursive(root, data);
}
private Node addRecursive(Node current, int data) {
if (current == null) {
return new Node(data);
}
if (data < current.data) {
current.left = addRecursive(current.left, data);
} else if (data > current.data) {
current.right = addRecursive(current.right, data);
}
return current;
}
// Update a Node (Delete + Insert)
public void update(int oldData, int newData) {
delete(oldData);
add(newData);
}
// Delete a Node
public void delete(int data) {
root = deleteRecursive(root, data);
}
private Node deleteRecursive(Node current, int data) {
if (current == null) {
return null;
}
if (data == current.data) {
if (current.left == null && current.right == null) {
return null;
}
if (current.right == null) {
return current.left;
}
if (current.left == null) {
return current.right;
}
int smallestValue = findSmallestValue(current.right);
current.data = smallestValue;
current.right = deleteRecursive(current.right, smallestValue);
return current;
}
if (data < current.data) {
current.left = deleteRecursive(current.left, data);
return current;
}
current.right = deleteRecursive(current.right, data);
return current;
}
private int findSmallestValue(Node root) {
return root.left == null ? root.data : findSmallestValue(root.left);
}
// Search for a Node
public boolean search(int data) {
return searchRecursive(root, data) != null;
}
private Node searchRecursive(Node current, int data) {
if (current == null) {
return null;
}
if (data == current.data) {
return current;
}
return data < current.data ? searchRecursive(current.left, data) : searchRecursive(current.right, data);
}
public static void main(String[] args) {
BinaryTree bst = new BinaryTree();
bst.add(5);
bst.add(3);
bst.add(8);
bst.add(2);
bst.add(4);
bst.add(7);
bst.add(9);
// Updating node with data 7 to 6
bst.update(7, 6);
// Deleting node with data 2
bst.delete(2);
// Searching for node with data 4
boolean isFound = bst.search(4);
System.out.println("Is 4 found in the tree? " + isFound); // Output: true
}
}CRUD Operations in BST
- Create (Insertion):
- Operation: Inserts a new node into the BST while maintaining its properties.
- Method Name:
add(int data) - Average Time Complexity: O(logn)
- Worst-Case Time Complexity: O(n)
- Read (Search):
- Operation: Searches for a node with a specific value in the BST.
- Method Name:
search(int data) - Average Time Complexity: O(logn)
- Worst-Case Time Complexity: O(n)
- Update (Modification):
- Operation: Modifies the value of an existing node in the BST.
- Method Name:
update(int oldData, int newData) - Average Time Complexity: O(logn) for search + O(logn) for delete + O(logn) for insert =O(logn)
- Worst-Case Time Complexity: O(n)
- Delete (Removal):
- Operation: Removes a node with a specific value from the BST.
- Method Name:
delete(int data) - Average Time Complexity: O(logn)
- Worst-Case Time Complexity: O(n)
Notes on Time Complexity
- Average Case: Assumes that the tree is balanced, making the height of the tree logarithmic.
- Worst-Case: Assumes that the tree is skewed (either left or right), making the height of the tree linear.
These complexities are based on the height of the tree. For a balanced tree, these operations are quite efficient. However, it’s crucial to note that the tree can degenerate into a linked list in the worst-case scenario, leading to linear time operations. That’s why balanced trees like AVL or Red-Black trees are often preferred for maintaining logarithmic height.
Applications of BSTs
- Database Indexing: BSTs can speed up data retrieval operations.
- Dynamic Sorting: Allows efficient insertions, deletions, and look-ups.
- Range Queries: Efficient for range query operations.
- Balanced BSTs: Used in self-balancing trees like AVL or Red-Black trees.
Benefits of Using BSTs
- Sorted Data: Maintains data in sorted order, making in-order traversal efficient.
- Efficient Operations: Offers logarithmic performance for add, remove, and search operations.
- Flexibility: Easier to implement than sorted arrays or linked lists.
- Foundation for Advanced Trees: Concepts carry over to more advanced trees like AVL or Red-Black trees.