Treap con claves implícitas

Question

Hay una estructura de datos llamada treap: es un árbol de búsqueda binaria aleatorio, que también es un montón de las denominadas "prioridades" generadas aleatoriamente.

Hay una variación de esta estructura, donde las claves son implícitas, no se almacenan en el árbol, pero consideramos que el índice ordenado del nodo en el árbol es la clave de este nodo. Necesitamos almacenar el tamaño del subárbol en cada nodo en lugar de la clave. Esta técnica nos permite pensar en la detección como algún tipo de matriz, que admite muchas operaciones en el tiempo O (log N): inserción, eliminación, reversión de subcampo, cambio en el intervalo, etc.

Conozco un poco sobre esta estructura, pero no tanto. Intenté buscarlo en Google, pero solo encontré muchos artículos sobre el propio engaño, pero nada acerca de este "fraude implícito"/"lista indexada". Incluso no sé su nombre, porque mi lengua materna no es el inglés y la conferencia que escuché utilizó el término nativo de estructura, no el término original en inglés. Este término nativo se puede traducir directamente en inglés como "Treap on the implicit keys" o "Cartesian tree on the implicit keys".

¿Alguien puede señalarme el artículo sobre esta estructura o decirme su nombre original? Gracias.

P.S. Lo siento si mi inglés no era lo suficientemente comprensible.

UPD: Alguna explicación extra sobre la estructura que estoy buscando.

Considere un tratamiento habitual con prioridades y claves elegidas al azar, que son datos reales del usuario almacenados en el árbol. Entonces imaginemos que tenemos otra información de usuario almacenada en cada nodo, y las claves no son más que las claves de búsqueda. El siguiente paso es calcular y mantener el tamaño del subárbol en cada nodo: tenemos que actualizar este parámetro después de cada Combinar/Dividir/Agregar/Eliminar, pero nos permite encontrar, por ejemplo, el elemento Kth del árbol en O (log N) hora.

Cuando tenemos tamaños de subárbol en cada nodo, podemos tirar las claves e imaginar que el tratamiento representa una matriz de datos de usuario en el recorrido inorden. El índice de matriz de cada elemento se puede calcular fácilmente a partir de los tamaños de subárbol. Ahora podemos agregar/eliminar un elemento en el medio de la matriz o dividir esta matriz, todo en tiempo O (registrar N).

También podemos realizar operaciones "múltiples", por ejemplo, agregar un valor constante a todos los elementos de nuestra "matriz". Para implementar esto, tenemos que retrasar esta operación, agregar un parámetro en cada nodo que represente una constante diferida que se debe agregar "más adelante" a todos los elementos del subcampo de este nodo, y "empujar" los cambios hacia arriba como necesario. Agregar una constante a subcampo o pintar (marcar) el subcampo puede retrasarse de esta manera, como invertir el subcampo (aquí la información retrasada en el nodo en el subarreglo de bit "tiene que invertirse"), y así sucesivamente.

UPD2: Aquí está code snippet - parte de la pequeña cantidad de información que he encontrado. No se da cuenta del cirílico :) Las palabras "с неявным ключом" significan en traducción directa "con clave implícita".

Answer 1

Puede encontrar esta estructura de datos en el documento de Kaplan y Verbin sobre la clasificación de permutaciones firmadas por revocaciones (página 7, sección 3.1): http://www.math.jussieu.fr/~fouquet/ENSEIGNEMENT/PROJETS/kaplan.pdf.

Answer 2

La idea clave (sin juego de palabras) en treaps es utilizar claves, que son aleatorias. Si quitas las llaves, no veo cómo puedes tener una trampa: por lo tanto, tal vez malentendí tu pregunta. O tal vez se está refiriendo a la alternativa a treaps, el árbol de búsqueda binaria aleatorio . Ambas estructuras de datos usan la misma idea que usted puede lograr la complejidad de un caso promedio al asegurarse de que su árbol se vea como un árbol promedio (en lugar de un caso patológico).

Con las trampas, puede hacer esto usando prioridades aleatorias y equilibrado.

Con árboles binarios aleatorizados, la aleatoriedad se incluye únicamente durante la construcción: es decir, cuando inserta un nodo en el árbol T, tiene la probabilidad 1/(tamaño (T) + 1) de estar en la raíz, donde el tamaño (T) es la cantidad de nodos de T; y, por supuesto, si el nodo no está insertado en la raíz, continúa recursivamente hasta que se agrega. (Consulte los artículos de mi C. Martinez para obtener un estudio detallado de estos árboles).

Esta estructura de datos se comporta exactamente como un tiento, pero utiliza un mecanismo diferente que no requiere claves.

Si esto no es lo que estaba buscando, tal vez podría compartir información adicional: ¿mencionó su profesor a alguien que podría haber trabajado en esta estructura, dónde estuvo este profesor y cuál es su nacionalidad? Puede que no parezca así, pero conocer su lengua materna podría ser una pista importante ya que generalmente puede vincular algoritmos/estructuras de datos a un país específico que lo originó.

Answer 3

No creo que haya un nombre para esa estructura de datos ya que es simplemente una combinación de dos conceptos ortogonales. Podría usar claves implícitas como esta con casi cualquier estructura de datos de árbol de autoequilibrado.

Es posible que desee echar un vistazo a los árboles Scapegoat, ya que utilizan el tamaño del subárbol para el reequilibrio y no requieren ninguna sobrecarga por cada nodo.

Answer 4

Quizás esté buscando Rope (forma compleja de cadena) modificada a sus necesidades para operaciones retrasadas. Lo interesante es que hay una pregunta abierta con respecto a las cuerdas right here right now.