A splay tree is a self-balancing binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in logarithmic time.
A splay tree is a binary tree that satisfies the following invariant:
The following figure shows an example of a splay tree:
Splay trees are self-balancing, meaning that the tree adjusts itself so that the most recently accessed elements are quick to access again. This is done by moving the accessed element to the root of the tree.
The following operations are supported by splay trees:
All of these operations are performed in logarithmic time.
Insertion into a splay tree is similar to insertion into a binary search tree. First, we find the correct position for the new element by traversing the tree. Then, we insert the new element into the tree.
However, after insertion, we need to splay the new element to the root. This is done by a series of tree rotations.
The following figure shows an example of insertion into a splay tree:
Look-up in a splay tree is similar to look-up in a binary search tree. First, we find the element that we are looking for by traversing the tree. Then, we return the element.
However, after look-up, we need to splay the element to the root. This is done by a series of tree rotations.
The following figure shows an example of look-up in a splay tree:
Removal from a splay tree is similar to removal from a binary search tree. First, we find the element that we want to remove by traversing the tree. Then, we remove the element.
However, after removal, we need to splay the parent of the removed element to the root. This is done by a series of tree rotations.
The following figure shows an example of removal from a splay tree:
A splay tree can be implemented as a binary search tree. The following pseudo-code shows an example of how to insert an element into a splay tree:
insert(x, t)
if t is empty
return new node with value x
if x < t.value
t.left = insert(x, t.left)
else
t.right = insert(x, t.right)
return t
The following pseudo-code shows an example of how to look-up an element in a splay tree:
lookup(x, t)
if t is empty
return null
if x < t.value
return lookup(x, t.left)
else if x > t.value
return lookup(x, t.right)
else
return t
The following pseudo-code shows an example of how to remove an element from a splay tree:
remove(x, t)
if t is empty
return null
if x < t.value
t.left = remove(x, t.left)
else if x > t.value
t.right = remove(x, t.right)
else
t = remove(t)
return t
remove(t)
if t.left is empty and t.right is empty
return null
if t.left is empty
return t.right
if t.right is empty
return t.left
y = t.right
while y.left is not empty
y = y.left
t.right = remove(y.value, t.right)
y.left = t.left
y.right = t.right
return y
The time complexity of the operations supported by splay trees is as follows:
The space complexity of a splay tree is O(n), where n is the number of elements in the tree.