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

Question

Imagina que tengo un orden en un montón de elementos como este:

Donde una flecha $X \leftarrow Y$ significa $X < Y$.También es transitivo:$\left(X < Y ight) \cuña \left(Y < Z ight) \implica \left(X < Z ight)$.

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

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

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

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

Answer 1

Esto se conoce como el Problema de "mantenimiento de pedidos". Hay una solución relativamente simple usando el tiempo $ O (1) $ amortizado para consultas y insertos. Ahora, por "relativamente simple", quiero decir que tienes que entender algunos bloques de construcción, pero que una vez que los obtienes, 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 por ensalada realz, pero

• Los nodos se etiquetan directamente con cadenas de bits de longitud $ o ( lg n) $ con un pedido que coincide con su orden en el árbol. La comparación, por lo tanto, lleva tiempo constante

• Se usa un árbol con menos rotaciones que un árbol AVL, como un árbol de chivo expiatorio o un árbol equilibrado con peso, por lo que las relabiones ocurren con menos frecuencia.

El nivel inferior son las hojas del árbol. Ese nivel utiliza la misma longitud de las etiquetas, $ o ( lg n) $, pero posee solo $ o ( lg n) $ elementos en cada hoja en una lista simple vinculada. Esto le ofrece suficientes bits adicionales para volver a alquilar agresivamente.

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

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

Answer 2

En lugar de una numeración simple, puede distribuir los números en un rango grande (de tamaño constante), como el mínimo y máximo de un entero de CPU.Luego puedes seguir poniendo números "intermedios" promediando los dos números circundantes.Si los números se abarrotan demasiado (por ejemplo, termina con dos números enteros adyacentes y no hay ningún número intermedio), puede volver a numerar todo el orden una sola vez, redistribuyendo los números uniformemente en todo el rango.

Por supuesto, puede encontrarse con la limitación de que se utilicen 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 del número 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 hay un problema, simplemente puede volver a numerarlos con un rango de números enteros mayor.

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 a la consulta $\left(X \stackrel{?}{<}Y ight)$.

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

Inserción

En primer lugar, mantendría la lista vinculada del pedido, como se muestra en la pregunta.La inserción aquí, dados los nodos para colocar el nuevo elemento entre ellos, sería $\mathcal{O}\left(1 ight)$.

Etiquetar el nuevo elemento normalmente sería rápido $\mathcal{O}\left(1 ight)$ porque calcularías el nuevo número fácilmente promediando los números circundantes.Ocasionalmente, es posible que se quede sin números "intermedios", lo que activaría el procedimiento de renumeración de tiempo $\mathcal{O}\left(n ight)$.

Evitar la renumeración

Puedes usar flotantes en lugar de números enteros, de modo que cuando obtengas dos números enteros "adyacentes", poder ser promediado.Por lo tanto, puede evitar volver a numerar cuando se enfrenta a dos números flotantes enteros:simplemente divídelos por la mitad.Sin embargo, eventualmente el tipo de coma flotante perderá precisión y no se podrán promediar dos flotadores "adacentes" (el promedio de los números circundantes probablemente será igual a uno de los números circundantes).

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

El uso de una lista de números 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 según la longitud de las listas involucradas.Sin embargo, esto puede desequilibrar el etiquetado;algunas etiquetas pueden requerir solo un número entero (sin decimales), otras pueden tener una lista de longitud larga (decimales largos).Esto es un problema, y ​​la renumeración también puede ayudar en este caso, redistribuyendo la numeración (en este caso, listas de números) uniformemente en un rango elegido (rango aquí posiblemente signifique longitud de las listas) de modo que después de dicha renumeración, todas las listas tengan la misma longitud. .

---

Este método en realidad se utiliza en este algoritmo (implementación,estructura de datos relevante);en el transcurso del algoritmo, se debe mantener un orden arbitrario y el autor utiliza números enteros y renumeraciones para lograrlo.

---

Tratar de ceñirse a los números hace que el 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 teclas podrían volverse arbitrariamente largas B.La comparación de claves largas podría resultar costosa

Answer 3

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" de otro nodo (o en en otras palabras, "entre" dos nodos), donde "después" significa que viene después en el recorrido ordenado del árbol.De este modo, el árbol mantendrá el orden de forma natural y también se equilibrará gracias a las rotaciones integradas 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 en sí es $\mathcal{O}\left(1 ight)$, ya que tiene los nodos "antes" y "después".

El tiempo de inserción en el árbol es $\mathcal{O}\left(\log {n} ight)$, 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 inserta el nuevo nodo a la izquierda del nodo más a la izquierda del hijo derecho;esta ubicación es la "siguiente" en el orden del árbol (es la siguiente en el recorrido en orden).Luego haz las rotaciones típicas de AVL para reequilibrar el árbol.Puedes hacer una operación similar para "insertar antes";Esto es útil cuando necesita insertar algo al principio de la lista y no hay ningún nodo "antes".

Respondiendo consultas

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

Este procedimiento toma $\mathcal{O}\left(\log{n} ight)$ tiempo para subir el árbol hasta la raíz y obtener las listas de ancestros.Si bien es cierto que esto parece más lento que la comparación de números enteros, lo cierto es que es lo mismo;solo que la comparación de enteros en una CPU está limitada por una constante grande para que sea $\mathcal{O}\left(1 ight)$;Si desborda esta constante, debe mantener varios enteros ($\mathcal{O}\left(\log{n} ight)$ enteros en realidad) y hacer lo mismo $\mathcal{O}\left(\log{ n} ight)$ comparaciones.Alternativamente, puede "limitar" la altura del árbol en una cantidad constante y "hacer trampa" de la misma manera que lo hace la máquina con los números enteros:ahora las consultas aparecerán $\mathcal{O}\left(1 ight)$.

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

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

Paso 1

Empieza con $D$

Lista:

Árbol:

Paso 2

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

Lista:

Árbol:

Tenga en cuenta que usted pone explícitamente $C$ "antes" de $D$, no porque la letra C esté antes de D, sino porque $C < D$ en la lista.

Paso 3

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

Lista:

Árbol:

Rotación AVL:

Etapa 4

Inserte $B$, $A < B < C$.

Lista:

Árbol:

No son necesarias rotaciones.

Paso 5

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

Lista:

Árbol:

Paso 6

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

Simplemente lo colocamos justo "después" de $B$ en el árbol, en este caso simplemente adjuntándolo a la derecha de $B$;por lo tanto, $F$ está ahora justo después de $B$ en el recorrido en orden del árbol.

Lista:

Árbol:

Rotación AVL:

Demostración de 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 de gráficos

• gist.github.com/realazthat/9299877a83cba4720aec