Binary Search Trees: Insertion, Deletion, AVL & Red-Black Trees Explained

Introduction to Binary Search Trees (BST)

A Binary Search Tree (BST) is a node-based data structure where each node has at most two children, referred to as the left and right child.

Each node in a BST follows these properties:

• The left subtree of a node contains only nodes with values lesser than the node’s value.
• The right subtree of a node contains only nodes with values greater than the node’s value.
• Both left and right subtrees must also be binary search trees.

BSTs are widely used in searching applications due to their efficient O(log n) time complexity for insertion, deletion, and search operations.

Insertion in a Binary Search Tree

Insertion in a BST follows these steps:

1. Start from the root node.
2. If the new value is smaller than the current node, move to the left subtree.
3. If the new value is greater, move to the right subtree.
4. Repeat the process until an empty spot is found and insert the new node.

The time complexity of insertion in a balanced BST is O(log n), while in an unbalanced BST, it can be O(n).

Deletion in a Binary Search Tree

There are three cases when deleting a node in a BST:

• Case 1: The node to be deleted is a leaf node (no children). Simply remove it.
• Case 2: The node has one child. Replace the node with its child.
• Case 3: The node has two children. Find its in-order successor (smallest node in the right subtree) and replace the node’s value with it, then delete the successor.

Deletion in a BST has a time complexity of O(log n) in a balanced BST and O(n) in an unbalanced BST.

Self-Balancing Binary Search Trees

In a standard BST, insertion and deletion operations may cause the tree to become unbalanced, increasing the search time to O(n). To avoid this, self-balancing BSTs are used. These include AVL trees and Red-Black trees.

AVL Trees

An AVL tree is a self-balancing BST where the difference between heights of left and right subtrees of any node is at most 1. It ensures that search, insertion, and deletion operations take O(log n) time.

Rotations in AVL Tree

• Right Rotation (LL Rotation) - Performed when nodes are inserted into the left subtree of a left-heavy node.
• Left Rotation (RR Rotation) - Performed when nodes are inserted into the right subtree of a right-heavy node.
• Left-Right Rotation (LR Rotation) - A left rotation followed by a right rotation.
• Right-Left Rotation (RL Rotation) - A right rotation followed by a left rotation.

AVL trees provide faster lookup times compared to unbalanced BSTs.

Red-Black Trees

A Red-Black Tree is another self-balancing BST that ensures balance through the following properties:

• Each node is either red or black.
• The root node is always black.
• Red nodes cannot have red children (no two consecutive red nodes).
• Every path from a node to its descendant NULL nodes must have the same number of black nodes.

Red-Black Trees provide efficient insertion and deletion while keeping the tree balanced, ensuring O(log n) complexity.

Conclusion

Binary Search Trees are essential for efficient searching, insertion, and deletion. However, maintaining balance is crucial for optimal performance. Self-balancing trees like AVL and Red-Black trees ensure that operations remain efficient with O(log n) complexity, making them ideal for large datasets.