Treap con claves implícitas

Question

Hay una estructura de datos llamada Treap:. Eso es un árbol binario de búsqueda al azar, que es también un montón en los llamados "prioridades" generados al azar

Hay una variación de esta estructura, donde las claves son implícitas, que no se almacenan en el árbol, pero consideramos que el índice ordenado del nodo en el árbol como la clave de este nodo. Necesitamos almacenar el tamaño del subárbol en cada nodo en lugar de llave. Esta técnica nos permite pensar en Treap como una especie de matriz, que soporta las porciones de operación en O (log N) tiempo:. Inserción, deleción, reversión de submatriz, el cambio en el intervalo y así sucesivamente

Me sabe un poco acerca de esta estructura, pero no tanto. Traté de google, pero he encontrado sólo un montón de artículos sobre Treap sí, pero nada de esto "Treap implícita" / "lista indexada". Incluso no sé su nombre, porque mi lengua materna no es Inglés y una conferencia que he escuchado utilizado el término nativo de la estructura, no Inglés término original. Este término nativo puede traducirse directamente en Inglés como "Treap en las teclas implícitas" o "árbol cartesiano en las teclas implícitas".

me puede punto cualquiera en el artículo acerca de esta estructura o dime su nombre original? Gracias.

P.S. Lo siento si mi Inglés no era lo bastante comprensible.

UPD:. Algunos explicación adicional sobre la estructura Busco

Considere una Treap habitual con las prioridades y las claves elegidas al azar, que son los datos reales de los usuarios almacenados en el árbol. Entonces imaginemos que tenemos alguna otra información del usuario almacenada en cada nodo, y las teclas son más que las claves de búsqueda. El siguiente paso es calcular y mantener el tamaño sub-árbol en cada nodo: hay que actualizar este parámetro después de cada Combinar / Dividir / añadir / quitar, pero nos permite encontrar, por ejemplo, k-ésimo elemento del árbol en O (log N) tiempo.

Cuando tenemos tamaños de subárbol en cada nodo, podemos tirar las llaves de distancia e imaginar que Treap representa un conjunto de datos de usuario en el recorrido en orden. El índice de matriz de cada elemento se puede calcular fácilmente a partir de tamaños de subárbol. Ahora podemos añadir / eliminar un elemento en el medio de matriz o dividir esta matriz - todo en O (log N) Tiempo

.

También puede hacer "múltiple" operación - por ejemplo, añadir un valor constante para todos los elementos de nuestra "matriz". Para implementar esto, tenemos que hacer esta operación retrasa, añadir un parámetro en cada nodo que representa una constante retraso que tiene que ser "más adelante", agregó a todos los elementos del subconjunto de este nodo, y "empujar" el cambia de arriba a abajo como necesario. La adición de una constante al subconjunto o pintar (marcado) el subconjunto se puede hacer retardada de esta manera, como la inversión de la submatriz (aquí la información retardada en el nodo en el bit "submatriz tiene que ser invertida"), y así sucesivamente.

UPD2: fragmento de código - pieza de la pequeña cantidad de información que he encontrado. No se dan cuenta cirílico :) Las palabras "? ??????? ??????" significa en la traducción directa "con la clave implícita".

Answer 1

Puede encontrar esta estructura de datos en el documento de Kaplan y Verbin en la clasificación permutaciones firmadas por reversiones (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 el uso de llaves, que son asignados al azar. Si quita las llaves, no veo cómo se puede tener un Treap: así que tal vez no he entendido bien su pregunta. O tal vez usted se refiere a la alternativa a treaps, el aleatorizados árbol binario de búsqueda . Ambas estructuras de datos utilizan la misma idea de que se puede alcanzar en el caso promedio complejidad asegurándose de que su apariencia de árbol como un árbol promedio (en lugar de un caso patológico).

Con los treaps, esto se hace uso de prioridades de azar y el equilibrio.

Con asignó al azar a los árboles binarios, la aleatoriedad es el único incluido durante la construcción: es decir, cuando se inserta un nodo en el árbol T, que tiene una probabilidad de 1 / (tamaño (T) + 1) para estar en la raíz, donde el tamaño (T) es el número de nodos de T; y por supuesto si el nodo no está insertado en la raíz, continúa de forma recursiva hasta que se añade. (Véanse los artículos de mi C. Martínez para un estudio detallado de estos árboles.)

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

Si esto no es lo que estabas buscando, tal vez usted podría compartir alguna información adicional es: ¿su profesor cualquiera mención que podrían haber trabajado en esta estructura, donde se hizo aquí esta conferenciante y lo que su / su nacionalidad. Puede que no lo parezca, pero a sabiendas de su lengua materna podría ser una pista importante, ya que por lo general puede PEG hacia abajo y algoritmos / estructuras de datos para un país específico que lo originó.

Answer 3

Tal vez usted está buscando un cuerda (forma compleja de cadena) modificado para sus necesidades de operaciones de retraso. Lo interesante es que no es una cuestión abierta con respecto cuerdas aquí y ahora .

Answer 4

No creo que hay un nombre para esa estructura de datos, ya que es simplemente una combinación de dos conceptos ortogonales. Se podría utilizar claves implícitas como esto con casi cualquier estructura de datos de árbol de auto-equilibrio.

Es posible que desee echar un vistazo a los árboles chivo expiatorio, ya que utilizan el tamaño subárbol ya para el reequilibrio y no requieren ningún tipo de gastos por nodo.