Binary Search Trees: Operations, Balancing & Applications

Master BST operations, balancing techniques, and real-world applications. This tutorial covers insertion, deletion, traversal, and self-balancing trees with implementation examples.

BST Usage in Systems (2023)

Database Indexing (40%)

Search Algorithms (30%)

Memory Management (20%)

Other (10%)

1. BST Fundamentals

Core Properties:

Ordering: Left subtree ≤ Node ≤ Right subtree
No Duplicates: Typically stores unique values
Efficiency: O(h) operations, where h = tree height

Time Complexities:

Operation	Average Case	Worst Case (Unbalanced)	Balanced Tree
Search	O(log n)	O(n)	O(log n)
Insertion	O(log n)	O(n)	O(log n)
Deletion	O(log n)	O(n)	O(log n)
Traversal	O(n)	O(n)	O(n)

Node Implementation:


class BSTNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
    this.parent = null; // Optional for some operations
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
}

2. Core BST Operations

Essential Methods:

Insertion


insert(value) {
  const newNode = new BSTNode(value);
  if (!this.root) {
    this.root = newNode;
    return;
  }

  let current = this.root;
  while (true) {
    if (value < current.value) {
      if (!current.left) {
        current.left = newNode;
        newNode.parent = current;
        break;
      }
      current = current.left;
    } else if (value > current.value) {
      if (!current.right) {
        current.right = newNode;
        newNode.parent = current;
        break;
      }
      current = current.right;
    } else {
      // Handle duplicates (optional)
      break;
    }
  }
}

Deletion (3 Cases)


delete(value) {
  const [node, parent] = this._findWithParent(value);
  if (!node) return false;

  // Case 1: No children
  if (!node.left && !node.right) {
    this._replaceChild(parent, node, null);
  }
  // Case 2: One child
  else if (!node.left || !node.right) {
    const child = node.left || node.right;
    this._replaceChild(parent, node, child);
  }
  // Case 3: Two children
  else {
    const successor = this._findMin(node.right);
    node.value = successor.value;
    this.delete(successor.value);
  }
  return true;
}

_findMin(node) {
  while (node.left) node = node.left;
  return node;
}

Search Techniques:

Iterative Search: Efficient O(h) implementation
Recursive Search: Cleaner code but uses call stack
Range Queries: Find all values between [x, y]
Successor/Predecessor: In-order traversal helpers

3. Balancing BSTs

Self-Balancing Variants:

AVL Trees

Height-balanced with rotations


class AVLTree extends BinarySearchTree {
  insert(value) {
    super.insert(value);
    this._balance(this.root);
  }

  _balance(node) {
    if (!node) return;
    const balanceFactor = this._getBalanceFactor(node);
    
    // Left heavy
    if (balanceFactor > 1) {
      if (this._getBalanceFactor(node.left) >= 0) {
        this._rotateRight(node);
      } else {
        this._rotateLeft(node.left);
        this._rotateRight(node);
      }
    }
    // Right heavy
    else if (balanceFactor < -1) {
      if (this._getBalanceFactor(node.right) <= 0) {
        this._rotateLeft(node);
      } else {
        this._rotateRight(node.right);
        this._rotateLeft(node);
      }
    }
    
    this._balance(node.left);
    this._balance(node.right);
  }
}

Red-Black Trees

Color-coded nodes with rules


class RedBlackTree extends BinarySearchTree {
  insert(value) {
    const newNode = super.insert(value);
    newNode.color = 'RED';
    this._fixInsertViolation(newNode);
  }

  _fixInsertViolation(node) {
    while (node !== this.root && node.parent.color === 'RED') {
      // ... Complex recoloring and rotation logic
    }
    this.root.color = 'BLACK';
  }
}

Balancing Operations:

Left Rotation: Pivot around right child
Right Rotation: Pivot around left child
Left-Right Rotation: Double rotation
Right-Left Rotation: Mirror of above

BST Problem-Solving Cheat Sheet

Problem Type	Approach	Time Complexity
Validate BST	In-order traversal check	O(n)
Kth Smallest	In-order traversal with count	O(k)
Lowest Common Ancestor	Utilize BST properties	O(h)
Range Sum	Modified traversal	O(k)

4. Advanced BST Concepts

Threaded BST

Optimized for in-order traversal


class ThreadedBSTNode extends BSTNode {
  constructor(value) {
    super(value);
    this.leftThread = false;
    this.rightThread = false;
  }
}

B-Tree Variants

Optimized for disk storage


class BTreeNode {
  constructor(order) {
    this.keys = [];
    this.children = [];
    this.order = order;
    this.isLeaf = true;
  }
}

Augmented BST

Additional node metadata


class AugmentedBSTNode extends BSTNode {
  constructor(value) {
    super(value);
    this.size = 1; // Subtree node count
    this.sum = value; // Subtree sum
  }
}

BST Problem-Solving Checklist

✓ Verify BST property maintenance

✓ Consider balance factor for performance

✓ Handle all deletion cases (0, 1, 2 children)

✓ Utilize in-order traversal for sorted output

DSA Expert Insight: BST problems appear in 35% of technical interviews. Mastering both basic operations and balancing techniques is crucial for efficient search and retrieval problems.

0 Interaction

0 Views

0 Likes