Splay Tree Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Splay Tree Sort

A self-adjusting search tree sort: elements are inserted into a Splay Tree, splaying recently accessed nodes to the root, followed by an in-order retrieval.

How it works

Splay Tree Sort is a variations of BST sort using a Splay Tree, a self-balancing binary search tree. Every insertion triggers a sequence of tree rotations called "splaying" that moves the newly inserted node to the root:

1. Splay Tree Insertion: For each element in the input, insert it into the BST. If a key is found or inserted, we "splay" it to the root using Zig-Zig, Zig-Zag, Zag-Zig, or Zag-Zag double-rotations.
2. Amortized Balancing: Splaying doesn't guarantee strict height balance (like AVL or Red-Black trees), but it achieves a logarithmic amortized cost per operation. Frequently accessed or recently inserted elements stay near the root.
3. In-Order Traversal: Once all elements are splayed and stored, an in-order traversal collects the items in sorted order and copies them back.

Complexity

Interactive visualization

Pseudocode

procedure splayTreeSort(A):
  root ← null
  for each x in A:
    root ← insert(root, x)
  i ← 0
  inOrderTraversal(root, A, i)

procedure insert(root, x):
  if root is null:
    return new Node(x)
  root ← splay(root, x)
  newNode ← new Node(x)
  if x < root.value:
    newNode.right ← root
    newNode.left ← root.left
    root.left ← null
  else:
    newNode.left ← root
    newNode.right ← root.right
    root.right ← null
  return newNode

JavaScript implementation

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

function rotateRight(x) {
  const y = x.left;
  x.left = y.right;
  y.right = x;
  return y;
}

function rotateLeft(x) {
  const y = x.right;
  x.right = y.left;
  y.left = x;
  return y;
}

function splay(root, val) {
  if (!root || root.val === val) return root;
  if (val < root.val) {
    if (!root.left) return root;
    if (val < root.left.val) {
      root.left.left = splay(root.left.left, val);
      root = rotateRight(root);
    } else if (val > root.left.val) {
      root.left.right = splay(root.left.right, val);
      if (root.left.right) root.left = rotateLeft(root.left);
    }
    return !root.left ? root : rotateRight(root);
  } else {
    if (!root.right) return root;
    if (val < root.right.val) {
      root.right.left = splay(root.right.left, val);
      if (root.right.left) root.right = rotateRight(root.right);
    } else if (val > root.right.val) {
      root.right.right = splay(root.right.right, val);
      root = rotateLeft(root);
    }
    return !root.right ? root : rotateLeft(root);
  }
}

function splayTreeSort(arr) {
  let root = null;
  for (let val of arr) {
    if (!root) {
      root = new SplayNode(val);
    } else {
      root = splay(root, val);
      const newNode = new SplayNode(val);
      if (val < root.val) {
        newNode.right = root;
        newNode.left = root.left;
        root.left = null;
      } else {
        newNode.left = root;
        newNode.right = root.right;
        root.right = null;
      }
      root = newNode;
    }
  }
  let i = 0;
  function inOrder(node) {
    if (!node) return;
    inOrder(node.left);
    arr[i++] = node.val;
    inOrder(node.right);
  }
  inOrder(root);
  return arr;
}

Pros and cons

When (not) to use it

• Working with biased data accesses: Excellent when some elements are queried or modified repeatedly.
• Standard in-memory arrays: Timsort or Quicksort are significantly faster due to the overhead of pointer updates and splaying cycles.