Splay Tree Search

Splay tree search looks up a key in a binary search tree and then restructures the tree by moving the accessed node, or the last visited node, to the root.

This restructuring is called splaying. It improves future access to recently used keys and gives amortized logarithmic performance without storing balance metadata such as heights, colors, or priorities.

Problem

Given a splay tree with root root and a target key x, find a node such that

node.key = x

If no such node exists, return null. After the search, splay the found node or the last visited node to the root.

Algorithm

First perform ordinary BST search. Keep track of the last visited node. If the key is found, splay that node. If the key is absent, splay the last visited node.

splay_tree_search(root, x):
    node = root
    last = null

    while node != null:
        last = node

        if x == node.key:
            root = splay(root, node)
            return root

        else if x < node.key:
            node = node.left

        else:
            node = node.right

    if last != null:
        root = splay(root, last)

    return null

Splay Cases

Splaying repeatedly applies rotations until the target node becomes the root.

case	condition	operation
zig	node has parent but no grandparent	single rotation
zig-zig	node and parent are both left children or both right children	rotate parent, then node
zig-zag	node and parent go in opposite directions	rotate node twice

Example

Search for 6:

The search path is 8 -> 4 -> 6. Since 6 is found, splaying moves it to the root.

After splaying:

      6
     / \
    4   8

Correctness

The search phase follows the binary search tree ordering invariant, so it visits the only possible path where the target can appear.

The splay phase uses tree rotations. Rotations preserve in-order key order, so they preserve the binary search tree invariant. Therefore, splaying changes the shape of the tree but does not change the set of keys or their sorted order.

If the algorithm returns a node, that node has key x. If it reaches null, the target is absent from the only possible search path, so no matching key exists.

Complexity

A single operation can take linear time on a badly shaped tree. Over a sequence of operations, the amortized cost is logarithmic.

case	time
single worst case	$O(n)$
amortized	$O(\log n)$

Space complexity:

version	space
iterative search	$O(1)$
recursive splay implementation	$O(h)$

When to Use

Splay trees are useful when access patterns are nonuniform. Recently accessed keys move near the root, so repeated or clustered accesses become faster.

They are appropriate when:

locality of reference is common
explicit balance metadata is undesirable
amortized guarantees are acceptable

They are less appropriate when every single operation must have a strict worst case bound.

Implementation

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.parent = None

def rotate_right(x):
    y = x.left
    x.left = y.right

    if y.right:
        y.right.parent = x

    y.parent = x.parent

    if x.parent:
        if x.parent.left is x:
            x.parent.left = y
        else:
            x.parent.right = y

    y.right = x
    x.parent = y
    return y

def rotate_left(x):
    y = x.right
    x.right = y.left

    if y.left:
        y.left.parent = x

    y.parent = x.parent

    if x.parent:
        if x.parent.left is x:
            x.parent.left = y
        else:
            x.parent.right = y

    y.left = x
    x.parent = y
    return y

def splay(x):
    while x.parent:
        p = x.parent
        g = p.parent

        if g is None:
            if p.left is x:
                rotate_right(p)
            else:
                rotate_left(p)

        elif g.left is p and p.left is x:
            rotate_right(g)
            rotate_right(p)

        elif g.right is p and p.right is x:
            rotate_left(g)
            rotate_left(p)

        elif g.left is p and p.right is x:
            rotate_left(p)
            rotate_right(g)

        else:
            rotate_right(p)
            rotate_left(g)

    return x

def splay_tree_search(root, x):
    node = root
    last = None

    while node:
        last = node

        if x == node.key:
            return splay(node)
        elif x < node.key:
            node = node.left
        else:
            node = node.right

    if last:
        root = splay(last)

    return None

type SplayNode struct {
	Key    int
	Left   *SplayNode
	Right  *SplayNode
	Parent *SplayNode
}

func rotateRight(x *SplayNode) *SplayNode {
	y := x.Left
	x.Left = y.Right

	if y.Right != nil {
		y.Right.Parent = x
	}

	y.Parent = x.Parent

	if x.Parent != nil {
		if x.Parent.Left == x {
			x.Parent.Left = y
		} else {
			x.Parent.Right = y
		}
	}

	y.Right = x
	x.Parent = y
	return y
}

func rotateLeft(x *SplayNode) *SplayNode {
	y := x.Right
	x.Right = y.Left

	if y.Left != nil {
		y.Left.Parent = x
	}

	y.Parent = x.Parent

	if x.Parent != nil {
		if x.Parent.Left == x {
			x.Parent.Left = y
		} else {
			x.Parent.Right = y
		}
	}

	y.Left = x
	x.Parent = y
	return y
}

func Splay(x *SplayNode) *SplayNode {
	for x.Parent != nil {
		p := x.Parent
		g := p.Parent

		if g == nil {
			if p.Left == x {
				rotateRight(p)
			} else {
				rotateLeft(p)
			}
		} else if g.Left == p && p.Left == x {
			rotateRight(g)
			rotateRight(p)
		} else if g.Right == p && p.Right == x {
			rotateLeft(g)
			rotateLeft(p)
		} else if g.Left == p && p.Right == x {
			rotateLeft(p)
			rotateRight(g)
		} else {
			rotateRight(p)
			rotateLeft(g)
		}
	}

	return x
}

func SplayTreeSearch(root *SplayNode, x int) *SplayNode {
	node := root
	var last *SplayNode

	for node != nil {
		last = node

		if x == node.Key {
			return Splay(node)
		} else if x < node.Key {
			node = node.Left
		} else {
			node = node.Right
		}
	}

	if last != nil {
		return Splay(last)
	}

	return nil
}