Treap (árbol cartesiano)

Un treap es una estructura de datos que combina un árbol binario y un heap binario (de ahí el nombre: tree + heap $\Rightarrow$ Treap).

Más concretamente, un treap es una estructura de datos que guarda pares $(X, Y)$ en un árbol binario de modo que es un árbol binario de búsqueda por $X$ y un heap binario por $Y$ . Si algún nodo del árbol contiene los valores $(X_0, Y_0)$ , todos los nodos del subárbol izquierdo tienen $X \leq X_0$ , todos los nodos del subárbol derecho tienen $X_0 \leq X$ , y todos los nodos de ambos subárboles izquierdo y derecho tienen $Y \leq Y_0$ .

Un Treap también se llama a menudo «árbol cartesiano», porque es fácil embeberlo en un plano cartesiano:

Los treaps fueron propuestos por Raimund Siedel y Cecilia Aragon en 1989.

Ventajas de esta organización de los datos

En esta implementación, los valores $X$ son las claves (y al mismo tiempo los valores guardados en el treap), y los valores $Y$ se llaman prioridades. Sin prioridades, el treap sería un árbol binario de búsqueda ordinario por $X$ , y un mismo conjunto de valores $X$ podría corresponder a muchos árboles distintos, algunos de ellos degenerados (por ejemplo, en forma de lista enlazada), y por tanto extremadamente lentos (las operaciones principales tendrían complejidad $O(N)$ ).

Al mismo tiempo, las prioridades (cuando son únicas) permiten especificar de forma única el árbol que se construirá (por supuesto, no depende del orden en que se agregan los valores), lo cual se puede demostrar con el teorema correspondiente. Obviamente, si elegimos las prioridades al azar, en promedio obtendremos árboles no degenerados, lo que garantiza complejidad $O(\log N)$ para las operaciones principales. De ahí otro nombre de esta estructura de datos: árbol binario de búsqueda aleatorizado.

Operaciones

Un treap ofrece las siguientes operaciones:

Insert (X,Y) en $O(\log N)$ .
Agrega un nuevo nodo al árbol. Una variante posible es pasar solo $X$ y generar $Y$ al azar dentro de la operación.
Search (X) en $O(\log N)$ .
Busca un nodo con el valor de clave $X$ especificado. La implementación es la misma que para un árbol binario de búsqueda ordinario.
Erase (X) en $O(\log N)$ .
Busca un nodo con el valor de clave $X$ especificado y lo quita del árbol.
Build ( $X_1$ , …, $X_N$ ) en $O(N)$ .
Construye un árbol a partir de una lista de valores. Esto se puede hacer en tiempo lineal (suponiendo que $X_1, …, X_N$ están ordenados).
Union ( $T_1$ , $T_2$ ) en $O(M \log (N/M))$ .
Fusiona dos árboles, suponiendo que todos los elementos son distintos. Es posible alcanzar la misma complejidad si los elementos duplicados deben eliminarse durante la fusión.
Intersect ( $T_1$ , $T_2$ ) en $O(M \log (N/M))$ .
Calcula la intersección de dos árboles (es decir, sus elementos comunes). No consideraremos aquí la implementación de esta operación.

Además, por el hecho de que un treap es un árbol binario de búsqueda, puede implementar otras operaciones, como encontrar el $K$ -ésimo elemento más grande o encontrar el índice de un elemento.

Descripción de la implementación

En términos de implementación, cada nodo contiene $X$ , $Y$ y punteros a los hijos izquierdo ( $L$ ) y derecho ( $R$ ).

Implementaremos todas las operaciones requeridas usando solo dos operaciones auxiliares: Split y Merge.

Split

Split ( $T$ , $X$ ) separa el árbol $T$ en 2 subárboles $L$ y $R$ (que son los valores de retorno de split) de modo que $L$ contiene todos los elementos con clave $X_L \le X$ , y $R$ contiene todos los elementos con clave $X_R > X$ . Esta operación tiene complejidad $O (\log N)$ y se implementa con una recursión limpia:

Si el valor del nodo raíz (R) es $\le X$ , entonces L consistiría al menos de R->L y R. Luego llamamos split sobre R->R, y anotamos su resultado de split como L' y R'. Finalmente, L también contendría L', mientras que R = R'.
Si el valor del nodo raíz (R) es $> X$ , entonces R consistiría al menos de R y R->R. Luego llamamos split sobre R->L, y anotamos su resultado de split como L' y R'. Finalmente, L=L', mientras que R también contendría R'.

Así, el algoritmo de split es:

decidir a qué subárbol pertenecería el nodo raíz (izquierdo o derecho)
llamar recursivamente a split sobre uno de sus hijos
crear el resultado final reutilizando la llamada recursiva a split.

Merge

Merge ( $T_1$ , $T_2$ ) combina dos subárboles $T_1$ y $T_2$ y devuelve el árbol nuevo. Esta operación también tiene complejidad $O (\log N)$ . Funciona bajo el supuesto de que $T_1$ y $T_2$ están ordenados (todas las claves $X$ en $T_1$ son menores que las claves en $T_2$ ). Así, hay que combinar estos árboles sin violar el orden de las prioridades $Y$ . Para ello, elegimos como raíz el árbol que tiene mayor prioridad $Y$ en el nodo raíz, y llamamos recursivamente a Merge para el otro árbol y el subárbol correspondiente del nodo raíz seleccionado.

Insert

Ahora la implementación de Insert ( $X$ , $Y$ ) resulta obvia. Primero descendemos en el árbol (como en un árbol binario de búsqueda regular por X), y nos detenemos en el primer nodo en el que el valor de prioridad es menor que $Y$ . Hemos encontrado el lugar donde insertaremos el elemento nuevo. Luego, llamamos Split (T, X) sobre el subárbol que empieza en el nodo encontrado, y usamos los subárboles devueltos $L$ y $R$ como hijos izquierdo y derecho del nodo nuevo.

Como alternativa, insert se puede hacer partiendo el treap inicial en $X$ y haciendo $2$ merges con el nodo nuevo (véase la figura).

Erase

La implementación de Erase ( $X$ ) también es clara. Primero descendemos en el árbol (como en un árbol binario de búsqueda regular por $X$ ), buscando el elemento que queremos borrar. Una vez encontrado el nodo, llamamos Merge sobre sus hijos y colocamos el valor de retorno de la operación en el lugar del elemento que estamos borrando.

Como alternativa, podemos extraer el subárbol que contiene $X$ con $2$ operaciones split y fusionar los treaps restantes (véase la figura).

Build

Implementamos la operación Build con complejidad $O (N \log N)$ usando $N$ llamadas a Insert.

Union

Union ( $T_1$ , $T_2$ ) tiene complejidad teórica $O (M \log (N / M))$ , pero en la práctica funciona muy bien, probablemente con una constante oculta muy pequeña. Supongamos sin pérdida de generalidad que $T_1 \rightarrow Y > T_2 \rightarrow Y$ , es decir, la raíz de $T_1$ será la raíz del resultado. Para obtener el resultado, hay que fusionar los árboles $T_1 \rightarrow L$ , $T_1 \rightarrow R$ y $T_2$ en dos árboles que podrían ser hijos de la raíz de $T_1$ . Para ello, llamamos Split ( $T_2$ , $T_1\rightarrow X$ ), partiendo así $T_2$ en dos partes L y R, que luego combinamos recursivamente con los hijos de $T_1$ : Union ( $T_1 \rightarrow L$ , $L$ ) y Union ( $T_1 \rightarrow R$ , $R$ ), obteniendo así los subárboles izquierdo y derecho del resultado.

Implementación


struct item {
	int key, prior;
	item *l, *r;
	item () { }
	item (int key) : key(key), prior(rand()), l(NULL), r(NULL) { }
	item (int key, int prior) : key(key), prior(prior), l(NULL), r(NULL) { }
};
typedef item* pitem;

Esta es nuestra definición de item. Nótese que hay dos punteros a hijos, y una clave entera (para el BST) y una prioridad entera (para el heap). La prioridad se asigna usando un generador de números aleatorios.


void split (pitem t, int key, pitem & l, pitem & r) {
	if (!t)
		l = r = NULL;
	else if (t->key <= key)
        split (t->r, key, t->r, r),  l = t;
	else
        split (t->l, key, l, t->l),  r = t;
}

t es el treap a partir, y key es el valor del BST por el cual partir. Nótese que no hacemos return de los valores resultado en ningún lado; en cambio, los usamos así:


pitem l = nullptr, r = nullptr;
split(t, 5, l, r);
if (l) cout << "Left subtree size: " << (l->size) << endl;
if (r) cout << "Right subtree size: " << (r->size) << endl;

Esta función split puede ser difícil de entender, porque tiene tanto punteros (pitem) como referencias a esos punteros (pitem &l). Entendamos en palabras qué pretende la llamada split(t, k, l, r): “partir el treap t por el valor k en dos treaps, y guardar el treap izquierdo en l y el treap derecho en r”. ¡Bien! Ahora apliquemos esta definición a las dos llamadas recursivas, usando el análisis por casos de la sección anterior: (la primera condición if es un caso base trivial para un treap vacío)

Cuando el valor del nodo raíz es $\le$ key, llamamos split (t->r, key, t->r, r), que significa: “partir el treap t->r (subárbol derecho de t) por el valor key y guardar el subárbol izquierdo en t->r y el subárbol derecho en r”. Después de eso, asignamos l = t. Nótese ahora que el valor resultado l contiene t->l, t y también t->r (que es el resultado de la llamada recursiva que hicimos), todos ya fusionados en el orden correcto. Conviene detenerse a verificar que este resultado de l y r corresponde exactamente con lo que discutimos antes en la descripción de la implementación.
Cuando el valor del nodo raíz es mayor que key, llamamos split (t->l, key, l, t->l), que significa: “partir el treap t->l (subárbol izquierdo de t) por el valor key y guardar el subárbol izquierdo en l y el subárbol derecho en t->l”. Después de eso, asignamos r = t. Nótese ahora que el valor resultado r contiene t->l (que es el resultado de la llamada recursiva que hicimos), t y también t->r, todos ya fusionados en el orden correcto. Conviene detenerse a verificar que este resultado de l y r corresponde exactamente con lo que discutimos antes en la descripción de la implementación.

Si todavía cuesta entender la implementación, hay que mirarla de forma inductiva, es decir: no intentar descomponer las llamadas recursivas una y otra vez. Asumir que la implementación de split funciona correctamente en un treap vacío, luego intentar ejecutarla para un treap de un solo nodo, luego un treap de dos nodos, y así sucesivamente, reutilizando cada vez el conocimiento de que split en treaps más pequeños funciona.


void insert (pitem & t, pitem it) {
	if (!t)
		t = it;
	else if (it->prior > t->prior)
		split (t, it->key, it->l, it->r),  t = it;
	else
		insert (t->key <= it->key ? t->r : t->l, it);
}
 
void merge (pitem & t, pitem l, pitem r) {
	if (!l || !r)
		t = l ? l : r;
	else if (l->prior > r->prior)
		merge (l->r, l->r, r),  t = l;
	else
		merge (r->l, l, r->l),  t = r;
}
 
void erase (pitem & t, int key) {
	if (t->key == key) {
		pitem th = t;
		merge (t, t->l, t->r);
		delete th;
	}
	else
		erase (key < t->key ? t->l : t->r, key);
}
 
pitem unite (pitem l, pitem r) {
	if (!l || !r)  return l ? l : r;
	if (l->prior < r->prior)  swap (l, r);
	pitem lt, rt;
	split (r, l->key, lt, rt);
	l->l = unite (l->l, lt);
	l->r = unite (l->r, rt);
	return l;
}

Mantener los tamaños de los subárboles

Para extender la funcionalidad del treap, a menudo es necesario guardar el número de nodos en el subárbol de cada nodo: el campo int cnt en la estructura item. Por ejemplo, se puede usar para encontrar el $K$ -ésimo elemento más grande del árbol en $O (\log N)$ , o para encontrar el índice del elemento en la lista ordenada con la misma complejidad. La implementación de estas operaciones será la misma que para el árbol binario de búsqueda regular.

Cuando el árbol cambia (se agregan o quitan nodos, etc.), hay que actualizar cnt de algunos nodos en consecuencia. Crearemos dos funciones: cnt() devolverá el valor actual de cnt o 0 si el nodo no existe, y upd_cnt() actualizará el valor de cnt para este nodo asumiendo que para sus hijos L y R los valores de cnt ya fueron actualizados. Evidentemente basta con agregar llamadas a upd_cnt() al final de insert, erase, split y merge para mantener los valores de cnt al día.


int cnt (pitem t) {
	return t ? t->cnt : 0;
}
 
void upd_cnt (pitem t) {
	if (t)
		t->cnt = 1 + cnt(t->l) + cnt (t->r);
}

Construir un Treap en $O (N)$ en modo offline {data-toc-label=“Construir un Treap en O(N) en modo offline”}

Dada una lista ordenada de claves, es posible construir un treap más rápido que insertando las claves una a una, lo cual toma $O(N \log N)$ . Como las claves están ordenadas, un árbol binario de búsqueda balanceado se puede construir fácilmente en tiempo lineal. Los valores de heap $Y$ se inicializan al azar y luego se pueden heapificar de forma independiente de las claves $X$ para construir el heap en $O(N)$ .


void heapify (pitem t) {
	if (!t) return;
	pitem max = t;
	if (t->l != NULL && t->l->prior > max->prior)
		max = t->l;
	if (t->r != NULL && t->r->prior > max->prior)
		max = t->r;
	if (max != t) {
		swap (t->prior, max->prior);
		heapify (max);
	}
}
 
pitem build (int * a, int n) {
	// Construir un Treap sobre los valores {a[0], a[1], ..., a[n - 1]}
	if (n == 0) return NULL;
	int mid = n / 2;
	pitem t = new item (a[mid], rand ());
	t->l = build (a, mid);
	t->r = build (a + mid + 1, n - mid - 1);
	heapify (t);
	upd_cnt(t)
	return t;
}

Nota: llamar a upd_cnt(t) solo es necesario si se necesitan los tamaños de los subárboles.

El enfoque de arriba siempre da un árbol perfectamente balanceado, lo cual en general es bueno para fines prácticos, pero a costa de no preservar las prioridades que se asignaron inicialmente a cada nodo. Por eso, este enfoque no es viable para resolver el siguiente problema:

[acmsguru - Cartesian Tree](https://codeforces.com/problemsets/acmsguru/problem/99999/155)

Dada una secuencia de pares

(x_i, y_i)

, construir un árbol cartesiano sobre ellos. Todos los

x_i

y todos los

y_i

son únicos.

Nótese que en este problema las prioridades no son aleatorias, así que insertar los vértices uno por uno podría dar una solución cuadrática.

Una de las soluciones posibles aquí es encontrar, para cada elemento, los elementos más cercanos a la izquierda y a la derecha que tienen una prioridad menor que este elemento. Entre estos dos elementos, el que tiene mayor prioridad debe ser el padre del elemento actual.

Este problema se puede resolver con una modificación de la pila de mínimo en tiempo lineal:


void connect(auto from, auto to) {
    vector<pitem> st;
    for(auto it: ranges::subrange(from, to)) {
        while(!st.empty() && st.back()->prior > it->prior) {
            st.pop_back();
        }
        if(!st.empty()) {
            if(!it->p || it->p->prior < st.back()->prior) {
                it->p = st.back();
            }
        }
        st.push_back(it);
    }
}
 
pitem build(int *x, int *y, int n) {
    vector<pitem> nodes(n);
    for(int i = 0; i < n; i++) {
        nodes[i] = new item(x[i], y[i]);
    }
    connect(nodes.begin(), nodes.end());
    connect(nodes.rbegin(), nodes.rend());
    for(int i = 0; i < n; i++) {
        if(nodes[i]->p) {
            if(nodes[i]->p->key < nodes[i]->key) {
                nodes[i]->p->r = nodes[i];
            } else {
                nodes[i]->p->l = nodes[i];
            }
        }
    }
    return nodes[min_element(y, y + n) - y];
}

Treaps implícitos

El treap implícito es una modificación simple del treap regular que es una estructura de datos muy poderosa. De hecho, el treap implícito se puede considerar como un arreglo con los siguientes procedimientos implementados (todos en $O (\log N)$ en modo online):

Insertar un elemento en el arreglo en cualquier posición
Eliminar un elemento arbitrario
Encontrar la suma, el elemento mínimo / máximo, etc. en un intervalo arbitrario
Suma, pintado sobre un intervalo arbitrario
Invertir los elementos en un intervalo arbitrario

La idea es que las claves deben ser los índices de los elementos en el arreglo, con indexación desde cero. Pero no guardaremos estos valores de forma explícita (de lo contrario, por ejemplo, insertar un elemento provocaría cambios de la clave en $O (N)$ nodos del árbol).

Nótese que la clave de un nodo es el número de nodos menores que él (tales nodos pueden estar no solo en su subárbol izquierdo sino también en los subárboles izquierdos de sus ancestros). Más concretamente, la clave implícita de algún nodo T es el número de vértices $cnt (T \rightarrow L)$ en el subárbol izquierdo de este nodo más valores similares $cnt (P \rightarrow L) + 1$ para cada ancestro P del nodo T, si T está en el subárbol derecho de P.

Ahora queda claro cómo calcular rápido la clave implícita del nodo actual. Como en todas las operaciones llegamos a cualquier nodo descendiendo en el árbol, podemos simplemente acumular esta suma y pasarla a la función. Si vamos al subárbol izquierdo, la suma acumulada no cambia; si vamos al subárbol derecho, aumenta en $cnt (T \rightarrow L) +1$ .

Aquí están las nuevas implementaciones de Split y Merge:


void merge (pitem & t, pitem l, pitem r) {
	if (!l || !r)
		t = l ? l : r;
	else if (l->prior > r->prior)
		merge (l->r, l->r, r),  t = l;
	else
		merge (r->l, l, r->l),  t = r;
	upd_cnt (t);
}
 
void split (pitem t, pitem & l, pitem & r, int key, int add = 0) {
	if (!t)
		return void( l = r = 0 );
	int cur_key = add + cnt(t->l); // clave implícita
	if (key <= cur_key)
		split (t->l, l, t->l, key, add),  r = t;
	else
		split (t->r, t->r, r, key, add + 1 + cnt(t->l)),  l = t;
	upd_cnt (t);
}

En la implementación de arriba, después de la llamada $split(T, T_1, T_2, k)$ , el árbol $T_1$ consistirá en los primeros $k$ elementos de $T$ (es decir, en los elementos cuya clave implícita es menor que $k$ ) y $T_2$ consistirá en el resto.

Ahora consideremos la implementación de varias operaciones sobre treaps implícitos:

Insertar un elemento.
Supongamos que hay que insertar un elemento en la posición $pos$ . Partimos el treap en dos partes, que corresponden a los arreglos $[0..pos-1]$ y $[pos..sz]$ ; para ello llamamos $split(T, T_1, T_2, pos)$ . Luego podemos combinar el árbol $T_1$ con el vértice nuevo llamando $merge(T_1, T_1, \text{new item})$ (es fácil ver que se cumplen todas las precondiciones). Finalmente, combinamos de nuevo los árboles $T_1$ y $T_2$ en $T$ llamando $merge(T, T_1, T_2)$ .
Borrar un elemento.
Esta operación es aún más fácil: encontrar el elemento a borrar $T$ , hacer merge de sus hijos $L$ y $R$ , y reemplazar el elemento $T$ por el resultado del merge. De hecho, borrar un elemento en el treap implícito es exactamente igual que en el treap regular.
Encontrar la suma / el mínimo, etc. en el intervalo.
Primero, crear un campo adicional $F$ en la estructura item para guardar el valor de la función objetivo para el subárbol de este nodo. Este campo es fácil de mantener de forma similar a mantener los tamaños de los subárboles: crear una función que calcule este valor para un nodo a partir de los valores de sus hijos y agregar llamadas a esta función al final de todas las funciones que modifican el árbol.
Segundo, hay que saber cómo procesar una consulta sobre un intervalo arbitrario $[A; B]$ .
Para obtener la parte del árbol que corresponde al intervalo $[A; B]$ , hay que llamar $split(T, T_2, T_3, B+1)$ , y luego $split(T_2, T_1, T_2, A)$ : después de esto $T_2$ consistirá en todos los elementos del intervalo $[A; B]$ , y solo en ellos. Por lo tanto, la respuesta a la consulta estará guardada en el campo $F$ de la raíz de $T_2$ . Después de responder la consulta, hay que restaurar el árbol llamando $merge(T, T_1, T_2)$ y $merge(T, T, T_3)$ .
Suma / pintado sobre el intervalo.
Actuamos de forma similar al párrafo anterior, pero en lugar del campo F guardaremos un campo add que contendrá el valor agregado para el subárbol (o el valor con el que se pinta el subárbol). Antes de realizar cualquier operación hay que “empujar” (push) este valor correctamente: es decir, cambiar $T \rightarrow L \rightarrow add$ y $T \rightarrow R \rightarrow add$ , y limpiar add en el nodo padre. De esta forma, después de cualquier cambio en el árbol la información no se perderá.
Invertir el intervalo.
Esto es otra vez similar a la operación anterior: hay que agregar un flag booleano rev y ponerlo en true cuando el subárbol del nodo actual tiene que invertirse. “Empujar” este valor es un poco más complicado: intercambiamos los hijos de este nodo y ponemos este flag en true para ellos.

Aquí hay un ejemplo de implementación del treap implícito con inversión sobre el intervalo. Para cada nodo guardamos un campo llamado value que es el valor real del elemento del arreglo en la posición actual. También damos la implementación de la función output(), que imprime un arreglo que corresponde al estado actual del treap implícito.


typedef struct item * pitem;
struct item {
	int prior, value, cnt;
	bool rev;
	pitem l, r;
};
 
int cnt (pitem it) {
	return it ? it->cnt : 0;
}
 
void upd_cnt (pitem it) {
	if (it)
		it->cnt = cnt(it->l) + cnt(it->r) + 1;
}
 
void push (pitem it) {
	if (it && it->rev) {
		it->rev = false;
		swap (it->l, it->r);
		if (it->l)  it->l->rev ^= true;
		if (it->r)  it->r->rev ^= true;
	}
}
 
void merge (pitem & t, pitem l, pitem r) {
	push (l);
	push (r);
	if (!l || !r)
		t = l ? l : r;
	else if (l->prior > r->prior)
		merge (l->r, l->r, r),  t = l;
	else
		merge (r->l, l, r->l),  t = r;
	upd_cnt (t);
}
 
void split (pitem t, pitem & l, pitem & r, int key, int add = 0) {
	if (!t)
		return void( l = r = 0 );
	push (t);
	int cur_key = add + cnt(t->l);
	if (key <= cur_key)
		split (t->l, l, t->l, key, add),  r = t;
	else
		split (t->r, t->r, r, key, add + 1 + cnt(t->l)),  l = t;
	upd_cnt (t);
}
 
void reverse (pitem t, int l, int r) {
	pitem t1, t2, t3;
	split (t, t1, t2, l);
	split (t2, t2, t3, r-l+1);
	t2->rev ^= true;
	merge (t, t1, t2);
	merge (t, t, t3);
}
 
void output (pitem t) {
	if (!t)  return;
	push (t);
	output (t->l);
	printf ("%d ", t->value);
	output (t->r);
}

Literatura

Blelloch, Reid-Miller “Fast Set Operations Using Treaps”