Splay Tree
Los arboles biselados (inglés: splay tree) son árboles binarios de búsqueda que ofrecen en tiempo O(log n) en las operaciones de búsqueda, inserción y eliminación deun nodo. En un árbol biselado cada vertice contiene a una clave y las claves en el ramo izquierdo son menores que la clave del vértice mismo, mientras a la derecha están las claves mayores. Las clavesson unicas.
Operación Splay
La idea básica es que después de acceder a un nodo éste se lleva a la raíz mediante rotaciones. En cada operación splay se hace ascender al nodo en uno o dos niveles,dependiendo de su orientación relativa respecto de su nodo abuelo. Un splay mueve el elemento recuperado a la raíz del árbol. Así, un splay hace que: Todos los nodos accedidos durante una consultaluego sean mucho menos costosos de acceder. Todos los demás nodos no accedidos, su consulta se empeora sólo un poco.
Metodo Splay
void splay (struct node *x, struct node *root) { node *p,*g; / *Comprobar si el nodo x es el nodo raíz * / if(x==root) return; / * Realiza el paso Zig* / else if(x->parent==root) { if(x==(x->parent)->left) rightrotation(root); else leftrotation(root); } else {p=x->parent; /*ahora apunta a los padres de x*/ g=p->parent; /*ahora apunta a los padres de los padres de x*/ /*Realiza paso Zig-Zig*/ if(x==p->left&&p==g->left) { rightrotation(g); rightrotation(p); }/*Realiza paso Zag-Zag*/ else if(x==p->right&&p==g->right) { leftrotation(g); leftrotation(p); } /*Realiza paso Zig-Zag*/ else if(x==p->right&&p==g->left) { leftrotation(p); rightrotation(g); }/*Realiza paso Zag-Zig*/ else if(x==p->left&&p==g->right) { rightrotation(p); leftrotation(g); } splay(x, root); } }
Ejemplo: splay(1,S), con S el árbol degenerado
Splay(2,S)
Para hacer splay enun nodo x, repetimos los siguientes pasos hasta que x sea la raíz del árbol: Caso Zig: si x es un hijo izquierdo de la raíz del árbol, rotar x a derecha y terminar.
Caso Zag: si x es un hijo...
Regístrate para leer el documento completo.