Por qué el árbol merece capítulo propio

Los niveles anteriores fueron subiendo por una escalera de tipos: el registro, el contador, el conjunto, el mapa, la secuencia. Cada peldaño era más difícil que el anterior, pero todos compartían una propiedad tranquilizadora que quizá no llegaste a nombrar: su corrección era local. Un conjunto está bien formado sea cual sea el contenido; un mapa está bien formado sea cual sea el valor de cada clave; una secuencia convergente está bien formada aunque el orden resultante no le guste a nadie. El árbol rompe esa racha, y la rompe de una manera que ninguna de las técnicas acumuladas hasta ahora arregla. Un árbol no es un contenedor con datos dentro: es un conjunto de aristas sujeto a una condición que no se puede verificar mirando ninguna arista por separado. Esta lección instala esa distinción, muestra cuántas cosas del día a día son árboles sin declararse como tales y deja preparado el escenario exacto donde todo se rompe.

Un árbol donde nadie dijo que hubiera uno

La palabra árbol aparece poco en las especificaciones de producto y muchísimo en el código que las implementa. Un sistema de carpetas es un árbol. Un esquema de documento con secciones y subsecciones es un árbol. Una lista con viñetas que admite sangrado es un árbol, aunque la interfaz la dibuje como una columna de líneas. El panel de capas de una herramienta de diseño es un árbol. Los hilos de comentarios, los marcadores del navegador, las categorías de un catálogo, el propio DOM: árboles todos.

Lo que tienen en común no es la forma del dibujo sino una capacidad concreta que se le concede al usuario: la de reorganizar. Una estructura jerárquica de solo lectura es un detalle de presentación y no plantea ningún problema interesante. En el momento en que arrastras una carpeta dentro de otra, o sangras un punto de la lista para que dependa del anterior, la aplicación deja de mostrarte una jerarquía y empieza a dejarte editarla. Y editar una jerarquía significa, casi siempre, mover.

Hay un criterio rápido para saber si tienes un árbol editable entre manos aunque el código no lo llame así: busca en tu interfaz cualquier gesto que cambie la pertenencia de un elemento sin cambiar su contenido. Arrastrar y soltar es el más obvio, pero no el único. La tecla de tabulación en un editor de esquemas, el botón de agrupar en una herramienta de diseño, el desplegable de mover a en un gestor de tareas, la reasignación de un ticket a otro proyecto: todos son la misma operación con distinta piel. Si tu producto tiene alguno de esos gestos y sincroniza entre dispositivos, este nivel te concierne aunque la palabra árbol no aparezca en tu esquema.

Conviene detenerse en la asimetría económica de este asunto. Mover es una operación barata para el usuario —un gesto de arrastre, una pulsación de tabulador— y desproporcionadamente cara para el sistema, porque cambia una relación estructural en vez de un valor. Casi todas las decisiones de diseño equivocadas en esta materia nacen de esa asimetría: la interfaz sugiere que mover es tan inocuo como escribir un carácter y la implementación hereda esa creencia.

La representación mínima: un mapa de hijo a padre

Hay dos maneras evidentes de guardar un árbol y solo una sobrevive al contacto con la replicación. La primera es dar a cada nodo la lista de sus hijos. La segunda es dar a cada nodo la identidad de su padre. Parecen equivalentes porque describen el mismo grafo, pero se comportan de forma opuesta cuando dos réplicas escriben sin verse.

Con listas de hijos, cada arista está representada dos veces si además guardas el padre, y una sola vez pero en un sitio compartido si no lo guardas. Mover un nodo exige entonces dos escrituras: quitarlo de la lista del padre viejo y añadirlo a la del padre nuevo. Dos escrituras que pueden fusionarse por separado, y ahí nace la patología más tonta de todas: el nodo aparece en las dos listas, o en ninguna. Ninguna réplica escribió eso; lo fabricó la fusión al aceptar una mitad de cada operación.

Con un mapa de hijo a padre, la arista vive en una sola clave y mover es una única escritura sobre esa clave. La consecuencia es inmediata y merece enunciarse como lo que es, un regalo: la invariante de un padre como máximo por nodo deja de ser algo que haya que comprobar y pasa a ser una propiedad del tipo, porque un mapa no puede tener dos valores para la misma clave. Toda la maquinaria de resolución que ya conoces —el registro de último escritor, el desempate por identidad de réplica— se aplica sin cambios a cada clave.

// Un arbol es un mapa: hijo -> padre. La raiz no tiene entrada.
const padre = new Map([
  ["notas.md",   "Proyecto"],
  ["Proyecto",   "Documentos"],
  ["Documentos", "raiz"],
  ["Imagenes",   "raiz"],
]);

// Mover es una sola escritura sobre una sola clave.
function mover(hijo, nuevoPadre) {
  padre.set(hijo, nuevoPadre);
}

Un tercer punto a favor del mapa, menos comentado y que se agradece mucho en la práctica, es que hace explícita la identidad del nodo. Las claves son identificadores estables, no posiciones ni rutas, de modo que un nodo sigue siendo el mismo objeto pase lo que pase con su ubicación. Cualquier representación basada en rutas —la cadena de carpetas separada por barras, el índice dentro de una lista de hijos— convierte la ubicación en el nombre, y entonces mover algo equivale a renombrarlo, con toda la cascada de referencias rotas que eso implica. La quinta lección vuelve sobre esto con detalle, porque es la raíz del error de modelado más caro de este nivel.

Fíjate en lo que ese mover de dos líneas no comprueba, porque es exactamente el tema de las cuatro lecciones siguientes. No comprueba que el nuevo padre exista. No comprueba que el nuevo padre no sea descendiente del hijo. Y sobre todo, no puede comprobar nada de eso de forma local, porque la respuesta depende de claves que no son la que se está escribiendo.

flowchart TD
N[notas.md] --> P[Proyecto]
P --> D[Documentos]
D --> R[raiz]
R --> F[la cadena termina: hay arbol]
style R fill:#89b4fa,color:#11111b
style F fill:#a6e3a1,color:#11111b

Tres invariantes y solo una sale gratis

Con la representación elegida, las condiciones que hacen que un mapa sea de verdad un árbol se enuncian con precisión. La primera es que cada nodo tenga como mucho un padre, y ya está resuelta por construcción. La segunda es que no haya ciclos. La tercera es que todo nodo alcance la raíz siguiendo la cadena de padres.

Hay una cuarta condición que a veces se añade y que conviene descartar por innecesaria: que exista una única raíz. Con la representación elegida sale gratis, porque la raíz es sencillamente el nodo sin entrada en el mapa, y basta con fijarla por convención al crear el documento. Los casos donde interesa permitir varias raíces —un bosque en vez de un árbol— cambian algunos detalles de las estrategias que verás después, pero no cambian nada del problema central, porque los ciclos aparecen igual.

La observación que conviene tener grabada es que las dos últimas no son independientes: en un grafo finito donde cada nodo tiene exactamente un puntero saliente, son la misma condición. El argumento cabe en tres frases. Parte de cualquier nodo y sigue la cadena de padres; como el conjunto de nodos es finito, o llegas a un nodo sin padre —la raíz— o repites alguno, y repetir uno significa haber entrado en un ciclo. No hay tercera opción. Por tanto aciclicidad y alcanzabilidad son equivalentes, y basta con vigilar una de las dos.

// Una sola comprobacion cubre las dos invariantes que no salen gratis.
function alcanzaLaRaiz(padre, nodo, raiz = "raiz") {
  const vistos = new Set();
  let actual = nodo;
  while (actual !== undefined && actual !== raiz) {
    if (vistos.has(actual)) return false; // se repitio: hay ciclo
    vistos.add(actual);
    actual = padre.get(actual);
  }
  return actual === raiz;
}

function esArbol(padre, raiz = "raiz") {
  return [...padre.keys()].every((n) => alcanzaLaRaiz(padre, n, raiz));
}

La forma de esa función dice más de lo que parece sobre el coste de la materia. esArbol recorre todas las claves y cada recorrido puede subir hasta la raíz, de modo que verificar la invariante cuesta, en el peor caso, proporcional al número de nodos por la profundidad. No es un coste prohibitivo, pero tampoco es constante, y esa es la diferencia estructural con todo lo anterior: comprobar que un conjunto sigue siendo un conjunto cuesta cero.

Por qué un mapa que converge no basta

Llegamos al punto donde este nivel se separa de todos los anteriores. Toma el mapa de padres y resuelve cada clave con la política que prefieras: último escritor según reloj lógico, desempate por identidad de réplica, lo que sea. Ese mapa es, palabra por palabra, el tipo que el nivel 30 construyó y demostró correcto, y no hay nada que reprocharle: cumple todas las propiedades que se le pidieron. Esa política converge, en el sentido técnico y exigente que el track lleva usando desde el principio: todas las réplicas que hayan visto las mismas operaciones tienen el mismo mapa, con independencia del orden de entrega y de los duplicados.

Y sin embargo el mapa al que convergen puede no ser un árbol. No porque la política sea mala, sino porque la política opera sobre claves individuales mientras que la invariante es una propiedad del mapa entero. Cada clave puede tener un ganador impecable, defendible ante cualquier usuario, y la combinación de ganadores impecables violar la aciclicidad. Esto es exactamente el conflicto semántico que el nivel 23 describió en abstracto, con la diferencia de que aquí no es un caso patológico rebuscado con fechas de inicio y fin: es el resultado de dos personas ordenando sus carpetas.

Y conviene notar que el mapa de padres, además de converger, hace bien casi todo lo demás. Sobrevive a los duplicados de entrega, porque escribir dos veces el mismo padre en la misma clave es idempotente. Sobrevive al reordenamiento, porque la política de cada clave no depende del orden de llegada. Y compone sin fricción con todo lo que cuelgue de cada nodo, porque el contenido de un nodo vive en su propio contenedor y no en la arista. De las muchas propiedades deseables que un tipo replicado puede tener, este mapa las tiene todas menos una, y esa una es la que hace que sea un árbol.

Merece la pena decir con claridad qué queda descartado. No se arregla afinando la granularidad, porque ya es máxima: una clave por arista. No se arregla con un reloj mejor, porque el problema no es que no sepamos qué pasó antes. No se arregla con un tipo convergente más listo para el valor, porque el valor de cada clave es un identificador de nodo y ahí no hay nada que fusionar. La invariante que se rompe no vive en ningún valor: vive en la relación entre valores.

Dicho de otro modo, y esta es la formulación que conviene llevarse: la fusión de dos mapas válidos es un mapa, pero la fusión de dos árboles válidos no tiene por qué ser un árbol. La clase de los mapas es cerrada bajo la operación de fusión y la clase de los árboles no lo es, y toda la dificultad del nivel cabe en esa diferencia. Cuando una clase no es cerrada bajo la operación que tu sistema aplica sin preguntar, necesitas algo que devuelva el resultado a la clase, y ese algo es lo que las lecciones siguientes construyen.

Antes de pasar al escenario conviene anticipar por qué esto no se arregla tampoco poniendo la comprobación en el sitio evidente. Si validas la invariante antes de emitir una operación, protegerás a tu réplica de emitir tonterías y no protegerás nada más, porque la otra réplica está haciendo lo mismo contra un estado distinto y las dos pasarán su propia validación. Y si la validas al recibir, rechazando lo que rompería tu árbol, cada réplica rechazará una cosa distinta y acabarás con divergencia permanente. Ninguna de las dos posiciones obvias funciona, y entender por qué es la mitad del camino hacia las que sí.

Con esto queda montado el escenario. Tenemos una representación mínima, una invariante que no se comprueba mirando una arista y una política de fusión que converge a estados que la violan. Lo único que falta es el par de operaciones concretas que produce la violación, y es tan corriente que probablemente lo hayas hecho sin enterarte: dos personas reorganizando la misma jerarquía al mismo tiempo. Esa es la siguiente lección.