Binary Data Structures: Trees and Heaps in JavaScript

Binary data structures are a fundamental concept in computer science, allowing for efficient organization and manipulation of data. Two of the most important binary structures are trees and heaps. In this article, we‘ll take an in-depth look at these data types and explore how to implement them in JavaScript.

Table of Contents

1. Introduction to Trees
2. Binary Search Trees
3. Implementing a BST in JavaScript
4. Introduction to Heaps
5. Max Heaps and Min Heaps
6. Implementing a Heap in JavaScript
7. Time Complexity Analysis
8. Trees vs Heaps: A Comparison
9. Advanced Topics
10. Conclusion

Introduction to Trees

A tree is a hierarchical data structure composed of nodes. Each node contains a value and references to child nodes. The topmost node is called the root. Nodes with no children are leaf nodes.

Trees have many applications, such as:

• Representing hierarchical relationships
• Managing sorted data
• Facilitating fast search, insertion, and deletion operations
• Providing a foundation for other data structures like heaps and graphs

There are many types of trees, including binary trees, where each node has at most two children, and N-ary trees, which can have any number of children per node. We‘ll focus on binary trees.

Binary Search Trees

A binary search tree (BST) is a type of binary tree that follows these rules:

1. Each node has at most two child nodes, referred to as the left child and right child
2. For any node, the value of the left child must be less than the node‘s value
3. For any node, the value of the right child must be greater than the node‘s value

These properties allow for efficient searching, insertion, and deletion.

To search for a value in a BST:

1. Start at the root
2. If the target value is less than the current node‘s value, move to the left child
3. If the target is greater than the current value, move to the right child
4. If the target is equal to the current value, you‘ve found the target node
5. If you reach a null node, the target is not present

Inserting a new node follows a similar process:

1. Start at the root
2. Compare the new value to the current node‘s value
3. If less, move left. If greater, move right.
4. Once you reach a null child, insert the new node there

Implementing a BST in JavaScript

Here‘s a basic BST implementation in JavaScript:

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;
      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;
      }
    }
  }

  search(value) {
    if (!this.root) return false;

    let current = this.root;
    while (current) {
      if (value === current.value) return current;
      if (value < current.value) {
        current = current.left; 
      } else {
        current = current.right;
      }
    }
    return false;
  }
}

We define a Node class to represent each node, with value, left, and right properties. The BinarySearchTree class has an insert method for adding new nodes and a search method for finding a node with a given value.

Introduction to Heaps

A heap is another type of binary tree, but with different rules than a BST. In a heap, the nodes are ordered according to the heap property. For a max heap, each parent node‘s value is greater than or equal to its children‘s values. For a min heap, each parent‘s value is less than or equal to its children‘s.

Heaps are commonly implemented as arrays, with the nodes laid out in breadth-first order. For a node at index i, its left child is at index 2i + 1, its right child is at 2i + 2, and its parent is at floor((i - 1) / 2).

Max Heaps and Min Heaps

The two types of heaps are max heaps and min heaps. In a max heap, the root node has the largest value, and each parent node has a value greater than or equal to its children. This allows for efficient retrieval of the maximum element.

In a min heap, the root has the smallest value, and parents are smaller than their children. This enables quick access to the minimum element.

Common heap operations include:

• insert: Add a new value to the heap
• extractMax / extractMin: Remove and return the max/min value
• heapify: Restore the heap property after an insertion or extraction

When inserting into a max heap, we add the new value to the end of the array, then "bubble up" the value by swapping it with its parent until the heap property is satisfied.

Extracting the max element involves replacing the root with the last element in the array, then "sinking down" the new root by swapping it with its larger child until the heap property is restored.

Implementing a Heap in JavaScript

Here‘s an implementation of a max heap in JavaScript:

class MaxHeap {
  constructor() {
    this.values = [];
  }

  insert(value) {
    this.values.push(value);
    this.bubbleUp();
    return this.values;
  }

  bubbleUp() {
    let index = this.values.length - 1;
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      if (this.values[parentIndex] >= this.values[index]) break;
      [this.values[parentIndex], this.values[index]] = 
        [this.values[index], this.values[parentIndex]];
      index = parentIndex;
    }
  }

  extractMax() {
    const max = this.values[0];
    const end = this.values.pop();
    if (this.values.length > 0) {
      this.values[0] = end;
      this.sinkDown();
    }
    return max;
  }

  sinkDown() {
    let index = 0;
    const length = this.values.length;
    while (true) {
      let leftChildIndex = 2 * index + 1;
      let rightChildIndex = 2 * index + 2;
      let leftChild, rightChild;
      let swap = null;

      if (leftChildIndex < length) {
        leftChild = this.values[leftChildIndex];
        if (leftChild > this.values[index]) {
          swap = leftChildIndex;
        }
      }
      if (rightChildIndex < length) {
        rightChild = this.values[rightChildIndex];
        if (
          (swap === null && rightChild > this.values[index]) ||
          (swap !== null && rightChild > leftChild)
        ) {
          swap = rightChildIndex;
        }
      }

      if (swap === null) break;
      [this.values[index], this.values[swap]] = 
        [this.values[swap], this.values[index]];
      index = swap;
    }
  }
}

The MaxHeap class uses an array to store the heap elements. The insert method adds a value to the end and calls bubbleUp to restore the heap property. extractMax removes and returns the root value, replacing it with the last element, then calls sinkDown to restore the heap order.

Time Complexity Analysis

For a BST with n nodes, the average time complexities are:

• Insertion: O(log n)
• Searching: O(log n)
• Deletion: O(log n)

In the worst case (an unbalanced tree), these operations may take O(n) time. Self-balancing trees like AVL trees and Red-Black trees are used to avoid this.

For a heap with n elements:

• Insertion (with bubble-up): O(log n)
• Extraction of max/min (with sink-down): O(log n)
• Search: O(n)

Heaps are great for retrieving the max or min value quickly, but not for searching for arbitrary values.

Trees vs Heaps: A Comparison

While both trees and heaps are hierarchical data structures, they have different strengths:

Trees:

• Ideal for storing sorted data and performing frequent searches
• Allow for efficient insertion, deletion, and search operations
• Useful for tasks like indexing and symbol tables

Heaps:

• Excel at accessing the maximum or minimum element
• Insertion and extraction are fast, but searching is slow
• Used in priority queues, scheduling, and algorithms like Heap Sort and Dijkstra‘s Algorithm

Advanced Topics

Some further concepts related to trees and heaps:

• Self-balancing BSTs like AVL trees and Red-Black trees maintain O(log n) operations by automatically rebalancing when needed
• Trie (prefix tree): A tree-like data structure for storing strings, enabling fast prefix matching
• Heap Sort: An O(n log n) sorting algorithm that uses a heap to efficiently find the next largest element
• Priority Queues: Abstract data type often implemented with heaps, allowing insertion of items with priorities and removal of the highest/lowest priority item

Understanding the mathematical underpinnings of these structures, such as logarithms and the binary number system, can deepen your grasp of their behavior and performance.

Conclusion

Trees and heaps are versatile, powerful tools in a programmer‘s toolkit. Trees provide a way to keep data sorted and searchable, while heaps excel at maintaining priority-based ordering and accessing extremal values. By mastering these data structures, you‘ll be well-equipped to tackle complex problems efficiently.

To learn more, dive into advanced tree types like B-trees and splay trees, and practice solving problems using heaps. With a solid understanding of these concepts, you‘ll be able to choose the ideal data structure for any situation.