Splay Tree Review

Link-Cut trees use splay trees internally. Quick review:

A splay tree is a self-balancing BST where every access moves the accessed node to the root via rotations.

function splay(x)
    while x is not root
        p := parent of x
        g := parent of p (grandparent)
        if g exists then
            if (x is left child) = (p is left child) then
                rotate(p)  // zig-zig
            else
                rotate(x)  // zig-zag
        rotate(x)

Splay trees have $O(\log n)$ amortized time for all operations. The splaying makes recently accessed nodes fast to access again.