Advanced Data Structures

Introduction

As computational problems grow in complexity, standard data structures often reach their limits. Advanced data structures provide sophisticated solutions to specific problem domains through specialized optimizations and novel approaches.

This article explores data structures designed for complex algorithmic challenges, covering their underlying principles, implementations, and practical applications.

Disjoint Set (Union-Find)

Concept and Purpose

Disjoint-set data structures, also known as Union-Find, track elements partitioned into non-overlapping subsets. They efficiently support two operations:

1. Find: Determine which subset an element belongs to
2. Union: Join two subsets into a single subset

Implementation

class DisjointSet {
  constructor(size) {
    this.parent = Array(size).fill().map((_, i) => i); // Each element is its own parent initially
    this.rank = Array(size).fill(0); // Rank to optimize union operations
    this.count = size; // Number of disjoint sets
  }
  
  // Find with path compression
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // Path compression
    }
    return this.parent[x];
  }
  
  // Union with rank optimization
  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    
    if (rootX === rootY) return false; // Already in the same set
    
    // Union by rank
    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      this.parent[rootY] = rootX;
      this.rank[rootX]++;
    }
    
    this.count--; // Reduce the number of disjoint sets
    return true;
  }
  
  // Check if two elements are in the same set
  connected(x, y) {
    return this.find(x) === this.find(y);
  }
  
  // Get the number of disjoint sets
  getCount() {
    return this.count;
  }
}

// Usage example: Kruskal's Minimum Spanning Tree Algorithm
function kruskalMST(n, edges) {
  const ds = new DisjointSet(n);
  let mstWeight = 0;
  const mstEdges = [];
  
  // Sort edges by weight
  edges.sort((a, b) => a.weight - b.weight);
  
  for (const edge of edges) {
    const { from, to, weight } = edge;
    
    // If including this edge doesn't create a cycle
    if (!ds.connected(from, to)) {
      ds.union(from, to);
      mstWeight += weight;
      mstEdges.push(edge);
      
      // MST has exactly n-1 edges
      if (mstEdges.length === n - 1) break;
    }
  }
  
  return { mstWeight, mstEdges };
}

// Example
const vertices = 4;
const edges = [
  { from: 0, to: 1, weight: 10 },
  { from: 0, to: 2, weight: 6 },
  { from: 0, to: 3, weight: 5 },
  { from: 1, to: 3, weight: 15 },
  { from: 2, to: 3, weight: 4 }
];

const mst = kruskalMST(vertices, edges);
console.log("MST Weight:", mst.mstWeight); // 19
console.log("MST Edges:", mst.mstEdges); // Edges of the minimum spanning tree

Time Complexity Analysis

Operation	Time Complexity (amortized)
Make-Set	O(1)
Find	O(α(n)) ≈ O(1)
Union	O(α(n)) ≈ O(1)
Connected	O(α(n)) ≈ O(1)

Where α(n) is the extremely slow-growing inverse Ackermann function.

Applications

1. Kruskal's algorithm for minimum spanning trees
2. Network connectivity problems
3. Image processing for connected component labeling
4. Percolation theory simulations
5. Dynamic graph connectivity queries

Skip Lists

Concept and Purpose

Skip lists are probabilistic data structures that allow fast search, insertion, and deletion operations. They maintain multiple layers of linked lists with progressively fewer elements, creating "express lanes" for faster traversal.

Implementation

class SkipListNode {
  constructor(value, level) {
    this.value = value;
    this.forward = new Array(level + 1).fill(null);
  }
}

class SkipList {
  constructor(maxLevel = 16, p = 0.5) {
    this.maxLevel = maxLevel;
    this.p = p; // Probability of promoting to higher level
    this.level = 0;
    this.header = new SkipListNode(-Infinity, maxLevel);
  }
  
  // Randomly determine level for a new node
  randomLevel() {
    let level = 0;
    while (Math.random() < this.p && level < this.maxLevel) {
      level++;
    }
    return level;
  }
  
  // Insert a new value
  insert(value) {
    const update = new Array(this.maxLevel + 1).fill(null);
    let current = this.header;
    
    // Find position for new node at each level
    for (let i = this.level; i >= 0; i--) {
      while (current.forward[i] !== null && current.forward[i].value < value) {
        current = current.forward[i];
      }
      update[i] = current;
    }
    
    current = current.forward[0];
    
    // Don't insert duplicates
    if (current !== null && current.value === value) {
      return false;
    }
    
    // Create new node with random level
    const newLevel = this.randomLevel();
    const newNode = new SkipListNode(value, newLevel);
    
    // Update maximum level
    if (newLevel > this.level) {
      for (let i = this.level + 1; i <= newLevel; i++) {
        update[i] = this.header;
      }
      this.level = newLevel;
    }
    
    // Insert node at all levels
    for (let i = 0; i <= newLevel; i++) {
      newNode.forward[i] = update[i].forward[i];
      update[i].forward[i] = newNode;
    }
    
    return true;
  }
  
  // Search for a value
  search(value) {
    let current = this.header;
    
    // Start from the highest level
    for (let i = this.level; i >= 0; i--) {
      while (current.forward[i] !== null && current.forward[i].value < value) {
        current = current.forward[i];
      }
    }
    
    current = current.forward[0];
    
    // Check if value was found
    return current !== null && current.value === value;
  }
  
  // Delete a value
  delete(value) {
    const update = new Array(this.maxLevel + 1).fill(null);
    let current = this.header;
    
    // Find position at each level
    for (let i = this.level; i >= 0; i--) {
      while (current.forward[i] !== null && current.forward[i].value < value) {
        current = current.forward[i];
      }
      update[i] = current;
    }
    
    current = current.forward[0];
    
    // Value not found
    if (current === null || current.value !== value) {
      return false;
    }
    
    // Remove references to node at all levels
    for (let i = 0; i <= this.level; i++) {
      if (update[i].forward[i] !== current) {
        break;
      }
      update[i].forward[i] = current.forward[i];
    }
    
    // Update level if needed
    while (this.level > 0 && this.header.forward[this.level] === null) {
      this.level--;
    }
    
    return true;
  }
  
  // Print the list (for debugging)
  printList() {
    console.log("\nSkip List:");
    for (let i = this.level; i >= 0; i--) {
      let current = this.header.forward[i];
      process.stdout.write(`Level ${i}: `);
      while (current !== null) {
        process.stdout.write(`${current.value} → `);
        current = current.forward[i];
      }
      console.log("null");
    }
  }
}

// Usage example
const sl = new SkipList();
sl.insert(3);
sl.insert(6);
sl.insert(7);
sl.insert(9);
sl.insert(12);
sl.insert(19);
sl.insert(17);
sl.insert(26);
sl.insert(21);
sl.insert(25);

sl.printList();
console.log("Search 19:", sl.search(19)); // true
console.log("Search 15:", sl.search(15)); // false
sl.delete(19);
console.log("Search 19 after delete:", sl.search(19)); // false

Time Complexity Analysis

Operation	Average Case	Worst Case
Search	O(log n)	O(n)
Insertion	O(log n)	O(n)
Deletion	O(log n)	O(n)
Space	O(n)	O(n log n)

Applications

1. Fast in-memory database indexes
2. Efficient implementation of ordered sets and maps
3. IP packet routing
4. Geographic information systems (GIS) for spatial data

B-Trees

Concept and Purpose

B-Trees are self-balancing search trees designed to work efficiently with disk-based storage systems. They maintain sorted data and allow searches, sequential access, insertions, and deletions in logarithmic time.

Key characteristics:

• All leaf nodes are at the same level
• Each node contains between t-1 and 2t-1 keys (t is the minimum degree)
• All nodes except the root have at least t-1 keys

Implementation

class BTreeNode {
  constructor(t, isLeaf = false) {
    this.t = t; // Minimum degree
    this.isLeaf = isLeaf;
    this.keys = []; // Array of keys
    this.children = []; // Array of child pointers
    this.n = 0; // Current number of keys
  }
  
  // Traverse the subtree rooted with this node
  traverse() {
    const result = [];
    
    // Traverse all keys and subtrees
    for (let i = 0; i < this.n; i++) {
      // If not leaf, traverse the subtree before the key
      if (!this.isLeaf) {
        const childValues = this.children[i].traverse();
        result.push(...childValues);
      }
      
      // Add current key
      result.push(this.keys[i]);
    }
    
    // Last child if not leaf
    if (!this.isLeaf) {
      const childValues = this.children[this.n].traverse();
      result.push(...childValues);
    }
    
    return result;
  }
  
  // Find the index of first key >= k
  findKey(k) {
    let idx = 0;
    while (idx < this.n && this.keys[idx] < k) {
      idx++;
    }
    return idx;
  }
  
  // Remove a key from this node
  removeFromNode(idx) {
    // Remove the key
    const removedKey = this.keys[idx];
    this.keys.splice(idx, 1);
    
    // If not leaf, remove the child pointer
    if (!this.isLeaf) {
      this.children.splice(idx + 1, 1);
    }
    
    this.n--;
    return removedKey;
  }
  
  // Insert a key in a non-full node
  insertNonFull(k) {
    let i = this.n - 1;
    
    if (this.isLeaf) {
      // Find position and insert
      while (i >= 0 && this.keys[i] > k) {
        this.keys[i + 1] = this.keys[i];
        i--;
      }
      
      this.keys[i + 1] = k;
      this.n++;
    } else {
      // Find child to insert into
      while (i >= 0 && this.keys[i] > k) {
        i--;
      }
      i++;
      
      // If child is full, split it
      if (this.children[i].n === 2 * this.t - 1) {
        this.splitChild(i, this.children[i]);
        
        // After split, the middle key goes up and child splits
        if (this.keys[i] < k) {
          i++;
        }
      }
      
      this.children[i].insertNonFull(k);
    }
  }
  
  // Split child at index i
  splitChild(i, y) {
    // Create new node to store (t-1) keys of y
    const z = new BTreeNode(this.t, y.isLeaf);
    z.n = this.t - 1;
    
    // Copy the last (t-1) keys of y to z
    for (let j = 0; j < this.t - 1; j++) {
      z.keys[j] = y.keys[j + this.t];
    }
    
    // Copy the last t children of y to z
    if (!y.isLeaf) {
      for (let j = 0; j < this.t; j++) {
        z.children[j] = y.children[j + this.t];
      }
    }
    
    // Reduce the number of keys in y
    y.n = this.t - 1;
    
    // Create space for new child
    this.children.splice(i + 1, 0, z);
    
    // Copy middle key of y to this node
    this.keys.splice(i, 0, y.keys[this.t - 1]);
    
    // Cleanup y's keys and children arrays
    y.keys.splice(this.t - 1, this.t);
    if (!y.isLeaf) {
      y.children.splice(this.t, this.t);
    }
    
    this.n++;
  }
}

class BTree {
  constructor(t = 3) { // Default minimum degree
    this.root = null;
    this.t = t;
  }
  
  // Traverse the tree and return an array of keys
  traverse() {
    if (!this.root) return [];
    return this.root.traverse();
  }
  
  // Search for a key in the tree
  search(k) {
    return this.root ? this._search(this.root, k) : null;
  }
  
  _search(node, k) {
    // Find the first key >= k
    let i = 0;
    while (i < node.n && k > node.keys[i]) {
      i++;
    }
    
    // If the found key is equal to k, return this node
    if (i < node.n && k === node.keys[i]) {
      return node;
    }
    
    // If key is not found and this is a leaf node
    if (node.isLeaf) {
      return null;
    }
    
    // Recursively search in the appropriate child
    return this._search(node.children[i], k);
  }
  
  // Insert a new key
  insert(k) {
    // If tree is empty
    if (!this.root) {
      this.root = new BTreeNode(this.t, true);
      this.root.keys[0] = k;
      this.root.n = 1;
      return;
    }
    
    // If root is full, tree grows in height
    if (this.root.n === 2 * this.t - 1) {
      const newRoot = new BTreeNode(this.t, false);
      newRoot.children[0] = this.root;
      
      // Split old root and move a key to the new root
      newRoot.splitChild(0, this.root);
      
      // New root has two children. Decide which child gets the new key
      let i = 0;
      if (newRoot.keys[0] < k) {
        i++;
      }
      newRoot.children[i].insertNonFull(k);
      
      this.root = newRoot;
    } else {
      // Root is not full, just insert
      this.root.insertNonFull(k);
    }
  }
  
  // Remove a key from the tree
  remove(k) {
    if (!this.root) {
      return;
    }
    
    this._remove(this.root, k);
    
    // If root has no keys, make its first child the new root
    if (this.root.n === 0) {
      if (this.root.isLeaf) {
        this.root = null; // Tree is empty
      } else {
        this.root = this.root.children[0];
      }
    }
  }
  
  _remove(node, k) {
    const idx = node.findKey(k);
    
    // If key is in this node
    if (idx < node.n && node.keys[idx] === k) {
      if (node.isLeaf) {
        // Case 1: Node is a leaf
        node.removeFromNode(idx);
      } else {
        // Case 2: Node is not a leaf
        this._removeFromNonLeaf(node, idx);
      }
    } else {
      // Key is not in this node
      if (node.isLeaf) {
        return; // Key not present in tree
      }
      
      // Flag to track if the key is in the last child
      const lastChild = (idx === node.n);
      
      // If the child where the key should be has less than t keys, fill it
      if (node.children[idx].n < this.t) {
        this._fill(node, idx);
      }
      
      // If the last child has been merged
      if (lastChild && idx > node.n) {
        this._remove(node.children[idx - 1], k);
      } else {
        this._remove(node.children[idx], k);
      }
    }
  }
  
  // Remove from a non-leaf node
  _removeFromNonLeaf(node, idx) {
    const k = node.keys[idx];
    
    // Case 2a: If the left child has at least t keys
    if (node.children[idx].n >= this.t) {
      // Find predecessor
      const pred = this._getPredecessor(node, idx);
      node.keys[idx] = pred;
      this._remove(node.children[idx], pred);
    }
    // Case 2b: If the right child has at least t keys
    else if (node.children[idx + 1].n >= this.t) {
      // Find successor
      const succ = this._getSuccessor(node, idx);
      node.keys[idx] = succ;
      this._remove(node.children[idx + 1], succ);
    }
    // Case 2c: Both left and right children have less than t keys
    else {
      this._merge(node, idx);
      this._remove(node.children[idx], k);
    }
  }
  
  // Get predecessor of keys[idx]
  _getPredecessor(node, idx) {
    // Keep going to the rightmost node until we reach a leaf
    let cur = node.children[idx];
    while (!cur.isLeaf) {
      cur = cur.children[cur.n];
    }
    
    // Return the last key of the leaf
    return cur.keys[cur.n - 1];
  }
  
  // Get successor of keys[idx]
  _getSuccessor(node, idx) {
    // Keep going to the leftmost node until we reach a leaf
    let cur = node.children[idx + 1];
    while (!cur.isLeaf) {
      cur = cur.children[0];
    }
    
    // Return the first key of the leaf
    return cur.keys[0];
  }
  
  // Fill node.children[idx] which has less than t-1 keys
  _fill(node, idx) {
    // If previous child has more than t-1 keys, borrow from it
    if (idx > 0 && node.children[idx - 1].n >= this.t) {
      this._borrowFromPrev(node, idx);
    }
    // If next child has more than t-1 keys, borrow from it
    else if (idx < node.n && node.children[idx + 1].n >= this.t) {
      this._borrowFromNext(node, idx);
    }
    // Merge with sibling
    else {
      if (idx < node.n) {
        this._merge(node, idx);
      } else {
        this._merge(node, idx - 1);
      }
    }
  }
  
  // Borrow a key from previous child
  _borrowFromPrev(node, idx) {
    const child = node.children[idx];
    const sibling = node.children[idx - 1];
    
    // Move all keys in child one step ahead
    for (let i = child.n - 1; i >= 0; i--) {
      child.keys[i + 1] = child.keys[i];
    }
    
    // If child is not a leaf, move its child pointers
    if (!child.isLeaf) {
      for (let i = child.n; i >= 0; i--) {
        child.children[i + 1] = child.children[i];
      }
    }
    
    // Set first key of child to current key in node
    child.keys[0] = node.keys[idx - 1];
    
    // Move sibling's last child as first child
    if (!child.isLeaf) {
      child.children[0] = sibling.children[sibling.n];
    }
    
    // Move sibling's last key to parent
    node.keys[idx - 1] = sibling.keys[sibling.n - 1];
    
    child.n++;
    sibling.n--;
  }
  
  // Borrow a key from next child
  _borrowFromNext(node, idx) {
    const child = node.children[idx];
    const sibling = node.children[idx + 1];
    
    // Set last key of child to parent key
    child.keys[child.n] = node.keys[idx];
    
    // Move sibling's first child to child's last
    if (!child.isLeaf) {
      child.children[child.n + 1] = sibling.children[0];
    }
    
    // Move sibling's first key to parent
    node.keys[idx] = sibling.keys[0];
    
    // Move sibling's keys one step back
    for (let i = 1; i < sibling.n; i++) {
      sibling.keys[i - 1] = sibling.keys[i];
    }
    
    // Move child pointers one step back
    if (!sibling.isLeaf) {
      for (let i = 1; i <= sibling.n; i++) {
        sibling.children[i - 1] = sibling.children[i];
      }
    }
    
    child.n++;
    sibling.n--;
  }
  
  // Merge node.children[idx] with node.children[idx+1]
  _merge(node, idx) {
    const child = node.children[idx];
    const sibling = node.children[idx + 1];
    
    // Add parent key to child
    child.keys[this.t - 1] = node.keys[idx];
    
    // Copy sibling keys to child
    for (let i = 0; i < sibling.n; i++) {
      child.keys[i + this.t] = sibling.keys[i];
    }
    
    // Copy sibling's child pointers
    if (!child.isLeaf) {
      for (let i = 0; i <= sibling.n; i++) {
        child.children[i + this.t] = sibling.children[i];
      }
    }
    
    // Move keys in parent node
    for (let i = idx + 1; i < node.n; i++) {
      node.keys[i - 1] = node.keys[i];
    }
    
    // Move child pointers
    for (let i = idx + 2; i <= node.n; i++) {
      node.children[i - 1] = node.children[i];
    }
    
    // Update counts
    child.n += sibling.n + 1;
    node.n--;
  }
}

// Usage example
const btree = new BTree(3); // Minimum degree 3
[1, 3, 7, 10, 11, 13, 14, 15, 18, 16, 19, 24, 25, 26, 21, 4, 5, 20, 22, 2, 17, 12, 6].forEach(val => {
  btree.insert(val);
});

console.log("B-Tree traversal:", btree.traverse()); // Sorted elements
console.log("Search for 15:", btree.search(15) !== null); // true
console.log("Search for 8:", btree.search(8) !== null); // false

btree.remove(15);
console.log("After removing 15:", btree.traverse());

Time Complexity Analysis

Operation	Average Case	Worst Case
Search	O(log n)	O(log n)
Insertion	O(log n)	O(log n)
Deletion	O(log n)	O(log n)

Applications

1. Database indexing and file systems
2. Multilevel indexing in large databases
3. Storage of blocks in disk-based storage systems
4. External sorting algorithms

Van Emde Boas Trees

Concept and Purpose

Van Emde Boas (vEB) trees provide efficient operations on a sorted set of integers from a limited universe {0, 1, ..., u-1}. They support basic operations in O(log log u) time, where u is the size of the universe.

Implementation

class VEBTree {
  constructor(universeSize) {
    this.universeSize = universeSize;
    this.min = null;
    this.max = null;
    
    if (universeSize <= 2) {
      this.summary = null;
      this.clusters = null;
    } else {
      const upperSqrt = Math.ceil(Math.sqrt(universeSize));
      this.summary = new VEBTree(upperSqrt);
      this.clusters = new Array(upperSqrt);
      
      for (let i = 0; i < upperSqrt; i++) {
        this.clusters[i] = new VEBTree(upperSqrt);
      }
    }
  }
  
  // Helper methods for index calculations
  high(x) {
    return Math.floor(x / Math.floor(Math.sqrt(this.universeSize)));
  }
  
  low(x) {
    return x % Math.floor(Math.sqrt(this.universeSize));
  }
  
  index(i, j) {
    return i * Math.floor(Math.sqrt(this.universeSize)) + j;
  }
  
  // Check if the tree is empty
  isEmpty() {
    return this.min === null;
  }
  
  // Check if the tree contains an element
  contains(x) {
    if (x === this.min || x === this.max) {
      return true;
    }
    
    if (this.universeSize <= 2) {
      return false;
    }
    
    return this.clusters[this.high(x)].contains(this.low(x));
  }
  
  // Insert an element
  insert(x) {
    if (this.min === null) {
      this.min = this.max = x;
      return;
    }
    
    if (x < this.min) {
      [x, this.min] = [this.min, x]; // Swap x and min
    }
    
    if (this.universeSize > 2) {
      const highX = this.high(x);
      const lowX = this.low(x);
      
      if (this.clusters[highX].isEmpty()) {
        this.summary.insert(highX);
      }
      
      this.clusters[highX].insert(lowX);
    }
    
    if (x > this.max) {
      this.max = x;
    }
  }
  
  // Find the successor of an element
  successor(x) {
    if (this.min !== null && x < this.min) {
      return this.min;
    }
    
    if (this.universeSize <= 2) {
      if (x === 0 && this.max === 1) {
        return 1;
      }
      return null;
    }
    
    const highX = this.high(x);
    const lowX = this.low(x);
    
    let successorCluster;
    let successorLow;
    
    if (lowX < this.clusters[highX].max) {
      // Successor is in the same cluster
      successorLow = this.clusters[highX].successor(lowX);
      return this.index(highX, successorLow);
    }
    
    // Find the next non-empty cluster
    successorCluster = this.summary.successor(highX);
    if (successorCluster === null) {
      return null;
    }
    
    successorLow = this.clusters[successorCluster].min;
    return this.index(successorCluster, successorLow);
  }
  
  // Find the predecessor of an element
  predecessor(x) {
    if (this.max !== null && x > this.max) {
      return this.max;
    }
    
    if (this.universeSize <= 2) {
      if (x === 1 && this.min === 0) {
        return 0;
      }
      return null;
    }
    
    const highX = this.high(x);
    const lowX = this.low(x);
    
    let predecessorCluster;
    let predecessorLow;
    
    if (lowX > this.clusters[highX].min) {
      // Predecessor is in the same cluster
      predecessorLow = this.clusters[highX].predecessor(lowX);
      return this.index(highX, predecessorLow);
    }
    
    // Find the previous non-empty cluster
    predecessorCluster = this.summary.predecessor(highX);
    if (predecessorCluster === null) {
      if (this.min !== null && x > this.min) {
        return this.min;
      }
      return null;
    }
    
    predecessorLow = this.clusters[predecessorCluster].max;
    return this.index(predecessorCluster, predecessorLow);
  }
  
  // Delete an element
  delete(x) {
    if (this.min === this.max) {
      if (this.min === x) {
        this.min = this.max = null;
      }
      return;
    }
    
    if (this.universeSize === 2) {
      if (x === 0) {
        this.min = 1;
      } else {
        this.min = 0;
      }
      this.max = this.min;
      return;
    }
    
    if (x === this.min) {
      const firstCluster = this.summary.min;
      x = this.index(firstCluster, this.clusters[firstCluster].min);
      this.min = x;
    }
    
    const highX = this.high(x);
    const lowX = this.low(x);
    
    this.clusters[highX].delete(lowX);
    
    if (this.clusters[highX].isEmpty()) {
      this.summary.delete(highX);
      
      if (x === this.max) {
        const summaryMax = this.summary.max;
        if (summaryMax === null) {
          this.max = this.min;
        } else {
          this.max = this.index(summaryMax, this.clusters[summaryMax].max);
        }
      }
    } else if (x === this.max) {
      this.max = this.index(highX, this.clusters[highX].max);
    }
  }
}

// Usage example
const veb = new VEBTree(16); // Universe size 16 (0-15)

veb.insert(2);
veb.insert(3);
veb.insert(4);
veb.insert(5);
veb.insert(7);
veb.insert(14);
veb.insert(15);

console.log("Contains 5:", veb.contains(5)); // true
console.log("Contains 6:", veb.contains(6)); // false
console.log("Successor of 5:", veb.successor(5)); // 7
console.log("Predecessor of 5:", veb.predecessor(5)); // 4

veb.delete(5);
console.log("Contains 5 after delete:", veb.contains(5)); // false
console.log("Successor of 4 after delete:", veb.successor(4)); // 7

Time Complexity Analysis

Operation	Time Complexity
Insert	O(log log u)
Delete	O(log log u)
Successor	O(log log u)
Predecessor	O(log log u)
Minimum	O(1)
Maximum	O(1)
Contains	O(log log u)

Where u is the size of the universe.

Applications

1. IP routing in computer networks
2. Process scheduling in operating systems
3. Priority queues with bounded integers
4. Range queries on bounded integer sets

Splay Trees

Concept and Purpose

Splay trees are self-adjusting binary search trees that move recently accessed elements closer to the root. While they don't guarantee worst-case performance, they provide amortized logarithmic time for operations.

Implementation

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

class SplayTree {
  constructor() {
    this.root = null;
  }
  
  // Right rotation
  rightRotate(x) {
    const y = x.left;
    x.left = y.right;
    y.right = x;
    return y;
  }
  
  // Left rotation
  leftRotate(x) {
    const y = x.right;
    x.right = y.left;
    y.left = x;
    return y;
  }
  
  // Splay operation - bring node with key k to root
  splay(root, k) {
    // Base cases
    if (!root || root.value === k) {
      return root;
    }
    
    if (root.value > k) {
      // Key is in left subtree
      if (!root.left) {
        return root; // Key not found
      }
      
      if (root.left.value > k) {
        // Zig-Zig (Left Left)
        root.left.left = this.splay(root.left.left, k);
        root = this.rightRotate(root);
      } else if (root.left.value < k) {
        // Zig-Zag (Left Right)
        root.left.right = this.splay(root.left.right, k);
        
        if (root.left.right) {
          root.left = this.leftRotate(root.left);
        }
      }
      
      // Do second rotation if needed
      return root.left ? this.rightRotate(root) : root;
    } else {
      // Key is in right subtree
      if (!root.right) {
        return root; // Key not found
      }
      
      if (root.right.value > k) {
        // Zig-Zag (Right Left)
        root.right.left = this.splay(root.right.left, k);
        
        if (root.right.left) {
          root.right = this.rightRotate(root.right);
        }
      } else if (root.right.value < k) {
        // Zig-Zig (Right Right)
        root.right.right = this.splay(root.right.right, k);
        root = this.leftRotate(root);
      }
      
      // Do second rotation if needed
      return root.right ? this.leftRotate(root) : root;
    }
  }
  
  // Search for a key (with splaying)
  search(k) {
    this.root = this.splay(this.root, k);
    return this.root && this.root.value === k;
  }
  
  // Insert a new key
  insert(k) {
    // If tree is empty
    if (!this.root) {
      this.root = new SplayNode(k);
      return;
    }
    
    // Splay the key
    this.root = this.splay(this.root, k);
    
    // If key already exists
    if (this.root.value === k) {
      return;
    }
    
    // Create a new node
    const newNode = new SplayNode(k);
    
    // If root's value is greater, make
    // newNode as root and make right subtree
    // as right of newNode
    if (this.root.value > k) {
      newNode.right = this.root;
      newNode.left = this.root.left;
      this.root.left = null;
    } else {
      // If root's value is smaller, make
      // newNode as root and make left subtree
      // as left of newNode
      newNode.left = this.root;
      newNode.right = this.root.right;
      this.root.right = null;
    }
    
    this.root = newNode;
  }
  
  // Delete a key
  delete(k) {
    if (!this.root) {
      return;
    }
    
    // Splay the key
    this.root = this.splay(this.root, k);
    
    // If key not found
    if (this.root.value !== k) {
      return;
    }
    
    // If root is the only node
    if (!this.root.left) {
      this.root = this.root.right;
    } else {
      // Find the maximum in left subtree
      let temp = this.root.right;
      this.root = this.root.left;
      
      // Splay the maximum to root
      this.root = this.splay(this.root, k);
      
      // Connect right subtree
      this.root.right = temp;
    }
  }
  
  // Inorder traversal
  inOrder() {
    const result = [];
    this._inOrderRecursive(this.root, result);
    return result;
  }
  
  _inOrderRecursive(node, result) {
    if (!node) return;
    
    this._inOrderRecursive(node.left, result);
    result.push(node.value);
    this._inOrderRecursive(node.right, result);
  }
}

// Usage example
const splayTree = new SplayTree();
[10, 5, 15, 3, 7, 13, 17, 2, 4, 6, 8].forEach(val => splayTree.insert(val));

console.log("Inorder traversal:", splayTree.inOrder()); // Sorted elements
console.log("Search for 7:", splayTree.search(7)); // true
console.log("Search for 9:", splayTree.search(9)); // false

splayTree.delete(7);
console.log("After deleting 7:", splayTree.inOrder());
console.log("Search for 7 after delete:", splayTree.search(7)); // false

Time Complexity Analysis

Operation	Amortized Time	Worst Case
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)
Search	O(log n)	O(n)

Applications

1. Caching systems (most recently used items near the root)
2. Self-adjusting data structures for access pattern optimization
3. Garbage collection algorithms
4. Implementation of other data structures like Fibonacci heaps

Comparison of Advanced Data Structures

Data Structure	Search	Insert	Delete	Space	Special Features
Skip List	O(log n)	O(log n)	O(log n)	O(n)	Simple implementation, probabilistic
B-Tree	O(log n)	O(log n)	O(log n)	O(n)	Optimized for disk access
Red-Black Tree	O(log n)	O(log n)	O(log n)	O(n)	Guaranteed balance
Splay Tree	O(log n)*	O(log n)*	O(log n)*	O(n)	Self-adjusting, access optimization
vEB Tree	O(log log u)	O(log log u)	O(log log u)	O(u)	Fast for bounded integers
Disjoint Set	O(α(n))	O(α(n))	-	O(n)	Union and Find operations

*Amortized time complexity

Conclusion

Advanced data structures provide specialized tools for solving complex computational problems efficiently. While they often require more complex implementations than basic structures, they offer significant performance benefits for specific use cases.

When selecting an advanced data structure for your application, consider:

1. The nature of your data: Size, distribution, and type
2. Required operations: Which operations need to be optimized
3. Implementation complexity: Balance between performance and maintainability
4. Memory constraints: Space efficiency requirements
5. Special requirements: Such as persistence, concurrency, or disk access optimization

By understanding the strengths and limitations of these advanced data structures, you can make informed decisions to optimize the performance of your algorithms and applications.

In future articles, we'll explore specialized data structures for text processing, geometric algorithms, and parallel computing.