arboles splay
TRANSCRIPT
Instituto Tecnológico de Costa Rica
Escuela de Computación
Curso de Estructuras de Datos
Árboles Splays
Estudiantes:
Randall Araya
Diego Delgado
Víctor Saborío
Bryan Serracín
Daniel Solís
2013
¿Qué son los árboles splay?
Definición
Es un árbol binario de búsqueda con la propiedad de
ser auto balanceable, además, los elemento recién
visitados, se accederán más rápido en próximas
consultas.
Acerca de los árboles.
Los árboles splay, fueron creados por: Robert Tarjan y Daniel Sleator.
La operación de biselación, se lleva a cabo mediante la reorganización del árbol
para cada cierto elemento, colocándolo en la raíz.
Éstos árboles son más simples de implementar que otros árboles binarios de
búsqueda auto balanceables.
Los árboles splay, funcionan de forma correcta aunque existan nodos con llaves
repetidas.
Inserción en un Árbol Splay
La inserción en este tipo de árbol es igual a la inserción en un
árbol binario de búsqueda.
Luego de la inserción se ejecuta la Biselación de ese nodo.
Inserción:
Para la inserción de un nuevo valor en el árbol binario de búsqueda se
deben considerar los siguientes aspectos.
La primera inserción en el árbol es conocida como la raíz pero esta va a
ser modificada por la Operación Biselación, otra forma de identificar la
raíz del árbol es que el nodo no tiene un nodo padre.
A la hora de la inserción se hace una comparación con el entre el nodo
padre y el nodo a insertar para evaluar su inserción.
A la hora de la inserción se hace una comparación con el nodo que ya esta en el
árbol para evaluar y dirigir hacia que lado del árbol se da la inserción hasta llegar a
insertarse en uno de los nodos hijos sean mayores o menores vacíos
Insertar: 5
4
5
5
4
4 < 5
entonces se
inserta al a
derecha por la
regla de
inserción
Luego se ejecuta la operación de
Biselación
Raíz5
4
Nueva Raíz
Insertar: 2
5
4
22 < 5 entonces se inserta a la
izquierda por la regla de
inserción, pero su hijo izquierdo
ya esta ocupado así que se
consulta a su hijo para
insertarlo debajo de él siendo el
su padre
5
42 < 4 entonces se
inserta al a
izquierda por la
regla de inserción2
Luego se ejecuta la operación de Biselación
5
4
2
2
Luego se ejecuta de nuevo la operación de
Biselación para el reacomodo del árbol
hasta que e ultimo valor insertado sea la
nueva raíz
4
5
Nueva Raíz
Operación de Biselación
Método eliminación Árbol Splay
Para el diseño de eliminación existen dos posibilidades
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 laproximidad del elemento borrado.
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. Luegoefectúa una operación splay con el nodo con mayor clave en el subárbol izquierdo; acontinuación se descarta la raíz; y finalmente se enlaza el subárbol derecho con elsubárbol izquierdo.
Por ejemplo, eliminar 4.
6
5
1
2
4
3
7 4
1
2
3 5
6
7
Continuación eliminar 4.
5
6
1
2
3
7
4
75
6
1
2
3Liberar Raíz
Join izquierda y derecha
En el ejemplo anterior, la operación eliminar 4, ubica el nodo
con valor 4, y lo lleva a la raíz. Luego se efectúa Splay 3, se
descarta el nodo con valor 4, y se efectúa la unión de dos
subárboles (join).
Ejemplo 2, eliminar 6
8
2
75
6
41
3
5
2
1
83
4 7
6
Splay 5
1
2
3
84
57
6 Liberar Raíz
2
8
1
3
4 7
5
Join izquierda y derecha
Búsqueda en Árbol Splay
Proceso de búsqueda
Para buscar una llave en un árbol splay, se realiza de la misma forma en que se busca
en los árboles binarios de búsqueda, pero con una serie de cambio en la estructura.
Proceso de búsquedaDentro de los cambio básicos, se encuentra:
Al momento de encontrar la llave por eliminar, el nodo del árbol, se bisela.
Si no se encuentra la llave, se bisela el último nodo que fue visitado, antes de descartar
la búsqueda.
Con esto, la raíz contendrá un sucesor o predecesor del nodo buscado.
Operación de biselación
Biselación: consiste en subir un nodo hasta que
este llegue a ser la raíz. Esto se realiza con
rotaciones simples y dobles.
¿Cuándo y a que nodo se realiza la
biselación?
Se sigue el mismo algoritmo de, búsqueda, eliminación
e inserción que de árbol binario de búsqueda, pero el
nodo que se insertó, buscó o el mayor hijo izquierdo
del nodo eliminado será biselado.
Caso 1(aplicando biselación al 4)
El 4 es hijo izquierdo de 9, por lo que aplicamos rotaciónsimple a la derecha a 9 (al “padre”). Recordar que labiselación consiste en que ese número llegue a ser la raíz.
Caso 1(aplicando biselación al 17)
El 17 es hijo derecho de 15, por lo que le aplicamos rotación simple a la izquierda a 15 (al “ padre”).
Caso 2(aplicando biselación al 17)
El 17 es hijo derecho de 15 y nieto derecho de 9, por loque aplicamos rotación doble a la izquierda , es decir,rotación simple izquierda a 9 (al “abuelo”) y luegorotación simple izquierda a 15 (“al padre”) .
Caso 2(aplicando biselación al 9)
El 9 es hijo izquierdo de 15 y nieto izquierdo de 17, porlo que aplicamos rotación doble a la derecha , esdecir, rotación simple derecha a 17 (al “abuelo”) yluego rotación simple derecha a 15 (“al padre”) .
Caso 3(aplicando biselación al 18)
El 18 es hijo izquierdo de 20 y nieto derecho de 14, porlo que aplicamos rotación simple derecha izquierda ,es decir, rotación simple derecha a 20 (al “padre”) yluego rotación simple izquierda a 14 (“al abuelo”) .
Caso 3(aplicando biselación al 18)
El 18 es hijo derecho de 14 y nieto izquierdo de 20, porlo que aplicamos rotación simple izquierda derecha ,es decir, rotación simple izquierda a 14 (al “padre”) yluego rotación simple derecha a 20 (“al abuelo”) .
Teoremas de rendimiento:
• TEOREMA DEL BALANCE
• TEOREMA DE OPTIMALIDAD ESTÁTICA
• TEOREMA “STATIC F INGER”
• TEOREMA “WORKING SET ”
• TEOREMA “DYNAMIC F INGER”
Teorema del balanceO(m log(n) + n log(n)).
Una secuencia de “m” operaciones Splay en un arbol de n nodos tiene una complejidad
temporal:
O(m log(n) + n log(n)).
En general cuando una secuencia de M operaciones toma tiempo O(M f(N)), se dice que
el costo Amortizado en tiempo de cada operación es O(f(N)). Por lo tanto, en un splay
tree los costos amortizados por operacion son de O(log(N)).
Teorema de optimalidad estática
Sea “q” el número de veces que se accede al elemento “i” en S.
En otras palabras, los árboles biselados se comportan tan bien como los árboles
binarios de búsqueda estáticos óptimos en las secuencias de al menos n accesos.
Teorema de “Static Finger”Suponemos siempre que la búsqueda de un elemento comienza desde el nodo raíz. El
elemento donde comenzamos búsqueda cambia cada vez que un elemento diferente
llega al nodo raíz.
Suponga que dieron un puntero a un elemento y comenzar la búsqueda de ella cada vez
que llega una consulta.
Sea i-j el elemento visitado en el e-esimo acceso de S y f sea un element fijo, el costo de
realizer esta secuencia de accesos seria de:
Teorema “Working Set”
Sea t(j) el numero de elementos distintos accedidos desde la ultima vez que
se accedió a J antes del instante i.
supongamos que J es buscado en la t-esima operación. T(j) denota el numero
de elementos distintos buscados desde la ultima búsqueda de J, por ejemplo
la secuencia 7,9,5,6,4,3,2,4,3,5, y si intentamos buscar T(10)(5) es 4. el
teorema explica que:
Teorema Dynamic finger
Supongamos que el tamaño (r) es el número de nodos en el subárbol
con raíz en r (incluyendo r) y el rango (r) = log2 (tamaño (r)). A
continuación, la función potencial de P (t) para un árbol de splay t es la
suma de los rangos de todos los nodos en el árbol. Esto tiende a ser alto
para los árboles mal equilibrados y bajo en los árboles equilibrados.