WikiGalaxy
Binary Search Tree Basics
Definition:
A Binary Search Tree (BST) is a node-based binary tree data structure where each node has at most two children referred to as the left child and the right child. For each node, the left subtree contains only nodes with keys lesser than the node's key, and the right subtree contains only nodes with keys greater than the node's key.
class Node {
int key;
Node left, right;
public Node(int item) {
key = item;
left = right = null;
}
}
public class BinarySearchTree {
Node root;
BinarySearchTree() {
root = null;
}
void insert(int key) {
root = insertRec(root, key);
}
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;
}
}
Insertion:
Inserting a new key into a BST involves comparing the key with the root node's key and recursively inserting it into the left or right subtree, maintaining the BST property.
Searching in a BST
Search Operation:
Searching for a key in a BST is efficient due to its sorted nature. The search operation compares the key with the current node's key to decide whether to continue the search in the left or right subtree.
Node search(Node root, int key) {
if (root == null || root.key == key)
return root;
if (root.key > key)
return search(root.left, key);
return search(root.right, key);
}
Efficiency:
The time complexity for searching in a BST is O(h), where h is the height of the tree. In the best case, the height is log(n), making the search operation very efficient.
Deleting a Node
Deletion Process:
Deleting a node from a BST involves three main scenarios: deleting a leaf node, deleting a node with one child, and deleting a node with two children. Each scenario requires different handling to maintain the BST properties.
Node deleteRec(Node root, int key) {
if (root == null) return root;
if (key < root.key)
root.left = deleteRec(root.left, key);
else if (key > root.key)
root.right = deleteRec(root.right, key);
else {
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
root.key = minValue(root.right);
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;
}
Complexity:
The deletion operation also has a time complexity of O(h), where h is the height of the tree. Proper balancing of the tree can help maintain an optimal height.
Inorder Traversal
Traversal Method:
Inorder traversal of a BST results in the nodes being visited in ascending order. This traversal method is useful for retrieving data from a BST in a sorted manner.
void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.print(root.key + " ");
inorderRec(root.right);
}
}
Use Case:
Inorder traversal is particularly useful when you need to output the contents of a BST in a sorted sequence.
Balancing a BST
Importance of Balance:
A balanced BST ensures that the depth of the two subtrees of every node never differ by more than one. Balancing is crucial for maintaining the efficiency of operations like insertion, deletion, and search.
// Example of AVL Tree rotation for balancing
class AVLTree {
int height(Node N) {
if (N == null)
return 0;
return N.height;
}
Node rightRotate(Node y) {
Node x = y.left;
Node T2 = x.right;
x.right = y;
y.left = T2;
y.height = Math.max(height(y.left), height(y.right)) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
return x;
}
}
AVL Trees:
AVL trees are a type of self-balancing BST where the heights of the two child subtrees of any node differ by at most one, ensuring logarithmic time complexity for all operations.
