¿Cómo unir y dividir funciona en un Treap al agregar o eliminar un elemento?

Puede haber alguna confusión aquí: no se une / divide un tratamiento al agregar / eliminar elementos.

Describiré dos algoritmos de unión / división, la versión clásica que probablemente conozcas y una versión mejorada que toma algunos atajos. En lo sucesivo, INSERT y DELETE se refieren a las operaciones de inserción y eliminación de treap, incluidas las rotaciones de árbol necesarias para corregir el orden de almacenamiento dinámico. DESCARGAR significa cortar todos los enlaces hacia / desde el nodo en cuestión y tirarlo a la basura.

Una advertencia muy importante: los dos algoritmos de combinación de treap a continuación suponen que los dos sub-treaps son el resultado de una división anterior, con prioridades sin cambios . Si intenta unir dos treaps arbitrarios, cuyo rango de valores puede superponerse, probablemente sea mejor construir un treap completamente nuevo INSERTANDO individualmente los valores de los dos sub-treaps.

• Cómo implementar un algoritmo de sincronización de reloj Berkeley en C ++
• ¿Se puede implementar BFS sin usar una cola? En caso afirmativo, ¿cuál es la mejor complejidad que se puede lograr?
• ¿Puede un gráfico en el que los pesos de los bordes no son necesariamente distintos tener más de un MST? Si es así, da un ejemplo. Si no, justifíquelo.
• ¿Qué tan importante es el DS y Algo?
• Cómo encontrar la complejidad de tiempo de caso promedio de un algoritmo

TREAP CLÁSICO UNIR / DIVIDIR
Prerrequisitos:

1. Las prioridades de nodo posibles mínimas ([matemáticas] P_ {min} [/ matemáticas]) y máximas ([matemáticas] P_ {máx} [/ matemáticas]) están reservadas. Por ejemplo, si está utilizando un número entero de 32 bits para almacenar prioridades, [math] P_ {min} = 0 [/ math] para unirse y [math] P_ {max} = 2 ^ {32} -1 [/ matemáticas] para dividir, entonces el resto puede asignarse aleatoriamente.
2. Para dividir un treap, conoce un valor [math] x [/ math] que se encuentra entre los valores de los dos nodos en los que desea dividir el treap.
3. Para unir dos treaps, todos los valores en un treap ([math] T_1 [/ math]) deben ser menores que el valor más pequeño en el segundo ([math] T_2 [/ math]). Además, conoce un valor [matemático] x [/ matemático] que está entre los dos rangos.

Para dividir un tratamiento en dos:

1. AGREGUE [math] x [/ math] al árbol con prioridad [math] P_ {max} [/ math].
2. Gire treap para corregir el orden de almacenamiento dinámico: [math] x [/ math] ahora es la raíz de treap, y sus elementos secundarios son los árboles divididos.
3. DESECHAR [matemáticas] x [/ matemáticas].

Para unir dos treaps:

1. Cree un nodo para [math] x [/ math] con prioridad [math] P_ {min} [/ math].
2. Convierta [math] T_1 [/ math] en su hijo izquierdo y [math] T_2 [/ math] en su hijo derecho, para que tenga un BST adecuado.
3. Gire para corregir el orden de almacenamiento dinámico: [math] x [/ math] ahora es un nodo hoja.
4. DESECHAR [matemáticas] x [/ matemáticas].

MEJOR TREAP JOIN / SPLIT
Prerrequisitos:

1. [math] P_ {max} [/ math] está reservado (ver arriba para su definición).
2. Para dividir un treap, conoce un valor [math] x [/ math] que ya está en el treap, alrededor del cual desea dividir. (Por ejemplo, si todos los valores contiguos alrededor del punto de división ya están en el árbol, el método clásico no se puede aplicar. Por supuesto, [math] x [/ math] permanecerá en uno de los sub-treaps).
3. Para unir dos treaps, todos los valores en un treap ([math] T_1 [/ math]) deben ser menores que el valor más pequeño en el segundo ([math] T_2 [/ math]). No se requiere ningún valor intermedio [matemática] x [/ matemática], a diferencia del método clásico.

Para dividir un tratamiento en dos: [1]

1. Encuentre el nodo con [math] x [/ math].
2. Guarde su prioridad original ([matemáticas] P_ {orig} [/ matemáticas]).
3. Asigne prioridad [matemática] x [/ matemática] [matemática] P_ {max} [/ matemática].
4. Gire treap para corregir el orden de almacenamiento dinámico: [matemáticas] x [/ matemáticas] ahora es el nodo raíz y la “raíz” de [matemáticas] T_2 [/ matemáticas], mientras que [matemáticas] T_1 [/ matemáticas] es su hijo izquierdo.
5. Eliminar [math] T_1 [/ math] de treap – [math] x [/ math] ahora solo tiene un hijo correcto.
6. Asigne prioridad [matemática] x [/ matemática] [matemática] P_ {orig} [/ matemática].
7. Gire [math] T_2 [/ math] para corregir el orden de almacenamiento dinámico.

Para unir dos treaps: [2]

1. Cree un nodo ficticio: el valor y la prioridad son irrelevantes. Haga su hijo izquierdo [matemática] T_1 [/ matemática] y su hijo derecho [matemática] T_2 [/ matemática].
2. RETIRE el nodo ficticio: su único propósito era vincular los dos subtratamientos juntos, y las rotaciones de ordenamiento del montón necesarias para mover el nodo ficticio a una posición de hoja para descartarlo volverán a colocar todo en su lugar correcto.

NOTAS
[1] Inspirado por esta respuesta en stackoverflow.com.
[2] Desvergonzadamente robado de la diapositiva 14 aquí.