Cómo lo consigue: el árbol de dos lados y la regla de colocación

La definición de la lección anterior no dice cómo construir nada: describe qué orden es aceptable, no cómo obtenerlo. El paso siguiente es el mecanismo, y aquí conviene resistir la tentación de leerlo como notación. La idea entera de Fugue cabe en una frase geométrica: si consigues que la ráfaga de cada usuario ocupe un subárbol propio, y recorres el árbol de manera que cada subárbol se emita entero antes de pasar al siguiente, entonces la no intercalación deja de ser algo que hay que vigilar y pasa a ser una consecuencia del recorrido. Todo lo demás —la elección de padre, el lado por el que se cuelga, el desempate entre hermanos— existe únicamente para garantizar esa condición geométrica. Esta lección construye la estructura con un ejemplo trabajado de una lista de la compra editada por dos personas sin conexión, una escribiendo hacia delante y otra anteponiendo, y muestra en el mismo ejemplo por qué los algoritmos anteriores, que solo disponían de un lado, no podían conseguirlo.

Un árbol de dos lados y un recorrido en orden

El estado de cada réplica es un árbol. Cada nodo distinto de la raíz lleva un identificador único y un valor —un carácter, un elemento de la lista de tareas, una fila—, y además lleva una marca que dice si es hijo izquierdo o hijo derecho de su padre. Esa marca es la pieza que no existía en las estructuras anteriores. El árbol no es binario: un mismo padre puede tener varios hijos izquierdos y varios hijos derechos a la vez, y de hecho eso es lo normal en cuanto hay concurrencia. Tampoco está equilibrado, ni hay ningún intento de equilibrarlo, porque el equilibrio no aporta nada a la semántica y el rendimiento se resuelve por otra vía que ocupa la lección siguiente.

El orden de la lista se obtiene con un recorrido en profundidad y en orden simétrico: para cada nodo se recorren primero sus hijos izquierdos, después se emite el valor del propio nodo y por último se recorren sus hijos derechos. Los hermanos del mismo lado —mismos padre y mismo lado— se recorren en el orden lexicográfico de sus identificadores; el artículo subraya que la construcción concreta de los identificadores y su orden es irrelevante mientras sea determinista, porque solo se usa como desempate.

Recorrido en orden simetrico de un nodo N:

  1  recorrer los hijos izquierdos de N, en orden de hermanos
  2  emitir el valor de N
  3  recorrer los hijos derechos de N, en orden de hermanos

Propiedad clave que se deduce de ahi:

  el subarbol enraizado en cualquier nodo se emite como un
  bloque contiguo de la lista, sin nada intercalado en medio.

Esa contiguidad es literalmente la definicion de no intercalar.
Todo el algoritmo consiste en conseguir que la rafaga de cada
autor caiga dentro de un subarbol propio.

La regla de colocación cabe en dos líneas

Para insertar un valor en la posición i, la réplica calcula sus dos orígenes: el izquierdo es el elemento que está en la posición anterior, o la raíz si se inserta al principio; el derecho es el nodo que sigue al origen izquierdo en el recorrido contando también las lápidas, es decir los elementos ya borrados. A partir de ahí hay exactamente dos casos.

// Regla de colocacion de Fugue. Dos casos, ninguno mas.
function colocar(arbol, indice, valor, id) {
  const izq = arbol.nodoEnIndice(indice - 1) ?? arbol.raiz;
  const der = arbol.siguienteEnRecorridoConLapidas(izq);

  if (!arbol.tieneHijosDerechos(izq)) {
    // caso 1: nadie ha colgado nada a la derecha de izq todavia
    return { id, valor, padre: izq.id, lado: "derecha" };
  }
  // caso 2: izq ya tiene descendencia derecha, asi que colgamos
  // por la izquierda del que venia justo despues
  return { id, valor, padre: der.id, lado: "izquierda" };
}

La demostración de que esto preserva la posición local es breve y merece seguirse, porque explica por qué no hace falta un tercer caso. Los dos orígenes son, por construcción, consecutivos en el recorrido. Si el origen izquierdo no tiene hijos derechos, colgar el nodo nuevo como su primer hijo derecho lo convierte en su sucesor inmediato en el recorrido, que es justo lo que se quiere. Si el origen izquierdo sí tiene hijos derechos, entonces el origen derecho tiene que ser descendiente suyo, y además no puede tener hijos izquierdos —si los tuviera, los dos orígenes no serían consecutivos—, de modo que colgar el nodo nuevo como primer hijo izquierdo del origen derecho lo coloca exactamente entre ambos. Con esos dos casos, el artículo demuestra que Fugue satisface la especificación fuerte de listas.

La réplica difunde entonces, por un protocolo de difusión causal, tres datos: el nodo nuevo, su padre y su lado. Nada más. No hay transformación de operaciones, no hay negociación y no hay servidor que secuencie: cualquier réplica que reciba esos tres datos puede insertar el nodo en su propio árbol y obtendrá el mismo orden que todas las demás.

El ejemplo trabajado: dos manos, dos direcciones

Partimos de una lista de la compra que contiene un único elemento, queso, que en el árbol es un hijo derecho de la raíz. Dos personas trabajan sin conexión sobre ella. La primera escribe hacia delante; la segunda antepone. Seguimos las dos ráfagas paso a paso.

RAFAGA HACIA DELANTE
Ana escribe pan detras de queso, letra a letra.

  insertar p tras queso   queso no tiene hijos derechos  -> p hijo derecho de queso
  insertar a tras p       p no tiene hijos derechos      -> a hijo derecho de p
  insertar n tras a       a no tiene hijos derechos      -> n hijo derecho de a

  resultado: una cadena que baja siempre por la derecha
  queso -> p -> a -> n

RAFAGA HACIA ATRAS
Beto antepone tres entradas al principio, sin haber visto nada de Ana.

  insertar manzana al principio   origen izq = raiz, origen der = queso
                                  la raiz ya tiene hijo derecho -> caso 2
                                  -> manzana hijo izquierdo de queso
  insertar pera al principio      origen der = manzana -> caso 2
                                  -> pera hijo izquierdo de manzana
  insertar FRUTA al principio     origen der = pera -> caso 2
                                  -> FRUTA hijo izquierdo de pera

  resultado: una cadena que baja siempre por la izquierda
  queso <- manzana <- pera <- FRUTA

Lo importante ya ha ocurrido y conviene nombrarlo: una ráfaga hacia delante produce una cadena por el lado derecho y una ráfaga hacia atrás produce una cadena por el lado izquierdo. En ambos casos la ráfaga entera es un subárbol, y un subárbol se emite contiguo. La estructura de dos lados existe exactamente para que las dos direcciones de escritura tengan cada una su propia forma de encadenarse.

Añadamos ahora la concurrencia. Supongamos que una tercera persona, también sin conexión, antepone su propio bloque de panadería: pan tostado, luego bollo, luego el encabezado PANADERIA. Por la misma regla, su bloque forma otra cadena izquierda colgada de queso. Al fusionar, queso acaba con dos hijos izquierdos —manzana y pan tostado, las cabezas de cada cadena— y con un hijo derecho, la p de Ana.

flowchart TD
R[raiz] -->|derecha| Q[queso]
Q -->|izquierda| M[manzana de Beto]
Q -->|izquierda| PT[pan tostado de Carla]
Q -->|derecha| P1[p de Ana]
M -->|izquierda| PE[pera de Beto]
PE -->|izquierda| F[FRUTA de Beto]
PT -->|izquierda| BO[bollo de Carla]
BO -->|izquierda| PA[PANADERIA de Carla]
P1 -->|derecha| A1[a de Ana]
A1 -->|derecha| N1[n de Ana]
style F fill:#a6e3a1,color:#11111b
style PA fill:#89b4fa,color:#11111b
style N1 fill:#f9e2af,color:#11111b

El recorrido produce entonces, sin que nadie tenga que comprobar nada: primero los hijos izquierdos de queso en orden de hermanos, y cada uno emite su subárbol completo, de modo que salen los tres elementos de Beto seguidos y después los tres de Carla seguidos, o al revés según el desempate; luego queso; y luego la cadena derecha de Ana, entera. Ninguna de las tres ráfagas se mezcla con las otras, y no porque el algoritmo lo haya impedido en el momento de fusionar, sino porque la mezcla nunca fue representable: las tres cayeron en subárboles distintos desde el instante mismo de la inserción local.

Por qué basta con un árbol

Recapitulando el mecanismo completo con la mirada puesta en la propiedad de la lección anterior, se ve que la correspondencia es casi literal y que ahí está el mérito del diseño.

Queda un detalle que conviene no pasar por alto porque suele generar dudas al implementar: el origen derecho se calcula sobre el recorrido que incluye las lápidas. Podría parecer una decisión de conveniencia y es en realidad lo que permite ignorar por completo las eliminaciones en todo el análisis de intercalación. Si el origen derecho se tomara sobre la lista visible, borrar un elemento cambiaría los orígenes derechos de sus vecinos y las propiedades demostradas dejarían de valer al primer borrado. Con lápidas, el origen derecho de un elemento queda fijado para siempre en el instante de su inserción, que es la clase de invariante sobre la que se pueden construir demostraciones.