The splay tree is 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.
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)\) amortized 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.
Complexity
| Operation | Average case | Worst case |
|---|---|---|
| Delete | \(O(\log n)\) | \(O(n)\), amortized \(O(\log n)\) |
| Insert | \(O(\log n)\) | \(O(n)\), amortized \(O(\log n)\) |
| Search | \(O(\log n)\) | \(O(n)\), amortized \(O(\log n)\) |
| Space | \(O(n)\) | \(O(n)\) |
Representation
See the BST article for information on representing a binary tree.
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.
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-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-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.
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.
Code
public class SplayTree {
private TreeNode root;
public SplayTree() { }
private void splay(TreeNode node) {
while (node.parentExists()) {
TreeNode parent = node.getParent();
if (!parent.parentExists()) {
if (parent.getLeft() == node) {
rotateRight(parent);
} else {
rotateLeft(parent);
}
} else {
TreeNode grandparent = parent.getParent();
if (parent.getLeft() == node &&
grandparent.getLeft() == parent) {
rotateRight(grandparent);
rotateRight(node.getParent());
} else if (parent.getRight() == node &&
grandparent.getRight() == parent) {
rotateLeft(grandparent);
rotateLeft(node.getParent());
} else if (parent.getLeft() == node &&
grandparent.getRight() == parent) {
rotateRight(parent);
rotateLeft(node.getParent());
} else {
rotateLeft(parent);
rotateRight(node.getParent());
}
}
}
}
private void rotateLeft(TreeNode x) {
TreeNode 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(TreeNode x) {
TreeNode 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(int key) {
if (root == null) {
root = new TreeNode(key, null);
return;
}
insert(key, root);
search(key);
}
private void insert(int key, TreeNode node) {
if (key < node.getKey()) {
if (node.leftExists())
insert(key, node.getLeft());
else
node.setLeft(new TreeNode(key, node));
}
if (key > node.getKey()) {
if (node.rightExists())
insert(key, node.getRight());
else
node.setRight(new TreeNode(key, node));
}
}
public void delete(int key) {
if (root == null)
return;
search(key);
delete(key, root);
}
private void delete(int key, TreeNode node) {
if (key < node.getKey()) {
if (node.leftExists())
delete(key, node.getLeft());
if (node.getLeft().isDeleted())
node.setLeft(null);
return;
}
if (key > node.getKey()) {
if (node.rightExists())
delete(key, node.getRight());
if (node.getRight().isDeleted())
node.setRight(null);
return;
}
delete(node);
}
private void delete(TreeNode 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
int min = findMin(node.getRight());
node.setKey(min);
}
private int findMin(TreeNode node) {
if (!node.leftExists()) {
node.setDeleted(true);
return node.getKey();
}
int min = findMin(node.getLeft());
if (node.getLeft().isDeleted())
node.setLeft(null);
return min;
}
public boolean search(int key) {
if (root == null)
return false;
TreeNode node = search(key, root);
splay(node);
return node != null;
}
private TreeNode search(int key, TreeNode node) {
if (key == node.getKey())
return node;
if (key < node.getKey()) {
if (!node.leftExists())
return null;
return search(key, node.getLeft());
}
if (key > node.getKey()) {
if (!node.rightExists())
return null;
return search(key, node.getRight());
}
return null;
}
public String toString() {
return root.toString();
}
}
Here is the TreeNode class used above.
public class TreeNode {
private final String nullNodeString = "_";
private TreeNode left;
private TreeNode right;
private TreeNode parent;
private int key;
private boolean isDeleted = false;
public TreeNode(int key, TreeNode parent) {
this.key = key;
this.parent = parent;
}
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 int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
public boolean isDeleted() {
return isDeleted;
}
public void setDeleted(boolean isDeleted) {
this.isDeleted = isDeleted;
}
public TreeNode getParent() {
return parent;
}
public void setParent(TreeNode parent) {
this.parent = parent;
}
}