Growing with the Web

Splay tree

Published , updated
Tags:

The splay tree is a type of self-adjusting binary search tree like the red-black tree. What makes the splay tree special is its ability to access recently accessed elements faster. Whenever an operation is performed, the tree performs an operation called splaying which pulls the element to the top of the tree.

Worst case

The worst case height of a splay tree is n, this could be the case if all nodes were accessed in ascending order for example.

This makes the worst case complexity of the splay tree’s operations O(n). Since all operations also splay the tree on the node, the tree ends up roughly balancing itself, this results in a O(\log n) amortised worst case time complexity for all operations.

The splay tree is a particularly good choice as a data structure when it’s likely that the same nodes will be accessed multiple times in a short period. This is where the real power in the splay tree lies, in its ability to hoist nodes up to the root when they are accessed, giving speedy access for nearby successive accesses.

This article assumes knowledge of the binary search tree (BST) data structure.

Complexity

Operation Description Complexity
Delete Deletes a node given a key O(\log n)*
Insert Inserts a node with an associated key O(\log n)*
Search Searches for and returns a node using its key O(\log n)*
Splay Reorganises the tree, moving a particular node to the top O(\log n)*

* Amortised

Representation

There are two main ways of representing a binary tree. The first is using node objects that have references to their children.

Tree representation

The second is using a regular array and manipulating the index of the node to find its children. The index of the left child of a node is 2i + 1 and the index of the right is 2i + 2 where i is the index of the parent.

Array representation

The index of node's parent can also be retrieved with \lfloor(i - 1) / 2\rfloor.

Parallelism

Due to the splay tree adjusting itself even after a “read-only” operation, the splay tree is probably not ideal in a multi-threaded application. If parallelism is desired, additional guards need to be put in place to protect against race conditions.

Operations

Rotation

The generic tree rotation operation is used to perform the below splaying operations. Here is an illustration of the process.

Rotation

Splay(a)

The splay operation is performed to bring the node a that is being worked on to the root of the tree. It performs a series of operations called zig, zig-zig and zig-zag depending on the characteristics of a. Each operation has two variants depending on whether a or its parent are left or right children.

Zig(a)

This operation is performed when the parent of a is the root of the tree. A left or right rotate is performed to bring a to the root of the tree.

Zig operation

Zig-zig(a)

This operation is performed when a and its parent are the same child type as each other (both left children or both right children). It performs either two right rotations or two left rotations depending on the side. Its name is derived from the fact that the rotations performed are of the same type.

Zig-zig operation

Zig-zag(a)

This operation is performed when a is a different child type to its parent. It performs a rotation of both types (left then right, or right then left) depending on the child type of a.

Zig-zig operation
Zig-zig operation

Delete(a)

Delete can be implemented two different ways:

  • by performing a regular BST delete on the node a and then splaying the tree on what was a’s parent, or
  • by splaying the node a and then performing a regular BST delete on the a.

Insert(a)

Insert performs a regular BST insert and then splays the tree on the node a, adjusting the tree so that the inserted node is at the root of the tree.

Search(a)

Search performs a regular BST search and then splays the tree on the node a, adjusting the tree so that the searched node is at the root of the tree.

Which binary search tree is best?

The AVL tree, red-black tree and splay tree are all self-adjusting binary search trees, so which one is better in which situation? And when is it better to use a regular BST?

A paper by Ben Pfaff of Stanford University performs an in-depth study of the performance characteristics of each tree under various circumstances. Each data structure excels based on runtime patterns in the input and the calling of operations. It comes to the following conclusions:

  • Regular BSTs excel when randomly ordered input can be relied upon.
  • Splay trees excel when data is often inserted in a sorted order and later accesses are sequential or clustered.
  • AVL trees excel when data is often inserted in a sorted order and later accesses are random.
  • Red-black trees excel when data is often inserted in random order but occasional runs of sorted order are expected.

Code

public class SplayTree<T extends Comparable<T>> {

    private SplayTreeNode<T> root;

    public SplayTree() { }

    private void splay(SplayTreeNode<T> node) {
        while (node.parentExists()) {
            SplayTreeNode parent = node.getParent();
            if (!parent.parentExists()) {
                if (parent.getLeft() == node) {
                    rotateRight(parent);
                } else {
                    rotateLeft(parent);
                }
            } else {
                SplayTreeNode gparent = parent.getParent();
                if (parent.getLeft() == node && gparent.getLeft() == parent) {
                    rotateRight(gparent);
                    rotateRight(node.getParent());
                } else if (parent.getRight() == node &&
                        gparent.getRight() == parent) {
                    rotateLeft(gparent);
                    rotateLeft(node.getParent());
                } else if (parent.getLeft() == node &&
                        gparent.getRight() == parent) {
                    rotateRight(parent);
                    rotateLeft(node.getParent());
                } else {
                    rotateLeft(parent);
                    rotateRight(node.getParent());
                }
            }
        }
    }

    private void rotateLeft(SplayTreeNode<T> x) {
        SplayTreeNode y = x.getRight();
        x.setRight(y.getLeft());
        if (y.getLeft() != null) {
            y.getLeft().setParent(x);
        }
        y.setParent(x.getParent());
        if (x.getParent() == null) {
            root = y;
        } else {
            if (x == x.getParent().getLeft()) {
                x.getParent().setLeft(y);
            } else {
                x.getParent().setRight(y);
            }
        }
        y.setLeft(x);
        x.setParent(y);
    }

    private void rotateRight(SplayTreeNode<T> x) {
        SplayTreeNode y = x.getLeft();
        x.setLeft(y.getRight());
        if (y.getRight() != null) {
            y.getRight().setParent(x);
        }
        y.setParent(x.getParent());
        if (x.getParent() == null) {
            root = y;
        } else {
            if (x == x.getParent().getLeft()) {
                x.getParent().setLeft(y);
            } else {
                x.getParent().setRight(y);
            }
        }
        y.setRight(x);
        x.setParent(y);
    }

    public void insert(T key) {
        if (root == null) {
            root = new SplayTreeNode(key, null);
            return;
        }

        insert(key, root);
        search(key);
    }

    private void insert(T key, SplayTreeNode<T> node) {
        if (key.compareTo( node.getKey() ) < 0) {
            if (node.leftExists()) {
                insert(key, node.getLeft());
            } else {
                node.setLeft(new SplayTreeNode(key, node));
            }
        }

        if (key.compareTo(node.getKey())>0) {
            if (node.rightExists()) {
                insert(key, node.getRight());
            } else {
                node.setRight(new SplayTreeNode(key, node));
            }
        }
    }

    public void delete(T key) {
        if (root == null) {
            return;
        }

        search(key);
        delete(key, root);
    }

    private void delete(T key, SplayTreeNode<T> node) {
        if (key.compareTo(node.getKey())< 0) {
            if (node.leftExists()) {
                delete(key, node.getLeft());
            }
            if (node.getLeft().isDeleted()) {
                node.setLeft(null);
            }
            return;
        }

        if (key.compareTo(node.getKey()) > 0) {
            if (node.rightExists()) {
                delete(key, node.getRight());
            }
            if (node.getRight().isDeleted()) {
                node.setRight(null);
            }
            return;
        }

        delete(node);
    }

    private void delete(SplayTreeNode<T> node) {
        if (!(node.leftExists() || node.rightExists())) {
            node.setDeleted(true);
            return;
        }

        if (node.leftExists() && !node.rightExists()) {
            node.setKey(node.getLeft().getKey());
            if (node.getLeft().rightExists()) {
                node.setRight(node.getLeft().getRight());
            }
            if (node.getLeft().leftExists()) {
                node.setLeft(node.getLeft().getLeft());
            } else {
                node.setLeft(null);
            }
            return;
        }

        if (node.rightExists() && !node.leftExists()) {
            node.setKey(node.getRight().getKey());
            if (node.getRight().leftExists()) {
                node.setLeft(node.getLeft().getLeft());
            }
            if (node.getRight().rightExists()) {
                node.setRight(node.getLeft().getRight());
            } else {
                node.setRight(null);
            }
            return;
        }

        // both exist, replace with minimum from right sub-tree
        T min = findMin(node.getRight());
        node.setKey(min);
    }

    private T findMin(SplayTreeNode<T> node) {
        if (!node.leftExists()) {
            node.setDeleted(true);
            return node.getKey();
        }

        T min = findMin(node.getLeft());
        if (node.getLeft().isDeleted()) {
            node.setLeft(null);
        }
        return min;
    }

    public boolean search(T key) {
        if (root == null) {
            return false;
        }

        SplayTreeNode<T> node = search(key, root);
        splay(node);
        return node != null;
    }

    private SplayTreeNode<T> search(T key, SplayTreeNode<T> node) {
        if (key == node.getKey()) {
            return node;
        }

        if (key.compareTo(node.getKey()) < 0) {
            if (!node.leftExists()) {
                return null;
            }
            return search(key, node.getLeft());
        }

        if (key.compareTo(node.getKey()) > 0) {
            if (!node.rightExists()) {
                return null;
            }
            return search(key, node.getRight());
        }

        return null;
    }

    public String toString() {
        return root.toString();
    }

}



public class SplayTreeNode<T extends Comparable<T>> {

    private final String nullNodeString = "_";
    private SplayTreeNode<T> left;
    private SplayTreeNode<T> right;
    private SplayTreeNode<T> parent;

    private T key;
    private boolean isDeleted = false;

    public SplayTreeNode(T key, SplayTreeNode<T> parent) {
        this.key = key;
        this.parent = parent;
    }

    @Override
    public String toString() {
        return key + " : { " +
                (leftExists() ? left.toString() : nullNodeString) + " , " +
                (rightExists() ? right.toString() : nullNodeString) + " }";
    }

    public boolean leftExists() {
        return left != null;
    }

    public boolean rightExists() {
        return right != null;
    }

    public boolean parentExists() {
        return parent != null;
    }

    public T getKey() {
        return key;
    }

    public void setKey(T key) {
        this.key = key;
    }

    public SplayTreeNode<T> getLeft() {
        return left;
    }

    public void setLeft(SplayTreeNode<T> left) {
        this.left = left;
    }

    public SplayTreeNode<T> getRight() {
        return right;
    }

    public void setRight(SplayTreeNode<T> right) {
        this.right = right;
    }

    public boolean isDeleted() {
        return isDeleted;
    }

    public void setDeleted(boolean isDeleted) {
        this.isDeleted = isDeleted;
    }

    public SplayTreeNode<T> getParent() {
        return parent;
    }

    public void setParent(SplayTreeNode<T> parent) {
        this.parent = parent;
    }

}
// file: splay-tree.js

var BaseBinaryTree = require('./base-binary-tree');
var BinaryTreeNode = require('./binary-tree-node');

/**
 * Creates a splay tree.
 *
 * @constructor
 * @param {function} customCompare An optional custom node comparison
 * function.
 */
var SplayTree = function (customCompare) {
  BaseBinaryTree.call(this);

  this.nodeCount = 0;

  if (customCompare) {
    this.compare = customCompare;
  }
};

SplayTree.prototype = Object.create(BaseBinaryTree.prototype);

SplayTree.prototype.constructor = SplayTree;

/**
 * Adds a key to the tree.
 *
 * @param {Object} key The key to add.
 * @return {boolean} Whether the node was added.
 */
SplayTree.prototype.add = function (key) {
  if (!this.root) {
    this.root = new BinaryTreeNode(key);
    this.nodeCount++;
    return true;
  }

  var wasAdded = insertInternal(this, key, this.root);
  this.contains(key);
  return wasAdded;
};

/**
 * Determines whether the tree contains a key.
 *
 * @param {Object} key The key to check.
 * @return {boolean} Whether the node contains the key.
 */
SplayTree.prototype.contains = function (key) {
  if (!this.root) {
    return false;
  }

  var node = containsInternal(this, key, this.root);
  if (node) {
    splay(this, node);
  }
  return !!node;
};

/**
 * @return {Object} The maximum key of the tree.
 */
SplayTree.prototype.findMaximum = function () {
  if (!this.root) {
    return undefined;
  }

  var current = this.root;
  while (true) {
    if (current.right) {
      current = current.right;
    } else {
      return current.key;
    }
  }
};

/**
 * @return {Object} The minimum key of the tree.
 */
SplayTree.prototype.findMinimum = function () {
  if (!this.root) {
    return undefined;
  }

  var current = this.root;
  while (true) {
    if (current.left) {
      current = current.left;
    } else {
      return current.key;
    }
  }
};

/**
 * @return {boolean} Whether the tree is empty.
 */
SplayTree.prototype.isEmpty = function () {
  return !this.root;
};

/**
 * Removes a key from the tree.
 *
 * @param {Object} key The key to remove.
 * @return {boolean} Whether the key was removed.
 */
SplayTree.prototype.remove = function (key) {
  if (!this.root) {
    return false;
  }

  this.contains(key);
  return removeInternal(this, key, this.root);
};

/**
 * @return The size of the tree.
 */
SplayTree.prototype.size = function () {
  return this.nodeCount;
};

/**
 * Compares two nodes with each other.
 *
 * @param {Object} a The first key to compare.
 * @param {Object} b The second key to compare.
 * @return -1, 0 or 1 if a < b, a == b or a > b respectively.
 */
SplayTree.prototype.compare = function (a, b) {
  if (a > b) {
    return 1;
  }
  if (a < b) {
    return -1;
  }
  return 0;
};

/**
 * Rotates a node in a tree left.
 *
 *     a                             b
 *    / \                           / \
 *   c   b   -> rotateLeft(a) ->   a   e
 *      / \                       / \
 *     d   e                     c   d
 *
 * @param {SplayTree} tree The splay tree.
 * @param {BinaryTreeNode} x The node being rotated.
 */
function rotateLeft(tree, x) {
  var y = x.right;
  x.right = y.left;
  if (y.left) {
    y.left.parent = x;
  }
  y.parent = x.parent;
  if (!x.parent) {
    tree.root = y;
  } else {
    if (x === x.parent.left) {
      x.parent.left = y;
    } else {
      x.parent.right = y;
    }
  }
  y.left = x;
  x.parent = y;
}

/**
 * Rotates a node in a tree right.
 *
 *       b                          a
 *      / \                        / \
 *     a   e -> rotateRight(b) -> c   b
 *    / \                            / \
 *   c   d                          d   e
 *
 * @param {SplayTree} tree The splay tree.
 * @param {BinaryTreeNode} x The node being rotated.
 */
function rotateRight(tree, x) {
  var y = x.left;
  x.left = y.right;
  if (y.right) {
    y.right.parent = x;
  }
  y.parent = x.parent;
  if (!x.parent) {
    tree.root = y;
  } else {
    if (x === x.parent.left) {
      x.parent.left = y;
    } else {
      x.parent.right = y;
    }
  }
  y.right = x;
  x.parent = y;
}

/**
 * Inserts a key into the tree rooted on a particular node.
 *
 * @param {SplayTree} tree The tree to insert into.
 * @param {Object} key The key to insert.
 * @param {BinaryTreeNode} mode The tree's node to insert until.
 */
function insertInternal(tree, key, node) {
  if (tree.compare(key, node.key) < 0) {
    if (node.left) {
      return insertInternal(tree, key, node.left);
    } else {
      node.left = new BinaryTreeNode(key, node);
      tree.nodeCount++;
      return true;
    }
  }

  if (tree.compare(key, node.key) > 0) {
    if (node.right) {
      return insertInternal(tree, key, node.right);
    } else {
      node.right = new BinaryTreeNode(key, node);
      tree.nodeCount++;
      return true;
    }
  }

  return false;
}

function containsInternal(tree, key, node) {
  if (key === node.key) {
    return node;
  }

  if (tree.compare(key, node.key) < 0) {
    if (!node.left) {
      return undefined;
    }
    return containsInternal(tree, key, node.left);
  }

  if (tree.compare(key, node.key) > 0) {
    if (!node.right) {
      return undefined;
    }
    return containsInternal(tree, key, node.right);
  }

  return undefined;
}

function removeInternal(tree, key, node) {
  if (tree.compare(key, node.key) < 0) {
    if (node.left) {
      return removeInternal(tree, key, node.left);
    }
    return false;
  }

  if (tree.compare(key, node.key) > 0) {
    if (node.right) {
      return removeInternal(tree, key, node.right);
    }
    return false;
  }

  return removeInternal2(tree, node);
}

function removeInternal2(tree, node) {
  if (!node.left && !node.right) {
    removeNodeWithNoChildren(tree, node);
    return true;
  }

  if (node.left && !node.right) {
    removeNodeWithLeftOnly(tree, node);
    return true;
  }

  if (node.right && !node.left) {
    removeNodeWithRightOnly(tree, node);
    return true;
  }

  // both exist, replace with node minimum from right sub-tree and delete the
  // node from the right sub-tree
  var minParent = findParentOfMinimum(node.right, node);
  var minNode = minParent.left ? minParent.left : minParent.right;
  var newKey = minNode.key;
  removeInternal2(tree, minNode);
  node.key = newKey;

  return true;
}

/**
 * Removes a node with no children.
 *
 * @param {SplayTree} tree The tree to remove the node from.
 * @param {BinaryTreeNode} node The node to remove.
 */
function removeNodeWithNoChildren(tree, node) {
  if (node.parent) {
    node.parent.removeChild(node);
  } else {
    tree.root = undefined;
  }
  tree.nodeCount--;
}

/**
 * Removes a node with a left child only, moving the left child in to the
 * node's place.
 *
 * @param {SplayTree} tree The tree to remove the node from.
 * @param {BinaryTreeNode} node The node to remove.
 */
function removeNodeWithLeftOnly(tree, node) {
  node.key = node.left.key;
  node.right = node.left.right;
  if (node.right) {
    node.right.parent = node;
  }
  node.left = node.left.left;
  if (node.left) {
    node.left.parent = node;
  }
  tree.nodeCount--;
}

/**
 * Removes a node with a right child only, moving the right child in to the
 * node's place.
 *
 * @param {SplayTree} tree The tree to remove the node from.
 * @param {BinaryTreeNode} node The node to remove.
 */
function removeNodeWithRightOnly(tree, node) {
  node.key = node.right.key;
  node.left = node.right.left;
  if (node.left) {
    node.left.parent = node;
  }
  node.right = node.right.right;
  if (node.right) {
    node.right.parent = node;
  }
  tree.nodeCount--;
}

/**
 * Splay the tree on a node, bringing it to the root using a series of
 * rotation operations.
 *
 * @param {SplayTree} tree The tree being splayed.
 * @param {BinaryTreeNode} node The node being splayed on.
 */
function splay(tree, node) {
  while (node.parent) {
    var parent = node.parent;
    if (!parent.parent) {
      if (parent.left === node) {
        rotateRight(tree, parent);
      } else {
        rotateLeft(tree, parent);
      }
    } else {
      var gparent = parent.parent;
      if (parent.left === node && gparent.left === parent) {
        rotateRight(tree, gparent);
        rotateRight(tree, node.parent);
      } else if (parent.right === node && gparent.right === parent) {
        rotateLeft(tree, gparent);
        rotateLeft(tree, node.parent);
      } else if (parent.left === node && gparent.right === parent) {
        rotateRight(tree, parent);
        rotateLeft(tree, node.parent);
      } else {
        rotateLeft(tree, parent);
        rotateRight(tree, node.parent);
      }
    }
  }
}

/**
 * @return {BinaryTreeNode} The parent of the minimum key node in the tree.
 */
function findParentOfMinimum(node, parent) {
  if (!node.left) {
    return parent;
  }

  return findParentOfMinimum(node.left, node);
}

module.exports = SplayTree;



// file: base-binary-tree.js

/**
 * Creates a base binary tree.
 * @constructor
 */
var BaseBinaryTree = function () {
  /**
   * The root of the tree.
   * @protected
   */
  this.root = undefined;
};

/**
 * Performs a pre-order traversal, calling a function on each node.
 *
 * @param {function} visit A function that takes a node's key.
 */
BaseBinaryTree.prototype.traversePreOrder = function (visit) {
  if (!this.root) {
    return;
  }

  var parentStack = [];
  parentStack.push(this.root);
  do {
    var top = parentStack.pop();
    visit(top.key);
    if (top.right) {
      parentStack.push(top.right);
    }
    if (top.left) {
      parentStack.push(top.left);
    }
  } while (parentStack.length);
};

/**
 * Performs a in-order traversal, calling a function on each node.
 *
 * @param {function} visit A function that takes a node's key.
 */
BaseBinaryTree.prototype.traverseInOrder = function (visit) {
  var parentStack = [];
  var node = this.root;
  while (parentStack.length || node) {
    if (node) {
      parentStack.push(node);
      node = node.left;
    } else {
      node = parentStack.pop();
      visit(node.key);
      node = node.right;
    }
  }
};

/**
 * Performs a post-order traversal, calling a function on each node.
 *
 * @param {function} visit A function that takes a node's key.
 */
BaseBinaryTree.prototype.traversePostOrder = function (visit) {
  var parentStack = [];
  var node = this.root;
  var lastVisitedNode;
  while (parentStack.length || node) {
    if (node) {
      parentStack.push(node);
      node = node.left;
    } else {
      var nextNode = parentStack[parentStack.length - 1];
      if (nextNode.right && lastVisitedNode !== nextNode.right) {
        // if right child exists AND traversing node from left child, move
        // right
        node = nextNode.right;
      } else {
        parentStack.pop();
        visit(nextNode.key);
        lastVisitedNode = nextNode;
      }
    }
  }
};

module.exports = BaseBinaryTree;



// file: binary-tree-node.js

/**
 * Creates a binary tree node.
 *
 * @constructor
 * @param {Object} key The key of the node.
 * @param {BinaryTreeNode} parent The parent of the node.
 */
function BinaryTreeNode(key, parent) {
  /**
   * The key of the node.
   * @public
   */
  this.key = key;

  /**
   * The parent of the node.
   * @public
   */
  this.parent = parent;

  /**
   * The left child of the node.
   * @public
   */
  this.left = undefined;

  /**
   * The right child of the node.
   * @public
   */
  this.right = undefined;
}

/**
 * Removes a child from the node. This will remove the left or right node
 * depending on which one matches the argument.
 *
 * @param {Object} node The node to remove.
 */
BinaryTreeNode.prototype.removeChild = function (node) {
  if (this.left === node) {
    this.left = undefined;
  }
  if (this.right === node) {
    this.right = undefined;
  }
};

module.exports = BinaryTreeNode;

Textbooks

Here are two CS textbooks I personally recommend; the Algorithm Design Manual (Steven S. Skiena) is a fantastic introduction to data structures and algorithms without getting to deep into the maths side of things, and Introduction to Algorithms (CLRS) which provides a much deeper, math heavy look.

 

Comments

comments powered by Disqus
Like this article?
Subscribe for more!