Arboles Splay

DIEGO RAFAEL ROMERO
200914939
UNIVERSIDAD DE SAN CARLOS DE GUATEMALA

DICIEMBRE 2013
ESTRUCTURA DE DATOS

Árboles Splay
Son árboles Binarios de Búsqueda Equilibrados, que mantienen el balance sin necesidad de añadir
propiedades (campos adicionales) a los nodos para verificar las condiciones de equilibrio. Utilizan
"operaciones splay", que como se verá a continuación se basanexclusivamente en rotaciones.
Operaciones Básicas: Splay
La idea del esplayado (splay) de un nodo consiste en llevar el nodo a la raíz a través de rotaciones.
Supongamos que deseamos hacer splay sobre un nodo X de un árbol; existen 3 casos posibles:

Rotación Zig: El padre de X es la raíz, es el caso más sencillo, se realiza una rotación simple a la izquierda
o derecha, según sea el caso:

rotacionzig

Rotación Zig-Zig: El padre de X no es la raíz y X y PADRE(X) son ambos hijos izquierdos (o ambos hijos
derechos). Se realiza en dos pasos: primero se rota PADRE(X) hasta llevarlo a la raíz, y luego se rota X.

rotacion zig-zig

DIEGO RAFAEL ROMERO
200914939
UNIVERSIDAD DE SAN CARLOS DE GUATEMALA

DICIEMBRE 2013
ESTRUCTURA DE DATOS

Rotación Zig-Zag: El padre de X no es la raíz yX es hijo izquierdo (derecho) y PADRE(X) es hijo derecho
(izquierdo). Se realiza en dos pasos: primero se rota X hasta llevarlo a la posición de su padre, y luego
hasta llevarlo a la raíz.

rotacion zig-zag
Para completar el splay de un nodo X, se realizan repetidamente los casos anteriores, hasta llevarlo a la
raíz.

Operaciones Básicas: Inserción
Se inserta como en un ABB y luego seaplica splay al nodo insertado.
arbol insertar(tipoclave valor, arbol t)
{
arbol p;
NodoInsercion = CreaNodo(valor); /* Crea el nodo y pega en la global */

// p=splayBU(valor, t, Root); /* Si no lo encuentra, lo inserta y lo coloca en la raíz */
p=splayTD(valor, t); /* Si no lo encuentra, lo inserta y lo coloca en la raíz */
if (NodoInsercion != NULL) { /* Si ya estaba, libera el nodo */Operaciones Básicas: Búsqueda

DIEGO RAFAEL ROMERO
200914939
UNIVERSIDAD DE SAN CARLOS DE GUATEMALA

DICIEMBRE 2013
ESTRUCTURA DE DATOS

Se busca como en un ABB y luego se aplica splay al nodo consultado. Si no se encuentra se hace splay
sobre su predecesor.
arbol buscar(tipoclave valor, arbol t)
{
arbol p;
NodoInsercion = NULL; /* */
//p=splayBU(valor, t, Root); /* si loencuentra, lo coloca en la raíz. */
p=splayTD(valor, t); /* si lo encuentra, lo coloca en la raíz. */
if(p==NULL) Error(2,valor); // Busca en árbol vacío.
return p;
}

Operaciones Básicas: Eliminación
Se busca el nodo a eliminar y se hace splay sobre el. Luego, estando en la raíz, con hijos left y right, se
elimina de la siguiente manera: se busca el mayor nodo del subárbol izquierdo y se hacesplay sobre
este. como hijo derecho de este se transforma el subárbol derecho (right).

arbol borrar(tipoclave valor, arbol t)
{
arbol p,q,r;
NodoInsercion = NULL; /* */
p=buscar(valor, t); /* si lo encuentra, lo coloca en la raíz. */
//MuestraArbol(p, 1);
if (p==NULL) return(NULL);
r=sucesor(p);
if(r!=NULL)
{q=splayTD(r->clave, p->right);
t=join(p->left,q);

DIEGO RAFAEL ROMERO200914939
UNIVERSIDAD DE SAN CARLOS DE GUATEMALA

DICIEMBRE 2013
ESTRUCTURA DE DATOS

}
else t=p->left;
LiberaNodo(p);
return(t);
}
USOS







Simulaciones en 3D, principalmente juegos, dibujan de forma eficiente los escenarios.
Tablas de enrutamiento que utilizan los routers para calcular la ruta más corta al momento de
transmitir información de un punto a otro.
Enaplicaciones de inteligencia artificial para la búsqueda de caminos. Por ejemplo, programas
que contienen información sobre una ciudad y calculan cómo llegar de una dirección a otra,
usan algoritmos de búsqueda que pueden utilizar árboles binarios.
Los compiladores crean árboles de sintaxis, que pueden ser árboles binarios.
En algoritmos de compresión, como el utilizado en el formato jpeg....