¿Mantener un orden eficiente en el que puede insertar elementos "entre" otros dos elementos en el orden?

Imagine que tengo un pedido en un grupo de elementos como este:

Donde una flecha $X \leftarrow Y$ medio $X < Y$. También es transitivo:$\left(X < Y\right) \wedge \left(Y < Z\right) \implies \left(X < Z\right)$.

Para responder eficientemente consultas como $A \stackrel {?}{<} D$, se requiere algún tipo de etiquetado o estructura de datos. Por ejemplo, podría numerar los nodos de izquierda a derecha y, por lo tanto, simplemente puede hacer una comparación de enteros para responder la consulta:$A \stackrel {?}{<} D \implies 1 < 4 \implies T$. Se vería algo así:

Donde el número es el pedido, y la letra es solo un nombre.

Pero, ¿qué pasaría si necesitara insertar elementos "entre" otros dos elementos en el orden, así:

¿Cómo puede mantener tal orden? Con una numeración simple, te encuentras con el problema de que no hay enteros "intermedios"$2,3$ usar.

Esto se conoce como el problema de "mantenimiento de pedidos" . Hay una solución relativamente simple usando$O(1)$tiempo amortizado para consultas e inserciones. Ahora, por "relativamente simple", quiero decir que tienes que entender algunos bloques de construcción, pero que una vez que los consigas, el resto no es difícil de ver.

http://courses.csail.mit.edu/6.851/spring12/lectures/L08.html

La idea básica es una estructura de datos de dos niveles. El nivel superior es como la solución de árbol AVL de Realz Slaw, pero

• Los nodos se etiquetan directamente con cadenas de bits de longitud $O(\lg n)$con un orden que coincida con su orden en el árbol. Por lo tanto, la comparación lleva tiempo constante

• Se utiliza un árbol con menos rotaciones que un árbol AVL, como un árbol chivo expiatorio o un árbol con equilibrio de peso, por lo que los reencauchados ocurren con menos frecuencia.

El nivel inferior son las hojas del árbol. Ese nivel usa la misma longitud de etiquetas,$O(\lg n)$, pero solo tiene $O(\lg n)$elementos en cada hoja en una lista simple vinculada. Esto le da suficientes bits adicionales para volver a etiquetar agresivamente.

Las hojas se vuelven demasiado grandes o demasiado pequeñas cada $O(\lg n)$ inserta, induciendo un cambio en el nivel superior, que toma $O(\lg n)$ tiempo amortizado$\Omega(n)$peor de los casos). Amortizado, esto es solo$O(1)$.

Existen estructuras mucho más complejas para realizar actualizaciones en $O(1)$ peor de los casos.

En lugar de una simple numeración, puede distribuir los números en un rango grande (tamaño constante), como los mínimos y máximos de un entero de CPU. Luego puede seguir poniendo números "en el medio" promediando los dos números circundantes. Si los números se llenan demasiado (por ejemplo, termina con dos enteros adyacentes y no hay ningún número intermedio), puede hacer una nueva numeración de todo el pedido, redistribuyendo los números de manera uniforme en todo el rango.

Por supuesto, puede encontrarse con la limitación de que se utilizan todos los números dentro del rango de la constante grande. En primer lugar, esto no suele ser un problema, ya que el tamaño entero en una máquina es lo suficientemente grande como para que si tuviera más elementos, probablemente no encajaría en la memoria de todos modos. Pero si es un problema, simplemente puede renumerarlos con un rango entero más grande.

Si el orden de entrada no es patológico, este método podría amortizar las renumeraciones.

Respondiendo consultas

Una simple comparación de enteros puede responder la consulta $\left(X \stackrel{?}{<}Y\right)$.

El tiempo de consulta sería muy rápido ( $\mathcal{O}\left(1\right)$) si usa enteros de máquina, ya que es una comparación de enteros simple. Usar un rango mayor requeriría enteros más grandes, y la comparación tomaría$\mathcal{O}\left(\log{|integer|}\right)$.

Inserción

En primer lugar, mantendría la lista vinculada de la orden, demostrada en la pregunta. La inserción aquí, dados los nodos para colocar el nuevo elemento en el medio, sería$\mathcal{O}\left(1\right)$.

Etiquetar el nuevo elemento generalmente sería rápido $\mathcal{O}\left(1\right)$porque calcularía el nuevo numerador fácilmente promediando los números circundantes. Ocasionalmente puede quedarse sin números "en el medio", lo que desencadenaría el$\mathcal{O}\left(n\right)$ procedimiento de renumeración de tiempo.

Evitar renumerar

Puede usar flotantes en lugar de enteros, por lo que cuando obtiene dos enteros "adyacentes", se pueden promediar. Por lo tanto, puede evitar renumerar cuando se enfrente con dos flotantes enteros: simplemente divídalos por la mitad. Sin embargo, con el tiempo el tipo de coma flotante se quedará sin precisión, y no se podrán promediar dos flotantes "adacent" (el promedio de los números circundantes probablemente será igual a uno de los números circundantes).

De manera similar, puede usar un entero de "lugar decimal", donde mantiene dos enteros para un elemento; uno para el número y uno para el decimal. De esta manera, puede evitar volver a numerar. Sin embargo, el entero decimal eventualmente se desbordará.

El uso de una lista de enteros o bits para cada etiqueta puede evitar por completo la renumeración; esto es básicamente equivalente a usar números decimales con longitud ilimitada. La comparación se haría lexicográficamente, y los tiempos de comparación aumentarán a lo largo de las listas involucradas. Sin embargo, esto puede desequilibrar el etiquetado; algunas etiquetas pueden requerir solo un número entero (sin decimal), otras pueden tener una lista de longitud larga (decimales largos). Esto es un problema, y ​​la renumeración también puede ayudar aquí, al redistribuir la numeración (aquí listas de números) de manera uniforme sobre un rango elegido (rango aquí posiblemente significa la longitud de las listas) para que después de tal renumeración, las listas tengan la misma longitud .

Este método se usa realmente en este algoritmo ( implementación , estructura de datos relevante ); En el curso del algoritmo, se debe mantener un orden arbitrario y el autor utiliza enteros y renumeración para lograrlo.

Intentar apegarse a los números hace que su espacio clave sea algo limitado. En su lugar, se podrían utilizar cadenas de longitud variable, utilizando la lógica de comparación "a" <"ab" <"b". Aún quedan dos problemas por resolver A. Las claves podrían llegar a ser arbitrariamente largas B. La comparación de las claves largas podría ser costosa

Puede mantener un árbol AVL sin clave o similar.

Funcionaría de la siguiente manera: el árbol mantiene un orden en los nodos tal como lo hace normalmente un árbol AVL, pero en lugar de que la clave determine dónde debe estar el nodo "," no hay claves, y debe insertar explícitamente los nodos "después "otro nodo (o en otras palabras" entre "dos nodos), donde" después "significa que viene después de él en el recorrido en orden del árbol. El árbol mantendrá así el orden para usted de forma natural, y también se equilibraría, debido a las rotaciones incorporadas del AVL. Esto mantendrá todo distribuido uniformemente de forma automática.

Inserción

Además de la inserción regular en la lista, como se demuestra en la pregunta, mantendría un árbol AVL separado. La inserción en la lista misma es$\mathcal{O}\left(1\right)$, ya que tiene los nodos "antes" y "después".

El tiempo de inserción en el árbol es $\mathcal{O}\left(\log {n}\right)$, lo mismo que la inserción en un árbol AVL. La inserción implica tener una referencia al nodo que desea insertar después, y simplemente inserte el nuevo nodo a la izquierda del nodo más a la izquierda del hijo derecho; esta ubicación es "siguiente" en el orden del árbol (es la siguiente en el recorrido en orden). Luego haga las rotaciones AVL típicas para reequilibrar el árbol. Puede hacer una operación similar para "insertar antes"; Esto es útil cuando necesita insertar algo al comienzo de la lista, y no hay un nodo "antes".

Respondiendo consultas

Para responder consultas de $\left(X \stackrel{?}{<}Y\right)$, simplemente encuentras a todos los antepasados ​​de $X$ y $Y$en el árbol, y analiza la ubicación de dónde divergen los antepasados ​​en el árbol; el que diverge a la "izquierda" es el menor de los dos.

Este procedimiento lleva $\mathcal{O}\left(\log{n}\right)$tiempo escalando el árbol hasta la raíz y obteniendo las listas de antepasados. Si bien es cierto que esto parece más lento que la comparación de enteros, la verdad es que es lo mismo; solo esa comparación de enteros en una CPU está limitada por una gran constante para que sea$\mathcal{O}\left(1\right)$; si desborda esta constante, debe mantener varios enteros ($\mathcal{O}\left(\log{n}\right)$ enteros en realidad) y hacer lo mismo $\mathcal{O}\left(\log{n}\right)$comparaciones Alternativamente, puede "vincular" la altura del árbol en una cantidad constante y "engañar" de la misma manera que la máquina lo hace con enteros: ahora aparecerán consultas$\mathcal{O}\left(1\right)$.

Demostración de la operación de inserción

Para demostrarlo, puede insertar algunos elementos con su orden de la lista en la pregunta:

Paso 1

Empezar con $D$

Lista:

Árbol:

Paso 2

Insertar $C$, $\emptyset < C < D$.

Lista:

Árbol:

Nota, pones explícitamente $C$ "antes de" $D$, no porque la letra C esté antes de D, sino porque $C < D$ en la lista.

Paso 3

Insertar $A$, $\emptyset < A < C$.

Lista:

Árbol:

Rotación AVL:

Paso 4

Insertar $B$, $A < B < C$.

Lista:

Árbol:

No hay rotaciones necesarias.

Paso 5

Insertar $E$, $D < E < \emptyset$

Lista:

Árbol:

Paso 6

Insertar $F$, $B < F < C$

Simplemente lo explicamos "después" $B$ en el árbol, en este caso simplemente uniéndolo a $B$tiene razón; así$F$ ahora es justo después $B$ en el recorrido en orden del árbol.

Lista:

Árbol:

Rotación AVL:

Demostración de la operación de comparación

$A \stackrel{?}{<} F$

ancestors(A) = [C,B]
ancestors(F) = [C,B]
last_common_ancestor = B
B.left = A
B.right = F
... A < F #left is less than right

$D \stackrel{?}{<} F$

ancestors(D) = [C]
ancestors(F) = [C,B]
last_common_ancestor = C
C.left = D
C.right = B #next ancestor for F is to the right
... D < F #left is less than right

$B \stackrel{?}{<} A$

ancestors(B) = [C]
ancestors(A) = [B,C]
last_common_ancestor = B
B.left = A
... A < B #left is always less than parent

Fuentes gráficas

• gist.github.com/realazthat/9299877a83cba4720aec