Arboles Splay

1

Capítulo 13

Árboles Desplegados. Splay Trees.
13.1 Definición.
Es un árbol de búsqueda autoorganizado que emplea rotaciones para mover cualquier clave
accesada, ya sea en búsqueda, inserción o descarte, a la raíz.
Esto deja a los nodos más recientemente accesados cerca de la raíz, haciendo que la posterior
búsqueda de ellos sea eficiente.
No se requiere almacenar informaciónadicional en el nodo, ya sea el factor de balance (AVL), o
el color en árboles coloreados, o un puntero adicional en árboles 2-3.
La forma del árbol va variando de acuerdo a los nodos que son más recientemente accesados.
Fueron desarrollados por Sleator y Tarjan in 1985, en la publicación del ACM Journal, “Selforganizing Binary Search Trees” como una alternativa a los algoritmos que mantienenbalanceado un árbol binario de búsqueda.
La heurística es similar a la empleada en listas autoorganizadas, en las cuales los elementos
buscados se van colocando más cerca del inicio de la lista. Una opción conservadora, es
adelantar en una posición, el elemento buscado, cada vez que hay un acceso a esa clave; otra,
más enérgica, es llevar el elemento al inicio de la lista. Puede comprobarse que moveral frente
tiene un mejor comportamiento, en caso de distribuciones de búsqueda que cambian.
Si algo ha sido accesado, es muy probable que sea nuevamente accesado.
En el caso de los árboles splay se lleva el elemento buscado o insertado a la posición de la raíz.
En la búsqueda o la inserción bottom-up, se realiza un recorrido desde la raíz hasta encontrar el
elemento buscado; o bien hastaencontrar una hoja, en caso de inserción. Luego de lo anterior se
realiza una operación splay para mover el elemento a la posición de la raíz.

13.2 Operación splay.
La operación splay, consiste de una secuencia de dobles rotaciones, hasta que el nodo quede a
un nivel debajo de la raíz; en este caso basta una rotación simple para completar la operación.
En cada operación splay se hace ascenderal nodo en uno o dos niveles, dependiendo de su
orientación relativa respecto de su nodo abuelo.

Profesor Leopoldo Silva Bijit

20-01-2010

2

Estructuras de Datos y Algoritmos

Hay tres casos:
Zig: el nodo es un hijo izquierdo o derecho (Zag) de la raíz. Sin abuelo.
Zig-Zag: El nodo es un hijo izquierdo de un hijo derecho; o un hijo derecho de un hijo izquierdo
(Zag-Zig).Zig-zig: El nodo es un hijo izquierdo de un hijo izquierdo; o un hijo derecho de un hijo derecho
(Zag-Zag).
Gráficamente:

y

x

Zig.

x

C

y
A

A

B

B

C

Figura 13.1. Operación Zig.
Si t apunta al padre de x, la rotación simple, en este caso, se logra con: t=rrot(t);
Se rota el padre de x, a la derecha.
Pasar de la figura de la derecha hacia la de la izquierda se denominaZag, y la operación que la
logra es: t=lrot(t).
Zig-Zig
x

z
y

y

A

D

z

x
B

C
A

C

B

D

Figura 13.2. Operación Zig-Zig.
Si inicialmente t apunta al abuelo de x. Se rota el abuelo de x, y luego el padre del nodo x.
Se logra con la secuencia :
t=rrot(t);
t=rrot(t);
Pasar de la figura derecha a la izquierda, el ascenso de z a la raíz se denomina Zag-zag.Zig-Zag.

z

x

y

D

z

y

x

A

A
B

B C

C

Figura 13.3. Operación Zig-Zag.

Profesor Leopoldo Silva Bijit

20-01-2010

D

Árboles desplegados. Splay trees.

3

Se rota el padre de x a la izquierda, y luego se rota el nuevo padre de x a la derecha. La imagen
especular se denomina Zag-Zig.
Mover a la raíz.
Debe notarse que mover un nodo hacia la raíz,siguiendo en forma inversa la trayectoria de
búsqueda desde a raíz hasta el nodo, no es enteramente equivalente a las dobles rotaciones
propuestas en árboles splay. Las operaciones Zig, Zag, Zig-Zag y Zag-Zig, son equivalentes a
las que produce el mover hacia la raíz; la diferencia está en las operaciones Zig-Zig y Zag-Zag.
En el caso de mover hacia la raíz, se rota el padre de x a la derecha y...