advanced-binary-trees.md

Advanced Binary Trees: Variations and Balancing

This document elaborates on Binary Trees, focusing on advanced variations such as Red-Black Trees and techniques for balancing. It explains the concepts, properties, and JavaScript implementations for Binary Search Trees (BSTs), AVL Trees, and Red-Black Trees, including balancing mechanisms.

Binary Search Trees (BST)

Concept

A Binary Search Tree is a binary tree where each node has a value, and for any node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater. BSTs enable efficient searching, insertion, and deletion with an average time complexity of O(log n) when balanced, but O(n) in the worst case (e.g., skewed trees).

Implementation

Below is a JavaScript implementation of a BST with insertion and in-order traversal.

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

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

  insert(value) {
    const newNode = new Node(value);
    if (!this.root) {
      this.root = newNode;
      return this;
    }
    let current = this.root;
    while (true) {
      if (value === current.value) return undefined; // No duplicates
      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          return this;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          return this;
        }
        current = current.right;
      }
    }
  }

  inOrder() {
    const result = [];
    function traverse(node) {
      if (node) {
        traverse(node.left);
        result.push(node.value);
        traverse(node.right);
      }
    }
    traverse(this.root);
    return result;
  }
}

// Example usage
const bst = new BinarySearchTree();
bst.insert(10).insert(5).insert(15).insert(3).insert(7);
console.log(bst.inOrder()); // Output: [3, 5, 7, 10, 15]

AVL Trees (Self-Balancing)

Concept

An AVL Tree is a self-balancing BST where the height difference (balance factor) between the left and right subtrees of any node is at most 1. It performs rotations to maintain balance after insertions or deletions, ensuring O(log n) operations. Key concepts:

• Balance Factor: Height of left subtree minus height of right subtree.
• Rotations: Left, Right, Left-Right, and Right-Left rotations to restore balance.

Implementation

Below is a JavaScript implementation of an AVL Tree with insertion and balancing.

class AVLNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
    this.height = 1;
  }
}

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

  // Get height of a node
  getHeight(node) {
    return node ? node.height : 0;
  }

  // Get balance factor
  getBalance(node) {
    return node ? this.getHeight(node.left) - this.getHeight(node.right) : 0;
  }

  // Update height
  updateHeight(node) {
    node.height = Math.max(this.getHeight(node.left), this.getHeight(node.right)) + 1;
  }

  // Right rotation
  rightRotate(y) {
    const x = y.left;
    const T2 = x.right;
    x.right = y;
    y.left = T2;
    this.updateHeight(y);
    this.updateHeight(x);
    return x;
  }

  // Left rotation
  leftRotate(x) {
    const y = x.right;
    const T2 = y.left;
    y.left = x;
    x.right = T2;
    this.updateHeight(x);
    this.updateHeight(y);
    return y;
  }

  insert(value) {
    this.root = this._insert(this.root, value);
  }

  _insert(node, value) {
    if (!node) return new AVLNode(value);

    if (value < node.value) {
      node.left = this._insert(node.left, value);
    } else if (value > node.value) {
      node.right = this._insert(node.right, value);
    } else {
      return node; // No duplicates
    }

    this.updateHeight(node);
    const balance = this.getBalance(node);

    // Left Left
    if (balance > 1 && value < node.left.value) {
      return this.rightRotate(node);
    }
    // Right Right
    if (balance < -1 && value > node.right.value) {
      return this.leftRotate(node);
    }
    // Left Right
    if (balance > 1 && value > node.left.value) {
      node.left = this.leftRotate(node.left);
      return this.rightRotate(node);
    }
    // Right Left
    if (balance < -1 && value < node.right.value) {
      node.right = this.rightRotate(node.right);
      return this.leftRotate(node);
    }

    return node;
  }

  inOrder() {
    const result = [];
    function traverse(node) {
      if (node) {
        traverse(node.left);
        result.push(node.value);
        traverse(node.right);
      }
    }
    traverse(this.root);
    return result;
  }
}

// Example usage
const avl = new AVLTree();
avl.insert(10);
avl.insert(20);
avl.insert(30); // Triggers rotation
console.log(avl.inOrder()); // Output: [10, 20, 30]

Red-Black Trees

Concept

A Red-Black Tree is a self-balancing BST with additional color properties (red or black) to ensure balance. It guarantees O(log n) operations by maintaining these properties:

1. Every node is either red or black.
2. The root is black.
3. All leaves (null nodes) are black.
4. Red nodes cannot have red children (no two consecutive reds).
5. Every path from a node to its descendant leaves has the same number of black nodes.

Balancing is achieved through rotations and color flips during insertions and deletions.

Implementation

Below is a JavaScript implementation of a Red-Black Tree with insertion and balancing.

class RBNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
    this.color = 'RED'; // New nodes are red
    this.parent = null;
  }
}

class RedBlackTree {
  constructor() {
    this.root = null;
    this.NIL = new RBNode(null);
    this.NIL.color = 'BLACK';
  }

  // Left rotation
  leftRotate(node) {
    const y = node.right;
    node.right = y.left;
    if (y.left !== this.NIL) {
      y.left.parent = node;
    }
    y.parent = node.parent;
    if (!node.parent) {
      this.root = y;
    } else if (node === node.parent.left) {
      node.parent.left = y;
    } else {
      node.parent.right = y;
    }
    y.left = node;
    node.parent = y;
  }

  // Right rotation
  rightRotate(node) {
    const x = node.left;
    node.left = x.right;
    if (x.right !== this.NIL) {
      x.right.parent = node;
    }
    x.parent = node.parent;
    if (!node.parent) {
      this.root = x;
    } else if (node === node.parent.right) {
      node.parent.right = x;
    } else {
      node.parent.left = x;
    }
    x.right = node;
    node.parent = x;
  }

  insert(value) {
    const newNode = new RBNode(value);
    newNode.left = this.NIL;
    newNode.right = this.NIL;
    let parent = null;
    let current = this.root;

    // Find position to insert
    while (current !== this.NIL) {
      parent = current;
      if (value < current.value) {
        current = current.left;
      } else {
        current = current.right;
      }
    }

    newNode.parent = parent;
    if (!parent) {
      this.root = newNode;
    } else if (value < parent.value) {
      parent.left = newNode;
    } else {
      parent.right = newNode;
    }

    this.fixInsert(newNode);
  }

  fixInsert(node) {
    while (node.parent && node.parent.color === 'RED') {
      if (node.parent === node.parent.parent.left) {
        const uncle = node.parent.parent.right;
        if (uncle.color === 'RED') {
          node.parent.color = 'BLACK';
          uncle.color = 'BLACK';
          node.parent.parent.color = 'RED';
          node = node.parent.parent;
        } else {
          if (node === node.parent.right) {
            node = node.parent;
            this.leftRotate(node);
          }
          node.parent.color = 'BLACK';
          node.parent.parent.color = 'RED';
          this.rightRotate(node.parent.parent);
        }
      } else {
        const uncle = node.parent.parent.left;
        if (uncle.color === 'RED') {
          node.parent.color = 'BLACK';
          uncle.color = 'BLACK';
          node.parent.parent.color = 'RED';
          node = node.parent.parent;
        } else {
          if (node === node.parent.left) {
            node = node.parent;
            this.rightRotate(node);
          }
          node.parent.color = 'BLACK';
          node.parent.parent.color = 'RED';
          this.leftRotate(node.parent.parent);
        }
      }
      if (node === this.root) break;
    }
    this.root.color = 'BLACK';
  }

  inOrder() {
    const result = [];
    function traverse(node, NIL) {
      if (node !== NIL) {
        traverse(node.left, NIL);
        result.push(node.value);
        traverse(node.right, NIL);
      }
    }
    traverse(this.root, this.NIL);
    return result;
  }
}

// Example usage
const rbt = new RedBlackTree();
rbt.insert(10);
rbt.insert(20);
rbt.insert(30);
console.log(rbt.inOrder()); // Output: [10, 20, 30]

Balancing Techniques

Why Balancing?

Unbalanced BSTs (e.g., skewed trees) degrade to O(n) performance for operations. Balancing ensures O(log n) time complexity by maintaining a roughly equal height of subtrees.

AVL vs. Red-Black Trees

• AVL Trees: Stricter balancing (balance factor ≤ 1) results in faster lookups but more rotations during insertions/deletions.
• Red-Black Trees: Looser balancing (via color properties) allows fewer rotations, making them more efficient for frequent modifications but slightly slower for searches.
• Use Cases:
  • AVL: Databases, applications needing frequent searches.
  • Red-Black: Standard libraries (e.g., C++ STL, Java TreeMap), dynamic datasets.

Other Balancing Techniques

• Splay Trees: Self-adjusting trees that move frequently accessed nodes to the root via rotations.
• B-Trees: Generalization of BSTs for disk-based storage, used in databases and file systems.
• Treaps: Combine BST and heap properties, using random priorities for balancing.

Conclusion

Binary Search Trees provide a foundation for efficient data management, but their performance depends on balance. AVL and Red-Black Trees address this through rotations and color-based rules, respectively. The provided JavaScript implementations demonstrate insertion and balancing, enabling O(log n) operations for various applications.