Transcript
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ón adicional 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 mantienen balanceado 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 mover al 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 hasta encontrar 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 ascender al 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 denomina Zag, 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 luego el nuevo padre de x, a la derecha. x
z y
z
A
D
x
y
D
C A
B
B
C
Figura 13.4. Mover x hacia la raíz. Medir el efecto de estos dos tipos de rotaciones requiere un análisis de costos denominado “Análisis amortizado”. Se puede verificar que el costo amortizado de m operaciones splay sobre un árbol con n nodos, es: O( (m + n) * log2(n + m) ) Es con este fundamento que se eligen las dobles rotaciones en este tipo de árboles, y como se verá a través de ejemplos, tienden a acortar la altura del árbol.
13.3 Tipos de algoritmos. Existen dos tipos de algoritmos, bottom-up (de abajo hacia arriba) o top-down (de arriba hacia abajo). 13.3.1. Splay Bottom-up. Las operaciones de búsqueda, inserción y descarte de un nodo se efectúan en forma similar a un árbol binario de búsqueda. Luego se realiza una operación splay sobre un nodo. En búsqueda el nodo es el que contiene el valor buscado, o el padre de la hoja si no lo encuentra. En inserción, el nodo sobre el que se aplica la operación splay es el de igual valor al buscado, si ya existía; o el nuevo nodo si éste no estaba en el árbol. En bottom-up se requiere descender de la raíz hasta el nodo al que se le aplicará la operación splay. Luego se van efectuado las rotaciones a medida que se asciende. Es decir se recorre el árbol dos veces. A partir del nodo, al que se le aplicará la operación, se asciende hasta encontrar el abuelo, y se efectúa la rotación doble que corresponda; si no existe abuelo, pero sí padre, se efectúa rotación simple.
Profesor Leopoldo Silva Bijit
20-01-2010
4
Estructuras de Datos y Algoritmos
13.3.2. Ejemplos de operaciones splay bottom-up. Splay(3, root); 1
1
1
2
3
2
6
6
Zig-Zig
2
3
2
4
Zag
4
4
4
6
6
Zag-Zig
3
5
1
3
5
5
5
Figura 13.5. Operación Splay(3, root) Splay(1, root); 7
6
6
5
2
1
Zig-Zig
4
2
Zig-Zig
2
1
6
4
1
Zag-Zag
4
1
6
5
4
3
7
7
2
5
7
5
3
3
3
Figura 13.6. Operación Splay(1, root) Las operaciones tienden a disminuir la altura. La figura siguiente, muestra la operación mover el nodo con valor 1, a la raíz. Lo que permite comparar las formas de los árboles generados mediante las dos operaciones. Ver Figuras 13.6 y 13.7.
Profesor Leopoldo Silva Bijit
20-01-2010
Árboles desplegados. Splay trees.
5
MuevealaRaiz(1, root) 7
1
6
7
5
6
Mueve a la raíz 4
5
3
4
2
3
1
2
Figura 13.7. Operación Mover a la raíz. Insertar nodo con valor 5. 5 7
7
1
6
3
8 4
1
4
2
3
8
3
2
Zig-Zag
7
8
1
6
5
2
4
6
Insert(5, root) 5
7
3
4
1
Zag-Zig
5
6
8
2
Splay(5, root)
Figura 13.8. Operación Insertar(5, root) Para el diseño de descarte existen varias posibilidades. a) Proceder como en árbol binario de búsqueda, y no emplear operaciones splay, considerando que si algo se borra, no significa que se intentará buscar en la proximidad del elemento borrado. b) Si lo busca y no lo encuentra efectúa una operación splay con el padre del buscado. Si lo encuentra, efectúa operación splay sobre el nodo, dejándolo en la raíz. Luego efectúa una operación splay con el nodo con mayor clave en el subárbol izquierdo; a continuación se descarta la raíz; y finalmente se enlaza el subárbol derecho con el subárbol izquierdo. Profesor Leopoldo Silva Bijit
20-01-2010
6
Estructuras de Datos y Algoritmos
La siguiente figura ilustra la alternativa b). La operación descarte(4, root), ubica el nodo con valor 4, y lo lleva a la raíz. Luego se efectúa: splay(3, TL), se descarta el nodo con valor 4, y se efectúa la unión de dos subárboles (join). Descartar(4, root). 7
3
4
4
6
6 TL
6
2
TL
2
6
3
5
1
5
3
2
4
1
7
5 1
7
2
5
7
1
3
Figura 13.9. Operación Descartar(4, root) Descartar(6, root) 3
6
TL
1
4
Zag-zag 2
3
6 5
7
Zag
7 5
8
5
5 7
4
1 8
Splay(6, root)
6 4 8
1
8
3 1
3 2
7
LiberarRaíz
Splay(5, TL)
2
join(L,R)
2
Figura 13.10. Operación Descartar(6, root) Para tener un conjunto de operaciones que consideren las propiedades de esta estructura, se pueden definir: accesar(i, t): Si i está en el árbol t, retorna un puntero al nodo encontrado, en caso contrario retorna NULL. Busca el nodo con valor i, y efectúa splay en ese nodo; si no lo encuentra, efectúa la operación splay con el último nodo accesado buscando i.
Profesor Leopoldo Silva Bijit
20-01-2010
Árboles desplegados. Splay trees.
7
join (L, R): Retorna árbol formado por la combinación del árbol L y el árbol R, asumiendo que todos los ítems de L tienen claves menores que cualquier item de R. Para esto aplica splay en el nodo con mayor valor de L, luego agrega R como subárbol derecho de la raíz. split (i, t): Parte el árbol t en dos subárboles, L que contiene todos los items con claves menores a i; y en R deja los nodos con claves mayores que i. Realiza accesar(i, t) luego parte el árbol en la raíz. inserte(i, t): Realiza split(i, t), luego convierte i en la raíz de los dos árboles que retorna split. descartar(i, t): Realiza accesar(i, t) luego descarta la raíz y realiza la unión de los subárboles. 13.3.2. Splay top-down. Se parte el árbol en dos subárboles, uno con claves menores al buscado y otro con claves mayores al buscado, y a medida que se desciende se van efectuado las rotaciones. Cuando se encuentra el nodo en la raíz del subárbol central, se unen los subárboles, dejando como raíz al nodo. Cada vez que se desciende desde un nodo x, por un enlace izquierdo, entonces x y su subárbol derecho serán mayores que el nodo (que será insertado o que es buscado). De esta forma se puede formar un subárbol, con x y su subárbol derecho, sea este subárbol R. El caso simétrico, que se produce cuando se sigue un enlace derecho, permite identificar el subárbol izquierdo de la nueva raíz, sea este subárbol denominado L. Como se recorre sólo una vez, ocupa la mitad del tiempo que el bottom-up. Se mantienen punteros a L y R, y punteros a los puntos de inserción de nuevos nodos en L y R; éstos son el hijo derecho del máximo elemento de L; y el hijo izquierdo del mínimo elemento de R. Estas variables evitan la necesidad de recorrer L y R; los nodos y subárboles que se agreguen a L o R, no cambian sus posiciones en L o R. A partir de la raíz se desciende hasta encontrar un posible nieto, se efectúa la operación pasando el abuelo y el padre a los subárboles L y R; el nieto queda en la raíz del árbol central. Si se encuentra el nodo se efectúa un join final.
Profesor Leopoldo Silva Bijit
20-01-2010
8
Estructuras de Datos y Algoritmos
Zig.
L
R
X
L
Y
R
L Y X
X YL
XR YR
YL
R
Y
YL YR
YR XR
XR
Figura 13.11. Top-down Zig Se aplica operación splay al nodo con valor Y. Mediante rotación derecha Y llega a ser la raíz, entonces el nodo X y su subárbol derecho (XR), se convierten en el hijo izquierdo del nodo con menor valor en R. En este caso, Y pasa a ser la raíz del subárbol central. Si t apunta a X, y si se tienen los punteros a punteros l y r, definidos según: arbol *l=&L, *r=&R; Se comienza a descender efectuando: p = t->left; entonces p apunta a Y. Si p no es nulo, y si el valor sobre el que se realiza splay no es mayor ni es menor que la clave Y (ésta es la condición para efectuar un Zig), entonces la siguiente secuencia, transforma el diagrama de la izquierda en el de la derecha: *r=t ; pega nodo X al subárbol R r=&(t->left); mantiene puntero al menor descendiente de R. t=t->left ; deja t apuntando a la nueva raíz (Y en el caso del ejemplo). El siguiente macro realiza la operación Zig top-down: #define rlink(t) (*r=(t), r=&((t)->left), (t)=(t)->left) Zig-Zig
L
R
X
L
R
Z Y
Y ZL
XR
ZR
Z
X YR
ZL
ZR
YR
Figura 13.12. Top-down Zig-Zig
Profesor Leopoldo Silva Bijit
20-01-2010
XR
Árboles desplegados. Splay trees.
9
Descendiendo buscando un nodo; cuando se llega a Z, se aplica Zig-Zig. Luego se extrae ZR, que después de la operación Zig-Zig, es el hijo izquierdo del nodo Y, y se coloca como subárbol derecho de Z; luego Y se liga como hijo izquierdo del menor valor en R. Si t apunta a X, y p = t->lext, la condición p diferente de nulo y (p->valor) mayor que el valor sobre el que se realiza la operación splay, se tiene la condición para la operación Zig-Zig. Se logra la transformación, con la secuencia: t=trot(t); rlink(t); Zig-Zag. L
R
X
L Y
Y
X
XR
ZL
Z
YL
R
Z
ZL
ZR
YL
XR
ZR
Figura 13.13. Top-down Zig-Zag Descendiendo buscando un nodo; cuando se llega a Z, se aplica Zig-Zag. Luego se pega Y a L, y X a R. Quedando Z en la raíz del árbol central. Si t apunta a X, y p = t->lext, la condición p diferente de nulo y (p->valor) menor que el valor sobre el que se realiza la operación splay, se tiene la condición para la operación Zig-Zag. Se logra la transformación, con la secuencia: rlink(t); llink(t); Con: #define llink(t) (*l=(t), l=&((t)->right), (t)=(t)->right) Después de rlink(t), t apunta al nodo Y. La descripción de llink es: *l=t ; pega Y y su subárbol izquierdo a L l=&(t->right) ; mantiene puntero al mayor descendiente de L. t=t->right; deja t apuntando a la nueva raíz (Z en el caso del ejemplo). Join. L
X
R
X
L XL
R
XR XL
Figura 13.14. Top-down Join.
Profesor Leopoldo Silva Bijit
20-01-2010
XR
10
Estructuras de Datos y Algoritmos
Cuando el nodo X, sobre el que originalmente se deseaba efectuar la operación splay, llega a estar en la raíz del subárbol central, se rearma el árbol, mediante la operación join. XL será el hijo derecho del máximo elemento de L; y XR será el hijo izquierdo del mínimo valor de R. Debe observarse que X es menor que los nodos en XR, y que éstos son menores que los que ya pertenecen a R. También X es mayor que los nodos en XL, y éstos son mayores que los que pertenecen a L. Si L y R eran los punteros a las raíces de los subárboles izquierdo y derecho respectivamente, la secuencia siguiente implementa la transformación de la Figura 13.14: *l = t->left; *r = t->right; t->left=L; t->right=R; Ejemplo top-down. Asumiendo que se busca E. Se encuentra C, descendiendo dos nodos; se pasan A y B a R. (Zig-Zig). L
R
A
L
R
C D
B
B A
E
C D E
Figura 13.15. Top-down Zig-Zig en C. Descendiendo dos niveles, se encuentra E, se deja en la raíz, con Zig-Zag. C se pega a L; D al nuevo R.
L
C
R D
C
B
E
E
L
R B A
A
D
Figura 13.16. Top-down Zig-Zag en E. Finalmente se efectúa el join. Profesor Leopoldo Silva Bijit
20-01-2010
Árboles desplegados. Splay trees.
11 E B
C D
A
Figura 13.17. Top-down Join.
13.4. Animaciones. http://www.ibr.cs.tu-bs.de/lehre/ss98/audii/applets/BST/SplayTree-Example.html
http://www.cs.technion.ac.il/~itai/ds2/framesplay/splay.html http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm
13.5. Códigos. /* splay.h*/ /* * 1985 D. D. Sleator R. E. Tarjan */ typedef int tipoclave; typedef struct moldenode { tipoclave clave; /* Clave */ struct moldenode *left, *right; } nodo, *arbol; /* Definiciones de macros */ #define max(A,B) ((A)>(B)?(A):(B)) #define search(valor,t) ((t)=splayBU((valor),(t),0), >clave==(valor))?(t):NULL) //funciones definidas en splay.c Pueden invocarse si se incluye splay.h extern arbol splayBU(tipoclave, arbol, int); extern arbol splayTD(tipoclave, arbol); extern arbol insertar(tipoclave, arbol); extern arbol borrar(tipoclave, arbol); extern int AlturaArbol(arbol); extern int ContarNodos(arbol); extern arbol BorraArbol(arbol); /* end of splay.h */ /* splay.c */ /* * Árbol binario autoorganizado. */ #include #include Profesor Leopoldo Silva Bijit
20-01-2010
((t)!=NULL&&(t)-
12
Estructuras de Datos y Algoritmos
#include "splay.h" //prototipos de funciones locales arbol sucesor(arbol t) ; static arbol join(arbol, arbol); arbol descartar(tipoclave valor, arbol t); static arbol lrot(arbol); static arbol rrot(arbol); static arbol CreaNodo(tipoclave); static void LiberaNodo(arbol); static void Error(int,tipoclave); void ImprimeNodo(arbol t, int h); //test void MuestraArbol(arbol t, int h); arbol insertarrecursivo(tipoclave valor, arbol T); arbol CreaArbol(arbol t, tipoclave a[]); //Variables Globales y Definiciones. static arbol NodoInsercion=NULL; /* Variable temporal, usada en insert, y por lo tanto en splay*/ static int flag; /* variable de estado */ /* * Bottom up */ #define Root 0 #define Zag 1 #define Zig 2 #define NotFind 0 #define Find 1 #define Zig_Zig 2 #define Zig_Zag 3 #define Zag_Zag 4 #define Zag_Zig 5 arbol splay(tipoclave valor, arbol t, int fw) { if (t == NULL && NodoInsercion == NULL) { flag=NotFind; /* árbol vacio o no lo encontró en búsqueda*/ return NULL; } else if (t == NULL && NodoInsercion != NULL) { /* encuentra posición para insertar */ t=NodoInsercion; /* Lo inserta */ NodoInsercion=NULL; /* Limpia variable global */ flag=Find; //comienza el ascenso y la operación splay. return t; } else if (t->clave == valor) { /* Lo encuentra antes de llegar a una hoja */ flag=Find; //comienza operación splay. No marca global NodoInsercion (3). return t; //retorna puntero al encontrado } Profesor Leopoldo Silva Bijit
20-01-2010
Árboles desplegados. Splay trees.
13
else if (t->clave < valor) { t->right=splay(valor,t->right, Zag); //desciende por la derecha if (flag) { /* rotaciones sólo si estaba en el árbol */ if (flag==Zag_Zag) { t=lrot(t); t=lrot(t); //efectúa doble rotación LL flag=Find; //resetea al ascender dos niveles. } else if (flag==Zag_Zig) { t=lrot(t); //rota el abuelo a la izquierda. (2) flag=Find; //resetea después de la doble rotación. } else if (fw==Zag) flag=Zag_Zag; //se juntan dos seguidas ascendiendo por la derecha else if (fw==Zig) { //está procesando Zig, y la anterior era Zag. t=lrot(t); //rota el padre a la izquierda (1) flag=Zig_Zag; } else /* (fw==Root) */ t=lrot(t); //efectúa Zag, un nivel bajo la raíz } } else { /* (t->clave < valor) */ t->left=splay(valor,t->left,Zig); //desciende por la izquierda if (flag) { /* rotaciones sólo si estaba en el árbol */ if (flag==Zig_Zig){ t=rrot(t); t=rrot(t); //efectúa doble rotación RR flag=Find; //resetea al ascender dos niveles. } else if (flag==Zig_Zag){ t=rrot(t); //rota el abuelo a la derecha (1) flag=Find; //resetea al ascender dos niveles. } else if (fw==Zig) flag=Zig_Zig; //se juntan dos seguidas ascendiendo por la izquierda else if (fw==Zag) { //está procesando Zag, y la anterior era Zig. t=rrot(t); //rota el padre a la derecha (2) flag=Zag_Zig; } else /* (fw==Root) */ t=rrot(t); //efectúa Zig, un nivel bajo la raíz } } return t; }
Profesor Leopoldo Silva Bijit
20-01-2010
14
Estructuras de Datos y Algoritmos
/* * Top Down */ #define rlink(t) (*r=(t), r=&((t)->left), (t)=(t)->left) #define llink(t) (*l=(t), l=&((t)->right), (t)=(t)->right) arbol splayTD(tipoclave valor, arbol t) { arbol L=NULL, R=NULL; /* Subárboles */ arbol *l=&L, *r=&R; /* punteros para insertar en L y R*/ arbol p; while (t != NULL && t->clave != valor) { if( valor < t->clave) { p = t->left; /*Desciende por la izquierda*/ if (p != NULL && valor < p->clave) { /* Zig_Zig */ printf("Zig-Zig en %d\n",t->clave); t=rrot(t); rlink(t); } else if (p != NULL && valor > p->clave) { /* Zig_Zag */ printf("Zig-Zag en %d\n",t->clave); rlink(t); llink(t); } else if(p != NULL && valor == p->clave) /* Zig */ { printf("Lo encontró. Zig en %d\n",t->clave); rlink(t); } else if(p==NULL && NodoInsercion !=NULL) { printf("Zig para insertar en %d\n",t->clave); rlink(t); //no está y debe insertarlo. } else if ((p==NULL) && NodoInsercion==NULL) { printf("Sube %d. Splay con el padre del no encontrado\n",t>clave); break; //no está el buscado. sube el padre del no encontrado a la raíz } } else { /* (valor > t->clave) */ p = t->right; /*Desciende por la derecha*/ if (p != NULL && valor > p->clave) { /* Zag_Zag */ printf("Zag-Zag en %d\n",t->clave); t=lrot(t); llink(t); } Profesor Leopoldo Silva Bijit
20-01-2010
Árboles desplegados. Splay trees.
15
else if (p != NULL && valor < p->clave) { /* Zag_Zig */ printf("Zag-Zig en %d\n",t->clave); llink(t); rlink(t); } else if(p!=NULL && valor == p->clave)/* Zag */ { printf("Lo encontró. Zag en %d\n",t->clave); llink(t); } else if(p==NULL && NodoInsercion !=NULL) { printf("Zag para insertar en %d\n",t->clave); llink(t); //no está y debe insertarlo. } else if ((p==NULL) && NodoInsercion==NULL) { printf("Sube %d .Splay con el padre del no encontrado\n",t->clave); break; //no está el buscado. sube el padre del no encontrado a la raíz } } } if (t==NULL && NodoInsercion == NULL) { /* si busca y árbol vacío */ return t; } if (t == NULL && NodoInsercion != NULL) { /* */ t=NodoInsercion; /* inserta y lo deja en la raíz */ NodoInsercion=NULL; /* reinicia global */ } if(L!=NULL) {*l = t->left; t->left =L; } /*join final*/ if(R!=NULL) {*r = t->right; t->right=R;} return t; } /* * insertar(valor, t): inserta nodo con clave igual a valor en arbol t */ 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 */ Profesor Leopoldo Silva Bijit
20-01-2010
16
Estructuras de Datos y Algoritmos free(NodoInsercion); NodoInsercion=NULL; Error(1,valor); // Avisa error de inserción. } return p;
} arbol buscar(tipoclave valor, arbol t) { arbol p; NodoInsercion = NULL; /* */ //p=splayBU(valor, t, Root); /* si lo encuentra, 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; } arbol sucesor(arbol t) /* Algoritmo iterativo */ /*menor descendiente de subárbol derecho */ { arbol p; if(t!=NULL) p = t->right; else return(NULL); if(p==NULL) return(NULL); if (p->left == NULL) /* No hay hijo izq. */ return (p); /* Retorna el menor */ while ( p->left != NULL) { /* Mientras no tenga hijo izq descender por la izq */ t = p; p = p->left; } /*Al terminar el while p apunta al menor descendiente */ return (p); /* Retorna el menor */ } 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); } else t=p->left; LiberaNodo(p); return(t); }
Profesor Leopoldo Silva Bijit
20-01-2010
Árboles desplegados. Splay trees.
17
13.6. Operaciones utilitarias. Se agrega descartar para completar las operaciones básicas. /* * descartar(valor, t): borra nodo con clave == valor en árbol t * No se implementa mediante splay. Lo que se borra no se volverá a emplear. */ arbol descartar(tipoclave valor, arbol t) { arbol *p = &t; arbol temp; while (*p != NULL && (*p)->clave != valor) {//descenso iterativo if((*p)->clave < valor) p = &((*p)->right); else p = &((*p)->left); } if (*p != NULL) { /* (*p)->clave == valor. Encontró el nodo para descartar */ temp = *p; /* Uno o dos hijos? */ if ((*p)->left == NULL) *p = (*p)->right; else if ((*p)->right == NULL)*p = (*p)->left; else /* si tiene dos hijos */ *p =join((*p)->left,(*p)->right); LiberaNodo(temp); } else /* No lo encontró */ Error(0,valor); return(t); } //join (l, r): Retorna el árbol formado por la combinación del árbol "l", y del árbol "r". //Se asume que cualquier item en "l" tiene valores menores que cualquier item en "r". static arbol join(arbol l, arbol r) { arbol t; arbol *p = &t; while (l != NULL && r != NULL) { *p = l; l = l->right; (*p)->right = r; p = &(r->left); r = r->left; } if (l == NULL) *p = r;
Profesor Leopoldo Silva Bijit
20-01-2010
18
Estructuras de Datos y Algoritmos else /* (r == NULL) */ *p = l; return t;
} static arbol lrot(arbol t) { arbol temp = t->right; t->right = temp->left; temp->left = t; return ( temp); } static arbol rrot(arbol t) { arbol temp = t->left; t->left = temp->right; temp->right = t; return (temp); } static void Error(int error, tipoclave valor) { if(error==1) printf("Error: Intenta insertar clave=%d existente!\n",valor); else if(error==0) printf("Error: Intenta descartar clave=%d inexistente!\n", valor); else if(error==2) printf("Error: Busca clave=%d en árbol vacío!\n", valor); } static nodo* CreaNodo(tipoclave valor) { arbol p; p=(arbol)calloc(1, sizeof(nodo)); //p->nombre=(char*) NULL; p->clave = valor; p->left = NULL; p->right = NULL; return p; } static void LiberaNodo(arbol p) { //if (p->nombre != (char *)NULL) free(p->nombre);//libera string free(p); } int AlturaArbol(arbol t) { if (t == NULL) return 0; else return 1+max(AlturaArbol(t->left),AlturaArbol(t->right)); } int ContarNodos(arbol t) { Profesor Leopoldo Silva Bijit
20-01-2010
Árboles desplegados. Splay trees.
19
if (t == NULL) return 0; else return 1+ContarNodos(t->left)+ContarNodos(t->right); } arbol BorraArbol(arbol t) { if (t != NULL) { t->left=BorraArbol(t->left); t->right=BorraArbol(t->right); LiberaNodo(t); } return NULL; } /* end of splay.c */
13.7. Funciones para efectuar test de splay. void ImprimeNodo(arbol t, int h) { int i; for(i=0; iclave); } void MuestraArbol(arbol t, int h) { if(t==NULL) ImprimeNodo(t, h); else {MuestraArbol(t->right, h+1); ImprimeNodo(t, h); MuestraArbol(t->left, h+1);} } arbol insertarrecursivo(tipoclave valor, arbol T) /* recursivo */ { if (T == NULL) { T = (arbol) malloc(sizeof(nodo)); if (T == NULL) printf("Rebalse del heap!\n"); else {T->clave = valor; T->left = T->right = NULL;} } else if (valor < T->clave) T->left = insertarrecursivo(valor,T->left); else if (valor > T->clave) T->right = insertarrecursivo(valor,T->right); else Error(1,valor); return(T); } #define maxnodos 2 arbol CreaArbol(arbol t, tipoclave a[]) { int i; Profesor Leopoldo Silva Bijit
20-01-2010
20
Estructuras de Datos y Algoritmos
for(i=0;i s’(y) y s’(x)> s(x) y mediante logaritmos se obtienen: r(y)> r’(y), y r’(x)>r(x). Entonces se puede acotar la amortización según: cˆi <= 1 + r'(x) - r(x) ya que r’(y)-r(y) < 0 Entonces con mayor razón, ya que r’(x)-r(x)>0: cˆi <= 1+ 3( r'(x) - r(x) ) Caso: Zig-Zag z
x
y
z
y
D x
A
A B
B C
D
C
Figura 13.21. Cambios de tamaños y rangos en Zig-Zag. Se tienen: s’(x) = s(z), s(y)>=s(x) , s’(x)>=s’(y)+s’(z) La primera implica: r’(x)-r(z)=0 La segunda: r(y)>=r(x) Para la tercera, se emplea la relación:
c a b, a 0, b 0
log(a) log(b) 2log(c) 2 Los logaritmos son en base dos.
La que se demuestra, según:
0 ( a b) 2
a 2 2ab b 2 Un cuadrado siempre es positivo
4ab a 2 2ab b 2
( a b) 2
c 2 Sumando 4ab en ambos lados, se obtiene
c2 ab 4 log(a) log(b) 2 log(c) 2 Entonces a partir de s’(x)>=s’(y)+s’(z), se obtiene: r’(y)+r’(z) <=r’(x)-2 la que implica: 2 <= 2r'(x) - r'(y) - r'(z) Calculando ahora el costo amortizado de Zig-Zag: cˆi ci ( Di ) ( Di 1 ) . Se requieren dos rotaciones, entonces el costo real es 2.
cˆi = 2 + ( r’(x)+r’(y)+r’(z) ) - ( r(x)+r(y)+r(z) ) ordenando, se obtiene: cˆi = 2 + r’(x)-r(z) –(r(x)+r(y)) + r’(y) + r’(z) Acotando la amortización, reemplazando r'(x) = r(z) y r(y) = r(x)+a, con a>0, se obtiene: cˆi <= 2 - 2r(x) + r'(y) + r'(z) , reemplazando ahora el primer 2, por algo mayor, se tiene: Profesor Leopoldo Silva Bijit
20-01-2010
Árboles desplegados. Splay trees.
31
cˆi <= (2r'(x) - r'(y) - r'(z)) + r'(y) + r'(z) - 2r(x), simplificando, se obtiene: cˆi <=2r’(x)-2r(x) y con mayor razón, ya que 3 es mayor que 2, y r’(x)>=r(x): cˆi <=3 ( r'(x) - r(x) ) Caso: Zig-Zig. x
z y
y
A
D
z
x B
C A
C
B
D
Figura 13.22. Cambios de tamaños y rangos en Zig-Zig. Se tienen; s'(x) = s(z) , s'(x) >= s'(y), s(y) >= s(x), s(x) + s'(z) <= s'(x) La última refleja que todos los nodos bajo x, luego de la rotación, deben ser al menos la suma de todos los nodos del árbol. Calculando ahora el costo amortizado de Zig-Zig, que también tiene costo real de dos rotaciones:
cˆi ci ( Di ) ( Di 1 ) cˆi = 2 + ( r’(x)+r’(y)+r’(z) ) - ( r(x)+r(y)+r(z) ) cˆi = 2 + ( r’(y)+r’(z) ) - ( r(x)+r(y) ) usando en la anterior que r'(x) = r(z) Buscando acotar la amortización, se tiene: cˆi <=2 + r'(x) + r'(z) - 2r(x) usando r'(x) >= r'(y) y r(y) >= r(x) Usando log(a) log(b) 2log(c) 2 , con s(x) + s'(z) <= s'(x) se tiene: r(x)+r’(z)<=2r’(x) -2 la que puede escribirse: 2 <= 2r'(x) - r(x) - r'(z) , lo cual puede reemplazarse en el costo amortizado por el primer 2. Se obtiene: cˆi <= (2r'(x) - r(x) - r'(z) ) + r'(x) + r'(z) - 2r(x) y arreglando, finalmente.
cˆi <= ( 3r'(x) - 3r(x) ) Ejemplo Veamos un cálculo amortizado para splay(3, root)
Profesor Leopoldo Silva Bijit
20-01-2010
32
Estructuras de Datos y Algoritmos 1
1
1
2
3
2
3
6
6
Zig-Zig 5
2
Zag-Zig
3
4
4
3
1
6
6
2
Zag
4
4
5
5
5
Figura 13.23. Cálculos amortizados. Sea x el nodo con valor 3, entonces: La operación Zig-Zig tiene costo amortizado menor que: 3(r’(x) - r(x) ) La operación Zag-Zig tiene costo amortizado menor que: 3(r’’(x) - r’(x) ) La operación Zag tiene costo amortizado menor que: 3(r’’’(x) - r’’(x)) + 1 Costo total: 3
cˆi <= 3(r’(x) - r(x) ) + 3(r’’(x) - r’(x) ) + 3(r’’’(x) - r’’(x)) + 1
i 1
Debido a la suma telescópica se cancelan r’(x) y r’’(x). Además la última rotación deja al nodo en la raíz, por lo tanto: 3
cˆi <= 3(r’’’(x) –r(x)) +1 = 3( r(raíz) – r(x) ) +1
i 1
13.8.9. Costo total amortizado de una operación splay. El costo total amortizado de una operación splay, de un nodo x en un árbol cuya raíz es t, será debido a las sumas telescópicas: 3(r(t)-r(x)) +1 Lo cual puede escribirse:
3(r (t ) r ( x)) 1 3log(
s(t ) s(t ) n ) 1 O(log( )) O(log( )) s ( x) s ( x) p
Ya que s(t) es n, el número de nodos en el árbol; y s(x) = p, donde p=0 se obtiene el costo amortizado de una operación: 3log(n) 1 Entonces, las m operaciones, más el cambio de potencial, se expresa según: m(3log(n) 1) O(n log(n)) la cual es O(m log(n) + n log(n)). Completando la demostración.
Referencias. Daniel Sleator, Robert Tarjan, “Self-Adjusting Binary Search Trees”, Journal of the Association for Computing Machinery. Vol. 32, No. 3, July 1985, pp. 652-686.
Profesor Leopoldo Silva Bijit
20-01-2010
34
Estructuras de Datos y Algoritmos
Índice general. CAPÍTULO 13 ............................................................................................................................................1 ÁRBOLES DESPLEGADOS. SPLAY TREES.......................................................................................1 13.1 DEFINICIÓN. ......................................................................................................................................1 13.2 OPERACIÓN SPLAY. ...........................................................................................................................1 Zig. .......................................................................................................................................................2 Zig-Zag.................................................................................................................................................2 Mover a la raíz. ....................................................................................................................................3 13.3 TIPOS DE ALGORITMOS. .....................................................................................................................3 13.3.1. Splay Bottom-up. ......................................................................................................................3 13.3.2. Ejemplos de operaciones splay bottom-up. .......................................................................................... 4 Splay(3, root); ............................................................................................................................................. 4 Splay(1, root); ............................................................................................................................................. 4 MuevealaRaiz(1, root)................................................................................................................................. 5 Insertar nodo con valor 5. ............................................................................................................................ 5 Descartar(4, root). ....................................................................................................................................... 6 Descartar(6, root) ........................................................................................................................................ 6
13.3.2. Splay top-down.........................................................................................................................7 Zig-Zig ............................................................................................................................................................. 8 Zig-Zag. ........................................................................................................................................................... 9 Join................................................................................................................................................................... 9 Ejemplo top-down. ......................................................................................................................................... 10
13.4. ANIMACIONES. ...............................................................................................................................11 13.5. CÓDIGOS. .......................................................................................................................................11 13.6. OPERACIONES UTILITARIAS. ...........................................................................................................17 SE AGREGA DESCARTAR PARA COMPLETAR LAS OPERACIONES BÁSICAS ........................................................17 13.7. FUNCIONES PARA EFECTUAR TEST DE SPLAY. .................................................................................19 13.8. ANÁLISIS DE COMPLEJIDAD. ...........................................................................................................20 13.8.1 Objetivo del análisis amortizado.............................................................................................20 13.8.2. Tipos de análisis.....................................................................................................................21 13.8.3. Analogía para la función potencial. .......................................................................................21 13.8.4. Ejemplo de análisis amortizado. ............................................................................................22 Método de agregación. ................................................................................................................................... 23 Método del banquero. .................................................................................................................................... 23 Método del potencial. ..................................................................................................................................... 24
13.8.5. Definiciones. ..........................................................................................................................25 13.8.6. Pasos en la aplicación del método del potencial. ..................................................................26 13.8.7. Función potencial en árboles splay. ......................................................................................27 Ejemplo función potencial. ............................................................................................................................ 28
13.8.8 Cálculo de costos amortizados por operación. .......................................................................29 Caso: Nodo x es la raíz .................................................................................................................................. 29 Caso: Zig ........................................................................................................................................................ 29 Caso: Zig-Zag ................................................................................................................................................ 30 Caso: Zig-Zig. ................................................................................................................................................ 31 Ejemplo .......................................................................................................................................................... 31
Profesor Leopoldo Silva Bijit
20-01-2010
Árboles desplegados. Splay trees.
35
13.8.9. Costo total amortizado de una operación splay. ................................................................... 32 13.8.10. Cambios de potencial. ......................................................................................................... 33 13.8.11. Teorema de Balance. ........................................................................................................... 33 REFERENCIAS. ........................................................................................................................................ 33 ÍNDICE GENERAL. ................................................................................................................................... 34 ÍNDICE DE FIGURAS................................................................................................................................. 35
Índice de figuras. FIGURA 13.1. OPERACIÓN ZIG. ..................................................................................................................... 2 FIGURA 13.2. OPERACIÓN ZIG-ZIG. .............................................................................................................. 2 FIGURA 13.3. OPERACIÓN ZIG-ZAG. ............................................................................................................. 2 FIGURA 13.4. MOVER X HACIA LA RAÍZ. ....................................................................................................... 3 FIGURA 13.5. OPERACIÓN SPLAY(3, ROOT)................................................................................................... 4 FIGURA 13.6. OPERACIÓN SPLAY(1, ROOT)................................................................................................... 4 FIGURA 13.7. OPERACIÓN MOVER A LA RAÍZ................................................................................................ 5 FIGURA 13.8. OPERACIÓN INSERTAR(5, ROOT) ............................................................................................. 5 FIGURA 13.9. OPERACIÓN DESCARTAR(4, ROOT).......................................................................................... 6 FIGURA 13.10. OPERACIÓN DESCARTAR(6, ROOT)........................................................................................ 6 FIGURA 13.11. TOP-DOWN ZIG ..................................................................................................................... 8 FIGURA 13.12. TOP-DOWN ZIG-ZIG .............................................................................................................. 8 FIGURA 13.13. TOP-DOWN ZIG-ZAG ............................................................................................................. 9 FIGURA 13.14. TOP-DOWN JOIN. ................................................................................................................... 9 FIGURA 13.15. TOP-DOWN ZIG-ZIG EN C. ................................................................................................... 10 FIGURA 13.16. TOP-DOWN ZIG-ZAG EN E. .................................................................................................. 10 FIGURA 13.17. TOP-DOWN JOIN. ................................................................................................................. 11 FIGURA 13.18. AMORTIZACIONES. .............................................................................................................. 22 FIGURA 13.19. TAMAÑOS Y RANGOS DE LOS NODOS. .................................................................................. 28 FIGURA 13.20. CAMBIOS DE TAMAÑOS Y RANGOS EN ZIG........................................................................... 29 FIGURA 13.21. CAMBIOS DE TAMAÑOS Y RANGOS EN ZIG-ZAG. ................................................................. 30 FIGURA 13.22. CAMBIOS DE TAMAÑOS Y RANGOS EN ZIG-ZIG. .................................................................. 31 FIGURA 13.23. CÁLCULOS AMORTIZADOS. ................................................................................................. 32
Profesor Leopoldo Silva Bijit
20-01-2010