Rotations

Rotation moves a node up while maintaining BST property:

function rotateRight(x)
    // x becomes parent of its former parent
    p := x.parent
    x.parent := p.parent
    p.left := x.right
    if x.right then x.right.parent := p
    x.right := p
    p.parent := x
    // Update grandparent's child pointer

function rotateLeft(x)
    // Mirror of rotateRight
    p := x.parent
    x.parent := p.parent
    p.right := x.left
    if x.left then x.left.parent := p
    x.left := p
    p.parent := x

Rotations are $O(1)$. The splay operation does $O(\log n)$ rotations amortized.