Introducción al Splay Tree
El Splay Tree es una variante autoajustable de árbol binario de búsqueda (BST). A diferencia de otros árboles balanceados que mantienen invariantes estrictos tras cada operación, el Splay utiliza la heurística de mover los nodos accedidos hacia la raíz. Esto garantiza una complejidad amortizada de $O(\log n)$ por operación.
Debido a su capacidad dinámica, es ideal para manejar operaciones sobre rangos, combinaciones de conjuntos y tareas donde el acceso local a datos frecuentes ocurre con frecuencia. Su implementación puede ser más compacta en términos de código comparada con otras estructuras de equilibrio, sin sacrificar rendimiento para aplicaciones generales.
Nodos y Representación
Cada nodo debe almacenar referencias a sus hijos, el valor clave, tamaño del subárbol y cualquier información auxiliar requerida. Usamos un array global para simular punteros y optimizar el uso de memoria.
struct Nodo {
int hijo[2]; // 0: izquierda, 1: derecha
int padre;
int valor;
int tamano; // Tamaño del subárbol
int contador; // Para duplicados
void inicializar(int p, int v) {
hijo[0] = hijo[1] = 0;
padre = p;
valor = v;
tamano = 1;
contador = 1;
}
};
const int MAXN = 500005;
Nodo arbol[MAXN];
int raiz, indice = 0;
Mecanismo Fundamental: Rotación y Splay
La rotación es la base de cualquier transformación estructural. Permite intercambiar las posiciones de un padre y su hijo mientras se conserva la prpoiedad de ordenamiento.
Rotación de Nodos
Dado un nodo $x$, identificamos su padre $y$ y abuelo $z$. Dependiendo de si $x$ es hijo izquierdo o derecho, actualizamos los puntes correspondientes.
void realizar_rotacion(int x) {
int y = arbol[x].padre;
int z = arbol[y].padre;
// Determinar si x es hijo derecho (1) o izquierdo (0)
int tipo = x == arbol[y].hijo[1];
// Conectar z con x (actualizando el lado correcto de z)
arbol[z].hijo[tipo] = x;
arbol[x].padre = z;
// Mover el hijo opuesto de x a su nuevo lugar (bajo y)
arbol[y].hijo[tipo ^ 1] = arbol[x].hijo[tipo];
arbol[arbol[x].hijo[tipo]].padre = y;
// Finalizar enlace entre y y x
arbol[x].hijo[tipo ^ 1] = y;
arbol[y].padre = x;
}
Operación Splay
La función central mueve un nodo $x$ hasta convertirse en el hijo de un nodo objetivo $k$, o la raíz si $k=0$. Se distinguen dos patrones: línea recta (Zig-Zig) y forma de L (Zig-Zag).
void ascender_nodo(int x, int k) {
// Mientras el padre no sea el nodo objetivo
while(arbol[x].padre != k) {
int y = arbol[x].padre;
int z = arbol[y].padre;
if(z != k) { // Si existe abuelo
// Verificar patrón: paridad diferente indica Zig-Zag
bool direccion_y = (y == arbol[z].hijo[1]);
bool direccion_x = (x == arbol[y].hijo[1]);
if(direccion_y != direccion_x) {
realizar_rotacion(x); // Zig-Zag
} else {
realizar_rotacion(y); // Zig-Zig
}
}
realizar_rotacion(x);
}
if(!k) raiz = x; // Actualizar raíz global si corresponde
}
Operaciones de Mantenimiento
Para realizar búsquedas basadas en rank (posición) y manejo eficiente de tamaños, necesitamos mantener el atributo tamano actualizado.
inline void actualizar_info(int x) {
arbol[x].tamano =
arbol[arbol[x].hijo[0]].tamano +
arbol[arbol[x].hijo[1]].tamano +
arbol[x].contador;
}
Búsqueda, Inserción y Eliminación
La inserción sigue el flujo estándar de un BST: localizar el lugar, agregar si es necesario, y luego ejecutar ascender_nodo en el nuevo elemento para mantener el balance amortizado.
void insertar_valor(int v) {
int u = raiz, p = 0;
while(u && u != 0) {
p = u;
u = arbol[u].hijo[v > arbol[u].valor];
}
int nodo_new = ++indice;
if(p) arbol[p].hijo[v > arbol[p].valor] = nodo_new;
else raiz = nodo_new;
arbol[nodo_new].inicializar(p, v);
ascender_nodo(nodo_new, 0);
}
La eliminación requiere asegurar que el nodo a borrar tenga como padre directo el límite superior o inferior del rango a eliminar antes de desvincularlo del árbol principal.
Interrogaciones Específicas
Con el tamaño del subárbol dsiponible, podemos calcular el rango ($rank$) de un valor o encontrar el valor de una posición específica ($k$-ésimo).
int obtener_rank(int v) {
// Truco: insertar temporalmente para normalizar la estructura si no existe
// Sin embargo, mejor buscar primero.
return 0;
}
int k_esimo(int k) {
int u = raiz;
if(!u) return -1;
// Descenso guiado por tamaño del subárbol izquierdo
while(true) {
int izq = arbol[u].hijo[0];
if(izq && arbol[izq].tamano >= k) {
u = izq;
} else {
int cnt_izq = arbol[izq] ? arbol[izq].tamano : 0;
if(cnt_izq + arbol[u].contador >= k) return arbol[u].valor;
k -= cnt_izq + arbol[u].contador;
u = arbol[u].hijo[1];
}
}
}
Gestión de Rangos y Propagación de Etiquetas
Una ventaja potente del Splay es soportar operaciones de intervalo modificables (como invertir un segmento o asignar valores constantes). Esto se logra mediante marcadores de懒惰 (lazy tags).
Lógica de PushDown
Antes de acceder a un hijo, debemos procesar sus etiquetas. Por ejemplo, si hay una bandera de inversión (rev), se intercambian los puntes izquierdo y derecho, y la bandera se propaga a los hijos.
void propagar_etiqueta(int x) {
int l = arbol[x].hijo[0];
int r = arbol[x].hijo[1];
if(l) {
arbol[l].rev ^= 1;
// Intercambiar hijos de l también
std::swap(arbol[l].hijo[0], arbol[l].hijo[1]);
}
if(r) {
arbol[r].rev ^= 1;
std::swap(arbol[r].hijo[0], arbol[r].hijo[1]);
}
// Limpiar bandera del nodo actual después de procesar
if(arbol[x].rev) arbol[x].rev = 0;
}
Aplicación en Problemas Complejos
En escenarios avanzados donde el número de elementos varía dinámicamente o existen operaciones de fusión de árboles, técnicas como la gestión de memoria (reciclaje de nodos eliminados) son cruciales para evitar fugas y cumplir con límites de tiempo.
void recolectar_memory(int x) {
if(arbol[x].hijo[0]) recolectar_memory(arbol[x].hijo[0]);
if(arbol[x].hijo[1]) recolectar_memory(arbol[x].hijo[1]);
// Añadir índice a cola de objetos libres
libre[++tt] = x;
}
Al combinar estas capacidades (splays, rotaciones, pushdown y gestión de memoria), es posible resolver problemas que requieren mantenimiento de secuencias dinámicas con complejidades eficientes para todas las consultas de rango y punto.