The splay tree was developed by Daniel Dominic Sleator and Robert Endre Tarjan in 1985. A Splay Tree is a self-adjusting binary search tree data structure that automatically reorganizes itself to optimize access times for frequently accessed elements by moving them closer to the root. It accomplishes this by performing a splay operation after every search, insert, or delete operation, bringing the accessed node to the root of the tree.
Splay Trees use rotations to perform the splay operation and bring the accessed node to the root.
procedure splayInsert(root, key):
if root is null:
// Create a new node with the given key and make it the root
root = createNode(key)
else:
// Perform a normal BST insertion
root = bstInsert(root, key)
// Splay the newly inserted node to the root
root = splay(root, key)
function bstInsert(node, key):
// Standard BST insertion procedure
if node is null:
return createNode(key)
if key < node.key:
node.left = bstInsert(node.left, key)
else if key > node.key:
node.right = bstInsert(node.right, key)
return node
function splay(root, key):
if root is null or root.key == key:
return root
// Key is in the left subtree
if key < root.key:
// Key is not in the tree, return the unchanged root
if root.left is null:
return root
// Zig-Zig step: Left-left case
if key < root.left.key:
root.left.left = splay(root.left.left, key)
root = rightRotate(root)
// Zig-Zag step: Left-right case
else if key > root.left.key:
root.left.right = splay(root.left.right, key)
if root.left.right is not null:
root.left = leftRotate(root.left)
// Perform a final rotation to bring the key to the root
if root.left is not null:
root = rightRotate(root)
return root
// Key is in the right subtree
else:
// Key is not in the tree, return the unchanged root
if root.right is null:
return root
// Zig-Zig step: Right-right case
if key > root.right.key:
root.right.right = splay(root.right.right, key)
root = leftRotate(root)
// Zig-Zag step: Right-left case
else if key < root.right.key:
root.right.left = splay(root.right.left, key)
if root.right.left is not null:
root.right = rightRotate(root.right)
// Perform a final rotation to bring the key to the root
if root.right is not null:
root = leftRotate(root)
return root
function rightRotate(node):
// Right rotation operation
newRoot = node.left
node.left = newRoot.right
newRoot.right = node
return newRoot
function leftRotate(node):
// Left rotation operation
newRoot = node.right
node.right = newRoot.left
newRoot.left = node
return newRoot
procedure splayDelete(root, key):
if root is null:
// Key not found, return the unchanged root
return root
// Splay the node containing the key to the root
root = splay(root, key)
// After splaying, if the key is not at the root, it's not in the tree
if key != root.key:
return root
// Perform the actual deletion
if root.left is null:
return root.right
else:
// Find the maximum node in the left subtree
maxNode = findMax(root.left)
// Splay the maximum node to the root of the left subtree
root.left = splay(root.left, maxNode.key)
// Attach the right subtree as the right child of the maximum node
maxNode.right = root.right
return maxNode
function findMax(node):
// Find the maximum node in a subtree
while node.right is not null:
node = node.right
return node
function splaySearch(root, key):
if root is null:
// Key not found, return null or a sentinel value
return null
// Start searching from the root
while root is not null:
if key == root.key:
// Key found, splay the node to the root
return splay(root, key)
else if key < root.key:
// Key is in the left subtree
if root.left is null:
// Key not found, splay the last accessed node (root)
return splay(root, key)
// Continue searching in the left subtree
root = root.left
else:
// Key is in the right subtree
if root.right is null:
// Key not found, splay the last accessed node (root)
return splay(root, key)
// Continue searching in the right subtree
root = root.right
// Key not found, return null or a sentinel value
return null