Splay Tree

Páginas: 3 (720 palabras) Publicado: 26 de agosto de 2011
Arboles biselados o 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...
Leer documento completo

Regístrate para leer el documento completo.

Estos documentos también te pueden resultar útiles

  • Treas
  • trea
  • Treas
  • tree
  • Trea
  • tree
  • trea
  • la trea

Conviértase en miembro formal de Buenas Tareas

INSCRÍBETE - ES GRATIS