El FHQ-Treap, también conocido como Treap de División y Fusión, es una implementación del Treap patentada por Fan Haoqiang. Su particularidad reside en el uso de las operaciones de división y fusión para realizar eficientemente operaciones como inserción, eliminación y búsqueda.

Estructura del Nodo

La estructura de un nodo en un FHQ-Treap se define típicamente de la siguiente manera, aunque puede adaptarse según los requisitos específicos del problema:

struct Nodo {
   int hijos[2]; // Punteros a los hijos izquierdo y derecho
   int valor;    // Valor asociado al nodo
   int prioridad; // Prioridad aleatoria para la propiedad del heap
   int cantidad;  // Número de elementos con el mismo valor
   int tamano;   // Tamaño del subárbol (incluyendo el nodo actual)
} fhq[2000010]; // Array para almacenar los nodos
   

Funciones Auxiliares

Se necesita un contador global para el número total de nodos y una variable para la raíz del árbol.

int contadorNodos = 0; // Contador de nodos utilizados
int raiz;             // Raíz del Treap
   

La creación de un nuevo nodo y la actualización de las propiedades de un nodo (como el tamaño del subárbol) son funciones fundamentales:

Nodo crearNodo(int val) {
   Nodo res;
   res.hijos[0] = res.hijos[1] = 0; // Inicializa los hijos como nulos
   res.valor = val;
   res.prioridad = rand();       // Asigna una prioridad aleatoria
   res.cantidad = res.tamano = 1; // Inicializa cantidad y tamaño a 1
   return res;
}

void actualizarPropiedades(int nodoIdx) {
   // Calcula el tamaño del subárbol basándose en los hijos y la cantidad del nodo actual
   fhq[nodoIdx].tamano = fhq[nodoIdx].cantidad;
   if (fhq[nodoIdx].hijos[0]) {
       fhq[nodoIdx].tamano += fhq[fhq[nodoIdx].hijos[0]].tamano;
   }
   if (fhq[nodoIdx].hijos[1]) {
       fhq[nodoIdx].tamano += fhq[fhq[nodoIdx].hijos[1]].tamano;
   }
}
   

Operación de División (Split)

La operación split divide un Treap en dos sub-Treaps basándose en un criterio (valor o rango). Aquí se presenta la división por valor:

pair<int, int> dividir(int nodoActual, int valorLimite);

Esta función divide el Treap con raíz nodoActual en dos Treaps: uno con todos los elementos menores o iguales a valorLimite y otro con los elementos mayores a valorLimite. Devuelve un par de enteros representando las raíces de los dos nuevos Treaps.

pair<int, int> dividir(int nodoActual, int valorLimite) {
   if (nodoActual == 0) {
       return {0, 0}; // Ambos sub-árboles están vacíos
   }

   if (fhq[nodoActual].valor <= valorLimite) {
       // El nodo actual y su subárbol izquierdo pertenecen al primer Treap.
       // Dividimos recursivamente el subárbol derecho.
       pair<int, int> resultadoSubdivision = dividir(fhq[nodoActual].hijos[1], valorLimite);
       fhq[nodoActual].hijos[1] = resultadoSubdivision.first; // El primer sub-árbol de la división se convierte en el hijo derecho
       actualizarPropiedades(nodoActual);                     // Actualiza el tamaño del nodo actual
       // Devuelve el nodo actual como raíz del primer Treap y el segundo sub-árbol de la división como raíz del segundo Treap.
       return {nodoActual, resultadoSubdivision.second};
   } else {
       // El nodo actual y su subárbol derecho pertenecen al segundo Treap.
       // Dividimos recursivamente el subárbol izquierdo.
       pair<int, int> resultadoSubdivision = dividir(fhq[nodoActual].hijos[0], valorLimite);
       fhq[nodoActual].hijos[0] = resultadoSubdivision.second; // El segundo sub-árbol de la división se convierte en el hijo izquierdo
       actualizarPropiedades(nodoActual);                      // Actualiza el tamaño del nodo actual
       // Devuelve el primer sub-árbol de la división como raíz del primer Treap y el nodo actual como raíz del segundo Treap.
       return {resultadoSubdivision.first, nodoActual};
   }
}
   

La complejidad de esta operación es logarítmica, \(O(\log n)\), debido a la naturaleza del árbol y la propiedad del heap.

Operación de Fusión (Merge)

La operación merge combina dos Treaps (u y v) en uno solo. Se asume que todos los valores en el Treap u son menores que todos los valores en el Treap v. La fusión se basa en las prioridades de los nodos raíz.

int fusionar(int u, int v);

int fusionar(int u, int v) {
   if (!u || !v) {
       return u | v; // Si uno de los árboles está vacío, devuelve el otro
   }

   if (fhq[u].prioridad < fhq[v].prioridad) {
       // Si la prioridad de u es menor, u se convierte en el padre.
       // Fusionamos recursivamente el hijo derecho de u con v.
       fhq[u].hijos[1] = fusionar(fhq[u].hijos[1], v);
       actualizarPropiedades(u); // Actualiza el tamaño de u
       return u;                // Devuelve u como la nueva raíz
   } else {
       // Si la prioridad de v es menor o igual, v se convierte en el padre.
       // Fusionamos recursivamente u con el hijo izquierdo de v.
       fhq[v].hijos[0] = fusionar(u, fhq[v].hijos[0]);
       actualizarPropiedades(v); // Actualiza el tamaño de v
       return v;                // Devuelve v como la nueva raíz
   }
}
   

La complejidad de la fusión también es logarítmica, \(O(\log n)\), ya que en cada paso recursivo se descarta uno de los nodos raíz.

Inserción y Eliminación

Inserción

Para insertar un valor val:

1. Dividir el Treap actual en dos: uno con valores < val y otro con valores ≥ val.
2. Dividir el segundo Treap (valores ≥ val) en dos: uno con valores == val y otro con valores > val.
3. Si el Treap de valores == val no está vacío, incrementar su contador. Si está vacío, crear un nuevo nodo para val.
4. Fusionar los tres Treaps resultantes en el orden correcto.

void insertar(int val) {
   // Dividir el árbol en dos partes: menores/iguales a 'val' y mayores que 'val'
   pair<int, int> partes1 = dividir(raiz, val);
   // Dividir la primera parte en dos: menores que 'val' y iguales a 'val'
   pair<int, int> partes2 = dividir(partes1.first, val - 1);

   int nodoValIgual = partes2.second; // Raíz del subárbol con valores iguales a 'val'

   if (!nodoValIgual) { // Si no existen nodos con el valor 'val'
       int nuevoNodoIdx = ++contadorNodos; // Crear un nuevo nodo
       fhq[nuevoNodoIdx] = crearNodo(val);
       nodoValIgual = nuevoNodoIdx;
   } else {
       fhq[nodoValIgual].cantidad++; // Incrementar la cantidad si ya existe
       actualizarPropiedades(nodoValIgual);
   }

   // Fusionar las tres partes: menores, iguales, mayores
   int arbolMenoresIguales = fusionar(partes2.first, nodoValIgual);
   raiz = fusionar(arbolMenoresIguales, partes1.second);
}
   

Eliminación

Para eliminar un valor val:

1. Dividir el Treap actual en tres partes: valores < val, valores == val, y valores > val.
2. Si el Treap de valores == val existe:

• Si su contador es mayor que 1, decrementar el contador.
• Si su contador es 1, eliminar completamente ese nodo (estalbecer su raíz a 0).

30. Fusionar las partes restantes.

void eliminar(int val) {
   // Dividir el árbol en tres partes: < val, == val, > val
   pair<int, int> partes1 = dividir(raiz, val);
   pair<int, int> partes2 = dividir(partes1.first, val - 1);

   int nodoValIgual = partes2.second; // Raíz del subárbol con valores iguales a 'val'

   if (nodoValIgual) { // Si existen nodos con el valor 'val'
       if (fhq[nodoValIgual].cantidad > 1) {
           fhq[nodoValIgual].cantidad--; // Decrementar la cantidad
           actualizarPropiedades(nodoValIgual);
           partes2.second = nodoValIgual; // Mantener el nodo
       } else {
           partes2.second = 0; // Eliminar el nodo si es el último
       }
   }

   // Fusionar las partes restantes
   int arbolMenoresIguales = fusionar(partes2.first, partes2.second);
   raiz = fusionar(arbolMenoresIguales, partes1.second);
}
   

Tanto la inserción como la eliminación tienen una complejidad de \(O(\log n)\) debido a las operaciones de división y fusión.

Consulta de Rango (Posición)

Para encontrar el rango (posición) de un valor val (cuántos elementos son menores o iguales a val):

1. Dividir el Treap en dos: valores < val y valores ≥ val.
2. El tamaño del primer Treap (valores < val) más 1 es el rango de val.
3. Fusionar los dos Treaps de nuevo.

int consultarRango(int val) {
   // Dividir el árbol en valores <= (val - 1) y > (val - 1)
   pair<int, int> partes = dividir(raiz, val - 1);
   // El tamaño del primer subárbol + 1 da el rango
   int rango = fhq[partes.first].tamano + 1;
   // Fusionar los árboles de nuevo
   raiz = fusionar(partes.first, partes.second);
   return rango;
}
   

Consulta de Valor por Rango

Para encontrar el valor en una posición rk específica:

Esta operación se realiza mediante una búsqueda binaria sobre la estructura del árbol.

int consultarValorPorRango(int nodoActual, int rk) {
   if (!nodoActual) return -1; // Árbol vacío

   int tamanoIzquierdo = fhq[nodoActual].hijos[0] ? fhq[fhq[nodoActual].hijos[0]].tamano : 0;

   if (rk <= tamanoIzquierdo) {
       // El elemento está en el subárbol izquierdo
       return consultarValorPorRango(fhq[nodoActual].hijos[0], rk);
   } else if (rk <= tamanoIzquierdo + fhq[nodoActual].cantidad) {
       // El elemento es el nodo actual
       return fhq[nodoActual].valor;
   } else {
       // El elemento está en el subárbol derecho
       // Ajustar el rango para la búsqueda en el subárbol derecho
       return consultarValorPorRango(fhq[nodoActual].hijos[1], rk - tamanoIzquierdo - fhq[nodoActual].cantidad);
   }
}
   

Consulta de Predecesor y Sucesor

Se pueden encontrar el predecesor y el sucesor de un valor val utilizando las operaciones de división y consulta de valor por rango.

Predecesor

El predecesor de val es el elemento más grande menor que val.

int consultarPredecesor(int val) {
   // Dividir el árbol en < val y >= val
   pair<int, int> partes = dividir(raiz, val - 1);
   // El elemento más grande en la primera parte es el predecesor
   int predecesorIdx = consultarValorPorRango(partes.first, fhq[partes.first].tamano);
   int valorPredecesor = fhq[predecesorIdx].valor;
   // Fusionar los árboles de nuevo
   raiz = fusionar(partes.first, partes.second);
   return valorPredecesor;
}
   

Sucesor

El sucesor de val es el elemento más pequeño mayor que val.

int consultarSucesor(int val) {
   // Dividir el árbol en <= val y > val
   pair<int, int> partes = dividir(raiz, val);
   // El elemento más pequeño en la segunda parte (el primero) es el sucesor
   int sucesorIdx = consultarValorPorRango(partes.second, 1);
   int valorSucesor = fhq[sucesorIdx].valor;
   // Fusionar los árboles de nuevo
   raiz = fusionar(partes.first, partes.second);
   return valorSucesor;
}