Este artículo explora el FHQ-Treap (Fancy Height-keyed Queap - Treap), una variante no rotatoria del Treap, discutiendo su funcionamiento, operaciones clave y aplicaciones.
Introducción a los Árboles de Búsqueda Binaria (BST)
Un Árbol de Búsqueda Binaria (BST) es una estructura de datos donde para cada nodo, todos los valores en su subárbol izquierdo son menores que el valor del nodo, y todos los valores en su subárbol derecho son mayores. Esto garantiza que un recorrido inorden del árbol produzca una secuencia ordenada de valores. Sin embargo, la estructura de un BST puede ser inestable, susceptible a ataques de datos que lo degeneran a una complejidad de tiempo de $O(n)$. Con datos aleatorios, la altura esperada es $O(\log n)$.
Conceptos Fundamentales del Treap
Un Treap combina las propiedades de un BST con las de un Heap. Cada nodo en un Treap tiene dos valores:
- Valor (Key): Se utiliza para mantener la propiedad del BST, asegurando que el valor del hijo izquierdo sea menor y el del hijo derecho sea mayor que el del nodo padre.
- Prioridad (Heap Value): Se asigna aleatoriamente a cada nodo y se utiliza para mantener la propiedad del Heap (generalmente un min-heap, donde la prioridad del padre es menor que la de sus hijos).
La combinación de estas dos propiedades hace que la estructura del Treap sea única para un conjunto dado de valores y prioridades aleatorias. La raíz del árbol siempre será el nodo con la prioridad mínima. Dado el nodo raíz, las particiones de valores para los subárboles izquierdo y derecho están definidas. Las restricciones de prioridad ayudan a determinar los hijos izquierdo y derecho de manera única, fijando así la estructura del árbol. Los Treaps se pueden implementar de dos maneras: rotatorios (como Splay Trees) o no rotatorios (como FHQ-Treap). Este artículo se enfoca en la implementación no rotatoria.
Complejidad del Treap
Si bien la distribución de valores no se puede controlar directamente, la aleatorización de las prioridades asegura que la altura del Heap sea $O(\log n)$. Dado que la altura del Treap está limitada por la altura del Heap, las operaciones tienen una complejidad esperada de $O(\log n)$.
Operaciones Clave: División y Unión
El FHQ-Treap se caracteriza por su implementación simplificada y su capacidad para realizar diversas operaciones a través de las operaciones de división (split) y unión (merge).
División (Split)
La operación de división divide un Treap en dos Treaps: uno que contiene elementos menores que un valor dado $x$, y otro que contiene elementos mayores o iguales a $x$.
Para dividir un Treap con raíz $u$:
- Si el valor del nodo raíz $u$ es menor o igual a $x$, entonces el nodo raíz y su subárbol izquierdo pertenecen al Treap resultante de la izquierda ($L$). La división continúa recursivamente en el subárbol derecho, buscando elementos menores o iguales a $x$.
- Si el valor del nodo raíz $u$ es mayor que $x$, entonces el nodo raíz y su subárbol derecho pertenecen al Treap resultante de la derecha ($R$). La división continúa recursivamente en el subárbol izquierdo, buscando elementos mayores que $x$.
El caso base es cuando $u$ es nulo, en cuyo caso ambos Treaps resultantes son nulos.
Es crucial actualizar el tamaño de los subárboles después de cada división.
void split(int u, int x, int &L, int &R) {
if (u == 0) {
L = R = 0;
return;
}
if (tree[u].key <= x) {
L = u;
split(tree[u].rs, x, tree[u].rs, R);
} else {
R = u;
split(tree[u].ls, x, L, tree[u].ls);
}
update(u); // Actualiza tamaño y otras propiedades del nodo u
}
Unión (Merge)
La operación de unión combina dos Treaps, $l$ y $r$, en un solo Treap. Esta operación requiere que los valores en el Treap $l$ sean menores que los valores en el Treap $r$. La unión se basa en las prioridades de los nodos raíz de $l$ y $r$.
- Si la prioridad del nodo raíz de $l$ es mayor que la del nodo raíz de $r$, entonces el nodo raíz de $l$ se convierte en la nueva raíz. El Treap $r$ se une recursivamente al subárbol derecho de $l$.
- Si la prioridad del nodo raíz de $l$ es menor o igual que la del nodo raíz de $r$, entonces el nodo raíz de $r$ se convierte en la nueva raíz. El Treap $l$ se une recursivamente al subárbol izquierdo de $r$.
Después de la unión, se actualizan las propiedades del nodo raíz resultante.
int merge(int L, int R) {
if (L == 0) return R;
if (R == 0) return L;
if (tree[L].pri > tree[R].pri) {
tree[L].rs = merge(tree[L].rs, R);
update(L);
return L;
} else {
tree[R].ls = merge(L, tree[R].ls);
update(R);
return R;
}
}
Inserción y Eliminación
Las operaciones de inserción y eliminación se pueden implementar eficientemente utilizando las operaciones de división y unión.
Inserción
Para insertar un valor $x$:
- Dividir el Treap actual en dos partes: una con elementos menores o iguales a $x$, y otra con elementos mayores que $x$.
- Crear un nuevo nodo para $x$.
- Unir el Treap de elementos menores o iguales a $x$ con el nuevo nodo, y luego unir el resultado con el Treap de elementos mayores que $x$.
void insert(int x) {
int l, r;
split(root, x, l, r); // Divide en <x y="">=x
int newNode = new_node(x); // Crea un nuevo nodo para x
root = merge(merge(l, newNode), r); // Une l, el nuevo nodo y r
}</x>
Eliminación
Para eliminar un valor $x$:
Eliminación Total de un Valor
- Dividir el Treap para separar los elementos menores que $x$.
- Dividir el segundo Treap para separar los elementos iguales a $x$ (el subárbol medio).
- Unir los dos Treaps restantes (elementos menores que $x$ y elementos mayores que $x$).
void deleteAll(int x) {
int l, r, mid;
split(root, x, l, r); // l: [1, x], r: [x+1, ...]
split(l, x - 1, l, mid); // l: [1, x-1], mid: [x, x]
root = merge(l, r); // Une los árboles sin el valor x
}
Eliminación de una Instancia de un Valor
Para eliminar una sola instencia de un valor $x$ (si hay duplicados):
- Dividir el Treap para separar los elementos menores que $x$.
- Dividir el segundo Treap para aislar el subárbol que contiene solo instancias de $x$.
- Unir los subárboles izquierdo y derecho del subárbol aislado de $x$ para eliminar su raíz.
- Unir los tres Treaps resultantes.
void deleteOne(int x) {
int l, r, mid;
split(root, x, l, r); // l: [1, x], r: [x+1, ...]
split(l, x - 1, l, mid); // l: [1, x-1], mid: [x, x]
// mid contiene los nodos con valor x. Aquí asumimos que solo hay uno.
// Si hay varios, se necesitaría una lógica más compleja para eliminar solo uno.
// Para eliminar una instancia, se unen los hijos del nodo 'mid'.
// Aquí simplificamos asumiendo 'mid' apunta a un solo nodo o a la raíz de un subárbol de 'x'.
// La lógica correcta implicaría extraer un nodo de 'mid' y luego unir.
// Una forma más directa si 'mid' es la raíz del subárbol de 'x':
if (mid != 0) {
// Para eliminar una instancia, se unen sus hijos.
// Esto asume que 'mid' es el nodo a eliminar.
// En una implementación real, se buscaría el nodo específico.
int nodeToDel = mid; // Simplificación: asumimos que mid es el nodo a eliminar
int merged_mid = merge(tree[nodeToDel].ls, tree[nodeToDel].rs);
root = merge(merge(l, merged_mid), r);
} else {
root = merge(l, r); // Si mid es 0, no hay nada que eliminar
}
}
Consultas
Consulta de Rango (Rank)
Obtener el rango de un valor $x$
El rango de un valor $x$ es el número de elementos en el Treap que son estrictamente menores que $x$, más uno. Esto se logra dividiendo el Treap para obtener todos los elementos menores que $x$ y obteniendo el tamaño de ese subárbol.
int getRank(int x) {
int l, r;
split(root, x - 1, l, r); // Divide en <x y="">=x
int rank = tree[l].size; // Tamaño del subárbol izquierdo es el número de elementos < x
root = merge(l, r); // Restaura el árbol
return rank + 1; // El rango es el tamaño + 1
}</x>
Obtener el k-ésimo elemento
Para encontrar el k-ésimo elemento en el Treap, se realiza una búsqueda recursiva basada en el tamaño del subárbol izquierdo.
int findKth(int u, int k) {
if (u == 0) return -1; // O algún indicador de error
int leftSize = tree[u].ls == 0 ? 0 : tree[tree[u].ls].size;
if (k == leftSize + 1) {
return u; // El nodo actual es el k-ésimo
} else if (k <= leftSize) {
return findKth(tree[u].ls, k); // Buscar en el subárbol izquierdo
} else {
return findKth(tree[u].rs, k - leftSize - 1); // Buscar en el subárbol derecho
}
}
Buscar el Predecesor y Sucesor
Predecesor de $x$
Para encontrar el predecesor de $x$, se divide el Treap para obtener todos los elementos menores que $x$. El elemento de mayor rango en este subárbol es el predecesor.
int predecessor(int x) {
int l, r;
split(root, x - 1, l, r); // l: [1, x-1], r: [x, ...]
// Encontrar el elemento de mayor rango en 'l'
int pred_node_idx = findKth(l, tree[l].size);
int res = (pred_node_idx == -1) ? -1 : tree[pred_node_idx].key; // -1 si no hay predecesor
root = merge(l, r); // Restaura el árbol
return res;
}
Sucesor de $x$
Para encontrar el sucesor de $x$, se divide el Treap para obtener todos los elementos menores o iguales a $x$. El elemento de menor rango en el subárbol restante (elementos mayores que $x$) es el sucesor.
int successor(int x) {
int l, r;
split(root, x, l, r); // l: [1, x], r: [x+1, ...]
// Encontrar el elemento de menor rango en 'r'
int succ_node_idx = findKth(r, 1);
int res = (succ_node_idx == -1) ? -1 : tree[succ_node_idx].key; // -1 si no hay sucesor
root = merge(l, r); // Restaura el árbol
return res;
}
Variaciones y Aplicaciones
División por Rango
Algunos problemas requieren dividir un Treap basado en el rango de los nodos en lugar de su valor. Esto es útil en aplicaciones como editores de texto o manejo de secuencias donde se opera sobre posiciones en lugar de valores directos.
void splitByRank(int u, int rank, int &L, int &R) {
if (u == 0) {
L = R = 0;
return;
}
int leftSize = tree[u].ls == 0 ? 0 : tree[tree[u].ls].size;
if (rank <= leftSize + 1) { // El nodo actual o algo a su izquierda es el separador
R = u;
splitByRank(tree[u].ls, rank, L, tree[u].ls);
} else { // El separador está en el subárbol derecho
L = u;
splitByRank(tree[u].rs, rank - leftSize - 1, tree[u].rs, R);
}
update(u); // Actualiza tamaño y otras propiedades
}
Estructuras con Múltiples Atributos
Para problemas que involucran múltiples criterios de ordenación o atributos, se pueden utilizar Treaps anidados o estructuras más complejas como "árboles sobre árboles" (tree-on-tree), especialmente si solo un atributo se utiliza para la eliminación y otros se usan para consultas. Si se necesitan eliminaciones basadas en múltiples atributos, las estructuras de árbol dinámicas más avanzadas pueden ser necesarias.