Unión más rápida de estructuras de datos tipo treap con aproximadamente el mismo tamaño

16

Dados dos árboles AVL y T 2 y un valor t r tal que x T 1 , y T 2 , x < t r < y , es fácil construir un nuevo árbol AVL que contenga t r y los valores en T 1 y T 2 en el tiempo O ( 1 + | h ( T 1 ) - h ( TT1T2trxT1,yT2,x<tr<ytrT1T2 , donde h ( T ) denota la altura de un árbol T (siempre que los árboles almacenen su altura).O(1+|h(T1)h(T2)|)h(T)T

Esto también es posible para árboles rojo-negros, y supongo que muchos otros tipos de árboles equilibrados también.

¿Es esto posible para treaps o estructuras de datos tipo treap? ¿Qué pasa si dejamos de lado ?tr

El documento treaps en Algorithmica muestra cómo hacer esto en tiempo esperado. Si hay una manera de realizar O (1) unión esperada en treaps (o estructuras de datos similares a treap) con aproximadamente el mismo tamaño (o prioridad de raíz), creo que podría ser posible usar un truco de Kaplan & Tarjan de bootstrapping las espinas para hacer treaps (o estructuras de datos similares a treap) con unión doblemente logarítmica.O(min(h(T1),h(T2)))

jbapple
fuente
Aquí hay un código de Haskell que escribí mostrando una unión rápida de árboles AVL con aproximadamente el mismo tamaño: haskell.pastebin.com/nfGV8Ffz
jbapple
Dudo que sea posible, porque parece (sin una prueba) que la profundidad esperada del nuevo nodo (que contiene el valor t_r) es más que una constante incluso en el caso donde h (T_1) = h (T_2).
Tsuyoshi Ito
Tsuyoshi Ito: Estoy de acuerdo, si asigna una prioridad al nuevo nodo de la misma manera que asigna prioridades a otros nodos. ¿Qué sucede si le asigna una prioridad garantizada que sea mayor que la de los nodos raíz? Eso destruye la naturaleza IID de las prioridades, pero ¿qué pasa si luego marca las otras prioridades como cambiadas, de alguna manera, como los caminos en los persistentes árboles rojo-negros se marcan en los puntos finales? ¿O qué pasa si uno almacena los valores solo en las hojas de un treap y realiza una unión sin un t_r?
jbapple
Los nodos en treaps con n descendientes han dejado descendientes con probabilidad 1 / n. Esto puede contribuir a los largos tiempos de fusión incluso para treaps de igual tamaño: la selección de una nueva raíz requiere navegar hacia ella, lo que, dado que la profundidad promedio en el árbol es Theta (lg n), también toma tiempo Theta (lg n). ¿Qué sucede si un nodo treap con n descendientes ha dejado hijos con probabilidad (n elija i) / 2 ^ n, y los valores solo se almacenan en hojas como en un árbol B +? Luego, unir dos redistribuciones de igual tamaño distribuye un pequeño número de elementos de un árbol a otro en expectativa.
jbapple
Si mis cálculos son correctos, el número esperado de elementos redistribuidos es Theta (sqrt n), que, suponiendo que todo lo demás pueda resolverse (como la propiedad de búsqueda de dedos), todavía tomaría el tiempo de Theta (lg n) en expectativa. ¿Qué pasa con el uso de una distribución aún más estricta?
jbapple

Respuestas:

3

No, no es posible hacer esto con Treaps ordinarios si las prioridades son aleatorias.

La afirmación precisa que haré es que para realizar una fusión de este tipo en dos treaps de igual tamaño con prioridades aleatorias, se debe actualizar Θ(logn) punteros en expectativa.

Aquí hay un boceto de prueba aproximada:

Considere la cantidad de punteros que tiene que cambiar con la expectativa de realizar la operación. Es más fácil probar un límite si no insertamos t r, sino que simplemente fusionamos T 1 y T 2 . Considere la columna derecha S 1 de T 1 y la columna izquierda S 2 de T 2 . Colorea los elementos de S 1 en rojo y los de S 2 en azul. Orden S 1S 2Θ(logn)trT1T2S1T1S2T2S1S2S1S2 por prioridad. Tenemos que cambiar un puntero cada vez que cambia el color en esta secuencia. Como ambas espinas tienen tamaño con alta probabilidad, y las prioridades son aleatorias, no es demasiado difícil ver que el número de cambios de color en la secuencia también es Θ ( log n ) . Por lo tanto, debemos actualizar lospunteros Θ ( log n ) para la fusión (sin agregar t r ).Θ(logn)Θ(logn)Θ(logn)tr

Ahora, agregar mientras se hace la fusión realmente no ayuda mucho. El número de cambios de puntero en ese caso puede ser limitado de la siguiente manera: Ordene S 1S 2{ t r } por prioridad. Eliminar todo menos que t r en la secuencia. Entonces # de cambios de color en la secuencia resultante es nuestro límite inferior. Dado que t r tiene prioridad aleatoria, la altura esperada del subárbol enraizado en el treap final es O ( 1 ) , por lo que solo tiene nodos O ( 1 ) de StrS1S2{tr}trtrO(1)O(1) con menor prioridad de lo esperado, por lo que solo perdimosS1S2cambios de puntero 1 ) en nuestro límite inferior al agregar t rO(1)tr .

Ahora, dicho esto, probablemente haya una forma de obtener una estructura de datos "similar a un treap" que permita fusiones de tiempo esperadas constantes.


fuente
Sí, estoy buscando una estructura de datos "tipo treap". Aunque mencioné tanto en los comentarios y mi respuesta difunta, no lo puse en el título o pregunta.
jbapple
Gracias por tu respuesta. He cambiado el título y el texto de la pregunta para que sea menos ambiguo.
jbapple
1

Actualización: consulte a continuación una actualización sobre la incorrección de esta operación de unión

Aquí hay un bosquejo muy aproximado de una posible solución:

Creo que puedo tener una solución a este problema usando un tipo de árbol B + balanceado al azar. Como los treaps, estos árboles tienen una representación única. A diferencia de los treaps, almacenan algunas claves varias veces. Podría ser posible arreglar eso usando un truco de los "Árboles de búsqueda sesgados" de Bent et al. Para almacenar cada clave solo en el nivel más alto (es decir, el más cercano a la raíz) en el que aparece)

Se crea un árbol para un conjunto ordenado de valores únicos asociando primero cada valor con un flujo de bits, de forma similar a la forma en que cada valor en un treap se asocia con una prioridad. Cada nodo en el árbol contiene una clave y un flujo de bits. Los nodos no hoja contienen, además, un número natural que indica la altura del árbol enraizado en ese nodo. Los nodos internos pueden tener cualquier número de hijos distinto de cero. Al igual que los árboles B +, cada ruta que no se cruza entre sí desde la raíz a una hoja tiene la misma longitud.

Cada nodo interno contiene (como en los árboles B +) la clave más grande k de sus hojas descendientes. Cada uno también contiene un número natural i que indica la altura del árbol enraizado en v , y el flujo de bits asociados con k desde el i + bit en adelante. Si cada clave en el árbol enraizada en v tiene el mismo primer bit en su flujo de bits, cada hijo de v es una hoja e i es 1 . De lo contrario, los hijos de v son nodos internos, todos los cuales tienen el mismo ivkivki+1vvi1vi ésimo bit en el flujo de bits asociado con su llave.

Para hacer un árbol a partir de una lista ordenada de claves con flujos de bits asociados, primero recopile las claves en grupos contiguos basados ​​en el primer bit de sus flujos. Para cada uno de estos grupos, cree un padre con la clave y la secuencia de bits de la clave más grande del grupo, pero evitando el primer bit de la secuencia. Ahora haga el mismo procedimiento de agrupación en los nuevos padres para crear abuelos. Continúe hasta que solo quede un nodo; Esta es la raíz del árbol.

La siguiente lista de claves y (comienzo de) secuencias de bits está representada por el árbol debajo de ella. En los prefijos de flujo de bits, un '.' significa cualquier parte. Es decir, cualquier flujo de bits para la clave A con un 0 en primer lugar produce el mismo árbol que cualquier otro, suponiendo que ningún flujo de bits de otra clave sea diferente.

A 0...
B 00..
C 10..
D 0...
E 0011
F 1...
G 110.
H 0001


        ____H____
       /         \
      E           H
      |          / \
    __E__       G   H
   /  |  \      |   |
  B   C   E     G   H
 / \  |  / \   / \  |
A   B C D   E F   G H

Cada hijo de un nodo interno particular tiene el mismo bit en primer lugar de su flujo de bits. Esto se llama el "color" del padre: 0 es rojo, 1 es verde. El niño tiene un "sabor" dependiendo del primer bit de su flujo de bits: 0 es cereza, 1 es menta. Las hojas tienen sabores, pero no tienen color. Por definición, un nodo cherry no puede tener un padre verde, y un nodo mint no puede tener un padre rojo.

n21n (n1i1)(n+1)/2norte2 , esto es34 4norte, entonces la altura esperada del árbol es O(lgnorte).

Para unir dos árboles de igual altura, primero verifique si sus raíces son del mismo color. Si es así, separe de la raíz izquierda a su hijo más a la derecha y de la raíz derecha a su hijo más a la izquierda, luego una de manera recursiva estos dos árboles. El resultado será un árbol de la misma altura o uno más alto ya que los árboles tienen el mismo sabor (ver más abajo). Si el resultado de unir recursivamente los dos árboles tiene la misma altura que los dos hijos cortados, conviértalo en el hijo del medio de una raíz con los hijos restantes de la raíz izquierda antes y los hijos restantes de la raíz derecha después. Si es más alto en 1, haga que sus hijos sean los hijos intermedios de una raíz con los hijos restantes de la raíz izquierda antes y los hijos restantes de la raíz derecha después. Si las raíces tienen colores diferentes, verifique si tienen el mismo sabor. Si lo hacen, darles un nuevo padre con la clave y la secuencia de bits de la raíz derecha, eludiendo su primer bit. Si no lo hacen, dele a cada raíz un nuevo padre con la clave y la secuencia de bits de la raíz anterior (eluyendo cada primer bit), luego unir recursivamente esos árboles.

Hay dos llamadas recursivas en este algoritmo. La primera es cuando las raíces tienen el mismo color, la segunda es cuando las raíces tienen diferentes colores y sabores diferentes. Las raíces tienen el mismo color con probabilidad.1/ /2. La llamada recursiva en este caso siempre ve raíces con el mismo sabor, por lo que el segundo tipo de recursión nunca ocurre después del primero. Sin embargo, lo primero puede ocurrir repetidamente, pero cada vez con probabilidad1/ /2, por lo que el tiempo de ejecución esperado sigue siendo O(1). La segunda llamada recursiva ocurre con probabilidad1/ /4 4, y las llamadas recursivas posteriores siempre están en árboles con diferentes colores, por lo que se aplica el mismo análisis.

Para unir dos árboles de altura desigual, primero trace la columna izquierda del árbol derecho, suponiendo que el árbol derecho sea más alto. (El otro caso es simétrico). Cuando se alcanzan dos árboles de igual altura, realice la operación de unión para dos árboles de igual altura, modificados de la siguiente manera: si el resultado tiene la misma altura, reemplace el árbol que era un niño con el resultado de la unión. Si el resultado es más alto, únase al padre del árbol a la derecha de la raíz del otro árbol, después de que uno lo haya hecho más alto agregando un padre para la raíz. El árbol tendrá la misma altura con probabilidad1/ /2, entonces esto termina en O(1) esperado.

Actualización: Gracias a QuickCheck, descubrí que el método de unión anterior no produce los mismos árboles que los árboles representados de forma única. El problema es que las elecciones de los padres cerca de las hojas pueden cambiar según los hermanos disponibles. Para arreglar esos cambios, unirse tendría que atravesar todo el camino hasta las hojas, lo cual no esO(1). Aquí está el ejemplo de QuickCheck encontrado:

a 01110
b 110..
c 10...
d 00000

El árbol hecho por [a,b]tiene altura 2, el árbol hecho por [c,d]tiene altura 2, y el árbol hecho por joinEqual (tree [a,b]) (tree [c,d])tiene altura 3. Sin embargo, el árbol hecho por [a,b,c,d]tiene altura 5.

Aquí está el código que usé para encontrar este error .

jbapple
fuente