Operaciones

La idea principal del splay tree es que el nodo que acaba de accederse debe quedar en la raíz del árbol. Para ello, una vez accedido un nodo $x$, éste se lleva a la raíz mediante una operación llamada $splay(x)$. Esta operación está formada por una secuencia de rotaciones. Para describirlas, usaremos el formato $z(A,B)$ para indicar un árbol con el elemento $z$ en la raíz, subárbol izquierdo $A$ y subárbol derecho $B$. Las rotaciones para ir subiendo al nodo $x$ son las siguientes:

• Zig-zig: $z(y(x(A,B),C),D) \rightarrow x(A,y(B,z(C,D)))$.
• Zig-zag: $z(y(A,x(B,C)),D) \rightarrow x(y(A,B),z(C,D))$.
• Zag-zig: $z(A,y(x(B,C),D)) \rightarrow x(z(A,B),y(C,D))$.
• Zag-zag: $z(A,y(B,x(C,D))) \rightarrow x(y(z(A,B),C),D)$.
• Zig: $y(x(A,B),C) \rightarrow x(A,y(B,C))$ (sólo si $y$ es raíz).
• Zag: $y(A,x(B,C)) \rightarrow (x(y(A,B),C)$ (sólo si $y$ es raíz).

--> imagenes

Supondremos que las rotaciones dobles cuestan 2 unidades de trabajo y las simples cuestan 1. Las operaciones del árbol se realizan de la siguiente manera:

Buscar

Se busca $x$ como en un árbol binario de búsqueda y luego se hace $splay(x)$. Si $x$ no se encuentra, se hace $splay(x')$, donde $x'$ es el último nodo visitado.

Insertar

Se inserta $x$ como en un árbol binario de búsqueda y luego se hace $splay(x)$.

Borrar

Se borra $x$ como en un árbol binario de búsqueda (es decir, si tiene dos hijos se reemplaza por su sucesor o predecesor in-order), y luego se hace $splay(x')$, donde $x'$ es el padre del nodo finalmente borrado (aquel sucesor o predecesor in-order de $x$).