A Binary Search Tree is a data structure used in computer science for organizing and storing data in a sorted manner. Each node in a Binary Search Tree has at most two children, a left child and a right child, with the left child containing values less than the parent node and the right child containing values greater than the parent node. This hierarchical structure allows for efficient searching, insertion, and deletion operations on the data stored in the tree.
Binary search tree (BST) operations include insertion, deletion, and search.
Here’s a brief overview of each operation:
Insertion:
To insert a new node into a binary search tree, you start at the root and compare the value of the new node with the value of the current node. If the new node’s value is less than the current node’s value, you move to the left child. If it’s greater, you move to the right child. You continue this process recursively until you find an empty spot where you can insert the new node.
Here’s a Java program to implement optimized insertion in a Binary Search Tree (BST):
class Node {
int key;
Node left, right;
public Node(int item) {
key = item;
left = right = null;
}
}
public class BalancedBST {
Node root;
BalancedBST() {
root = null;
}
// Utility function to insert a new node with a given key
// into the BST
Node insertRec(Node root, int key) {
// If the tree is empty, return a new node
if (root == null) {
root = new Node(key);
return root;
}
// Otherwise, recur down the tree
if (key < root.key)
root.left = insertRec(root.left, key);
else if (key > root.key)
root.right = insertRec(root.right, key);
// return the (unchanged) node pointer
return root;
}
// Method to insert a new key into the BST
void insert(int key) {
root = insertRec(root, key);
}
// Utility function to do inorder traversal of BST
void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.print(root.key + " ");
inorderRec(root.right);
}
}
// Method to do inorder traversal of BST
void inorder() {
inorderRec(root);
}
public static void main(String[] args) {
BalancedBST tree = new BalancedBST();
/* Constructing tree given in the above figure */
tree.insert(10);
tree.insert(20);
tree.insert(30);
tree.insert(40);
tree.insert(50);
tree.insert(25);
/* The constructed AVL Tree would be
30
/ \
20 40
/ \ \
10 25 50
*/
System.out.println("Inorder traversal of constructed BST is : ");
tree.inorder();
}
}
Deletion:
Deleting a node from a binary search tree can be a bit more complex than insertion. There are different cases to consider:
- If the node to be deleted is a leaf node (has no children), you can simply remove it.
- If the node to be deleted has one child, you can replace the node with its child.
- If the node to be deleted has two children, you can either replace it with the maximum node in its left subtree or the minimum node in its right subtree. After replacing, you need to remove the duplicate node from the subtree.
Below is a Java program implementing optimized deletion in a binary search tree (BST):
class Node {
int key;
Node left, right;
public Node(int item) {
key = item;
left = right = null;
}
}
public class BinarySearchTree {
Node root;
BinarySearchTree() {
root = null;
}
// Function to insert a new key
void insert(int key) {
root = insertRec(root, key);
}
// A recursive function to insert a new key in BST
Node insertRec(Node root, int key) {
if (root == null) {
root = new Node(key);
return root;
}
if (key < root.key)
root.left = insertRec(root.left, key);
else if (key > root.key)
root.right = insertRec(root.right, key);
return root;
}
// Function to delete a key from BST
void deleteKey(int key) {
root = deleteRec(root, key);
}
// A recursive function to delete a key in BST
Node deleteRec(Node root, int key) {
if (root == null)
return root;
// If the key to be deleted is smaller than the root's key,
// then it lies in the left subtree
if (key < root.key)
root.left = deleteRec(root.left, key);
// If the key to be deleted is greater than the root's key,
// then it lies in the right subtree
else if (key > root.key)
root.right = deleteRec(root.right, key);
// If key is the same as root's key, then this is the node to be deleted
else {
// Node with only one child or no child
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
// Node with two children: Get the inorder successor (smallest in the right subtree)
root.key = minValue(root.right);
// Delete the inorder successor
root.right = deleteRec(root.right, root.key);
}
return root;
}
int minValue(Node root) {
int minv = root.key;
while (root.left != null) {
minv = root.left.key;
root = root.left;
}
return minv;
}
// Function to do inorder traversal of BST
void inorder() {
inorderRec(root);
}
// A utility function to do inorder traversal of BST
void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.print(root.key + " ");
inorderRec(root.right);
}
}
// Main method to test the BST operations
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
// Inserting nodes
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
System.out.println("Inorder traversal of the given tree:");
tree.inorder();
System.out.println("\n\nDelete 20");
tree.deleteKey(20);
System.out.println("Inorder traversal after deletion of 20:");
tree.inorder();
System.out.println("\n\nDelete 30");
tree.deleteKey(30);
System.out.println("Inorder traversal after deletion of 30:");
tree.inorder();
System.out.println("\n\nDelete 50");
tree.deleteKey(50);
System.out.println("Inorder traversal after deletion of 50:");
tree.inorder();
}
}
Search:
Searching for a value in a binary search tree is straightforward. You start at the root and compare the value you’re searching for with the value of the current node. If they match, you’ve found the node. If the value is less than the current node’s value, you move to the left child. If it’s greater, you move to the right child. You continue this process recursively until you find the node with the matching value or you reach a leaf node (indicating that the value is not in the tree).
Below is a Java program to implement optimized searching in a Binary Search Tree (BST):
// Node class representing a node in the BST
class Node {
int key;
Node left, right;
public Node(int item) {
key = item;
left = right = null;
}
}
// BST class containing methods for insertion and searching
class BST {
Node root;
public BST() {
root = null;
}
// Method to insert a key into the BST
void insert(int key) {
root = insertRec(root, key);
}
// Recursive helper method to insert a key into the BST
Node insertRec(Node root, int key) {
// If the tree is empty, create a new node and return it
if (root == null) {
root = new Node(key);
return root;
}
// Otherwise, recur down the tree
if (key < root.key)
root.left = insertRec(root.left, key);
else if (key > root.key)
root.right = insertRec(root.right, key);
// Return the unchanged node pointer
return root;
}
// Method to search for a key in the BST
boolean search(int key) {
return searchRec(root, key);
}
// Recursive helper method to search for a key in the BST
boolean searchRec(Node root, int key) {
// Base cases: root is null or key is present at root
if (root == null || root.key == key)
return root != null;
// Key is greater than root's key
if (root.key < key)
return searchRec(root.right, key);
// Key is smaller than root's key
return searchRec(root.left, key);
}
}
// Main class to test the BST implementation
public class Main {
public static void main(String[] args) {
BST bst = new BST();
// Insert elements into the BST
bst.insert(50);
bst.insert(30);
bst.insert(20);
bst.insert(40);
bst.insert(70);
bst.insert(60);
bst.insert(80);
// Search for elements in the BST
System.out.println("Searching for 20: " + bst.search(20));
System.out.println("Searching for 90: " + bst.search(90));
}
}
