¿Cómo implementarías un treap con split y merge?

1. Problema y contexto

Mantener un conjunto ordenado dinámico que soporte búsqueda, inserción, eliminación y divisiones ocasionales por clave seguidas de una fusión. Implementa un treap: cada nodo satisface un invariante de árbol binario de búsqueda en key y un invariante de max-heap en prioridades aleatorias priority. Asume claves únicas primero y luego explica el manejo de duplicados.

2. Qué está evaluando el entrevistador

• Explicar qué proporciona el invariante de BST y qué proporciona el de heap.
• Componer insert y erase a partir de split y merge en lugar de limitarse a memorizar rotaciones.
• Indicar que O(log n) es esperado y que la calidad aleatoria y las colisiones de prioridad afectan la forma del árbol.
• Mantener el tamaño del subárbol o agregados, con un orden de actualización correcto y manejo de hijos vacíos.

3. Preguntas para aclarar primero

• ¿Son únicas las claves? Si se permiten duplicados, coloca las claves iguales de forma consistente en un lado o usa (key, id) como clave compuesta.
• ¿Las prioridades son suministradas por quienes llaman o se generan internamente? La generación interna requiere una fuente aleatoria, una política de colisiones y una semilla de prueba reproducible.
• ¿split coloca la clave límite a la izquierda o requiere una división estricta por menor que? Esto cambia el código de inserción y de consultas por rango.
• ¿Necesitamos estadísticas de orden k-ésimo, sumas de rango o una secuencia implícita? En ese caso, cada mutación debe actualizar los metadatos del subárbol.

4. Estructura de respuesta en 30 segundos

“Mantengo el orden de BST por clave y el orden de max-heap mediante una prioridad aleatoria. Las operaciones centrales son split(T, key), que devuelve claves como máximo iguales al límite y claves mayores que este, y merge(L, R), que asume que cada clave en L es como máximo igual a cada clave en R y elige la raíz con mayor prioridad. Insert divide alrededor de la nueva clave y la fusiona de vuelta; erase fusiona los hijos del objetivo. Cada retorno recursivo actualiza el tamaño. La altura y las operaciones son esperadas en O(log n), no en el peor caso, por lo que el código de producción necesita pruebas reproducibles, monitoreo de profundidad o un árbol con un límite determinista.”

5. Razonamiento paso a paso

Primero, fija los invariantes. Para cada nodo, las claves izquierdas no son mayores que su clave, las claves derechas son mayores y su prioridad es al menos igual a las prioridades de ambos hijos. Este artículo utiliza “las claves iguales van a la izquierda”; un (key, uniqueId) compuesto es otra política inequívoca.

Segundo, implementa split. Si la clave de la raíz es como máximo el límite, la raíz y el subárbol izquierdo pertenecen al resultado izquierdo, así que se recurre en el hijo derecho. De lo contrario, se recurre en el hijo izquierdo para el resultado derecho. Reconecta el hijo devuelto y actualiza el tamaño. Solo se visita un camino de raíz a hoja.

Tercero, implementa merge. Maneja un árbol vacío primero. Si la raíz izquierda tiene mayor prioridad, consérvala como raíz y fusiona su hijo derecho con el árbol derecho; de lo contrario, conserva la raíz derecha y fusiona el árbol izquierdo con su hijo izquierdo. La precondición de que cada clave izquierda no es mayor que cada clave derecha preserva el orden de BST.

Cuarto, compone las operaciones. Para insert, split(root, key) y luego merge(merge(left, node), right). Para erase, reemplaza el objetivo con merge(node.left, node.right). Search desciende por clave y no necesita split. Si se almacena el tamaño, ejecuta size = 1 + size(left) + size(right) después de cada split, merge, insert y erase.

Quinto, analiza la complejidad y los fallos. Las prioridades aleatorias hacen que la forma sea comparable a un BST construido aleatoriamente, proporcionando operaciones esperadas en O(log n); CP-Algorithms documenta split, merge, inserción y eliminación logarítmicas esperadas. Las prioridades casi monotónicas aún pueden crear un árbol O(n), así que usa semillas fijas en las pruebas, monitorea la altura o elige árboles AVL o rojinegros cuando un límite de peor caso sea obligatorio.

6. Respuesta de muestra de alta calidad

“Primero acordaría la semántica de claves duplicadas y luego implementaría dos primitivas. split devuelve árboles izquierdo y derecho alrededor de un límite, divide recursivamente un hijo y reconecta la raíz. merge asume que todas las claves izquierdas no son mayores que las claves derechas y elige la raíz con mayor prioridad. Insert divide y coloca el nuevo nodo entre los resultados; erase fusiona los hijos del objetivo. Actualizar el tamaño del subárbol también permite la selección del k-ésimo elemento. Las prioridades aleatorias proporcionan una altura esperada de O(log n), no una garantía de peor caso, por lo que probaría con semillas fijas en árboles vacíos, duplicados y trazas largas, monitorearía la profundidad y elegiría un árbol rojinegro cuando los límites deterministas sean importantes.”

7. Errores comunes

• Error → Mantener solo el orden de BST → las inserciones ordenadas siguen formando una lista enlazada → mantén también el invariante de heap por prioridad.
• Error → Hacer merge sin verificar los rangos de claves → las búsquedas toman el camino equivocado → documenta que las claves izquierdas no son mayores que las claves derechas.
• Error → Olvidar actualizar el tamaño del subárbol después de split → las estadísticas de k-ésimo elemento y de rango se desvían → extrae/actualiza los metadatos inmediatamente después de reconectar los hijos.
• Error → Tratar el O(log n) esperado como una garantía de peor caso → prioridades adversarias pueden crear un árbol profundo → monitorea la profundidad o usa árboles AVL/rojinegros.
• Error → Política de duplicados inconsistente entre search, erase y split → las claves iguales terminan en el subárbol incorrecto → usa una clave compuesta o una única regla de límite.

8. Preguntas de seguimiento

¿Cómo soportas el k-ésimo elemento más pequeño?

Almacena el tamaño del subárbol en cada nodo. Compara k con el tamaño izquierdo mientras desciendes; actualiza el tamaño en cada split, merge, inserción y eliminación, o la consulta se volverá incorrecta.

¿Cómo puede un treap representar una secuencia implícita?

No almacenes claves explícitas. Define la posición de un nodo a partir del tamaño de su subárbol izquierdo más las contribuciones de sus ancestros. Divide por posición y fusiona de vuelta para soportar inserción, eliminación y agregados por rango; las banderas perezosas (lazy flags) pueden manejar inversión o suma en rangos.

¿Cuándo evitarías un treap?

Elige AVL, un árbol rojinegro o un índice de base de datos cuando se requiera un O(log n) estricto en el peor caso, aleatoriedad controlada o una implementación concurrente madura. Los treaps intercambian esa garantía por un código corto y una composición flexible de split/merge.