Gestionar árbol de datos o nodos conectados

Un árbol de datos es una estructura jerárquica donde cada nodo tiene un valor y puede tener cero o más nodos hijos, que a su vez cada nodo posee sus propios hijos. Piensa en directorios, o carpetas, en un sistema operativo. Cada carpeta puede contener archivos, pero también otras carpetas con sus propios archivos u carpetas. En otras palabras, puede existir carpetas dentro de otras carpetas sin ningún tipo límite aparente. Otra implementación podría ser un sistema de comentarios o microblogging (como X/Twitter o Mastodon). Cada publicación/mensaje puede tener réplicas, y a su vez cada réplica las suyas con sus propios hilos. Cualquier sistema con información en forma de árbol.

Para almacena un árbol de datos en una base de datos es sencillo ya que guardamos cada nodo en una tabla que contiene una referencia a su nodo padre. Veamos la estructura de unos comentarios con las columnas id, contenido y padre_id:

- Juan: Gracias por el artículo.
- María: Me ha gustado mucho.
├─ Juan: Gracias, María.
- Pedro: No me ha gustado.
├─ Juan: ¿Por qué?
└─ Pedro: No me ha parecido interesante.
- Ana: Tengo una duda. ¿Podrías ayudarme?
└─ Juan: Claro, Ana. ¿En qué puedo ayudarte?
└─ Ana: ¿Puedo usar Linux?
        └─ Luis: Aprovecho la pregunta, ¿qué distribución recomiendas?

La tabla podría verse de la siguiente manera:

Si es un comentario raíz, el padre_id es NULL. Si es una respuesta a un comentario, el padre_id es el id del comentario al que responde.

Como puedes observar es fácil de guardar, pero a la hora de recuperar los datos, la cosa se complica. En algún momento tendremos que convertir esos nodos con referencias en una estructura de datos, como un diccionario en Python. Tal vez necesitemos representarlo (como crear una web), realizar operaciones (ver el padre con mayor profundidad), o cualquier otro asunto . Por ello voy a enseñarte cómo gestionar un árbol de datos usando un poco de recursividad y Python como referencia. Aunque es posible aplicar los mismos conceptos en cualquier otro lenguaje de programación o paradigma de programación (orientado a objetos o imperativo).

Convertir una lista de nodos en un árbol

Vamos a partir de la siguiente lista que podría representar los comentarios obtenidos de una supuesta base de datos:

comentarios = [
    {"id": 1, "contenido": "Gracias por el artículo.", "padre_id": None},
    {"id": 2, "contenido": "Me ha gustado mucho.", "padre_id": None},
    {"id": 3, "contenido": "Gracias, María.", "padre_id": 2},
    {"id": 4, "contenido": "No me ha gustado.", "padre_id": None},
    {"id": 5, "contenido": "¿Por qué?", "padre_id": 4},
    {"id": 6, "contenido": "No me ha parecido interesante.", "padre_id": 4},
    {"id": 7, "contenido": "Tengo una duda. ¿Podrías ayudarme?", "padre_id": None},
    {"id": 8, "contenido": "Claro, Ana. ¿En qué puedo ayudarte?", "padre_id": 7},
    {"id": 9, "contenido": "¿Puedo usar Linux?", "padre_id": 7},
    {"id": 10, "contenido": "Aprovecho la pregunta, ¿qué distribución recomiendas?", "padre_id": 9},
]

El objetivo es transformar los elementos de la lista de una sola dimensión a un árbol donde cada comentario tendrá sus respuestas como nodos hijos.

[
    {"comentario": {"id": 1, "contenido": "Gracias por el artículo.", "padre_id": None}, "hijos": []},
    {"comentario": {"id": 2, "contenido": "Me ha gustado mucho.", "padre_id": None}, "hijos": [
        {"comentario": {"id": 3, "contenido": "Gracias, María.", "padre_id": 2}, "hijos": []}
    ]},
    ...
]

El código para resolverlo es el siguiente:

def crear_arbol_de_nodos(arbol_de_nodos=[]):
    # Recolectar hijos por id
    def filtrar_nodos_por_padres(arbol_de_nodos, id=None):
        return tuple(filter(lambda nodo: nodo["padre_id"] == id, arbol_de_nodos))

    # Crear nodo
    def estructura_nodo(arbol_de_nodos, nodo):
        hijos = filtrar_nodos_por_padres(arbol_de_nodos, nodo["id"])
        return {
            "comentario": nodo,
            "hijos": [estructura_nodo(arbol_de_nodos, hijo) for hijo in hijos],
        }

    # Iterar todos los nodos padres
    return [
        estructura_nodo(arbol_de_nodos, nodo_padre)
        for nodo_padre in filtrar_nodos_por_padres(arbol_de_nodos)
    ]

Se divide en tres funciones anidadas:

1. filtrar_nodos_por_padres: Devuelve una tupla con los nodos que tienen como padre_id el id pasado como argumento. En otras palabras, los nodos hijos de una id dada.
2. estructura_nodo: Crea un diccionario con el nodo y sus hijos. Le dará el formato deseado a cada nodo.
3. crear_arbol_de_nodos: Itera todos los nodos padres y llama a estructura_nodo para cada uno de ellos.

¿Y como es posible que recorra todos los nodos padres, pero a su vez los hijos, y los hijos de los hijos, y así sucesivamente? La respuesta es la recursividad. La función estructura_nodo se llama a sí misma en cada hijo del nodo que se esta añadiendo. Sin duda esta es la parte interesante y complicada de entender.

El código podemos ejecutarlo de la siguiente manera:

print(crear_arbol_de_nodos(comentarios))

Y obtendremos el siguiente resultado:

[
    {
        "comentario": {
            "id": 1,
            "contenido": "Gracias por el artículo.",
            "padre_id": None,
        },
        "hijos": [],
    },
    {
        "comentario": {"id": 2, "contenido": "Me ha gustado mucho.", "padre_id": None},
        "hijos": [
            {
                "comentario": {"id": 3, "contenido": "Gracias, María.", "padre_id": 2},
                "hijos": [],
            }
        ],
    },
    {
        "comentario": {"id": 4, "contenido": "No me ha gustado.", "padre_id": None},
        "hijos": [
            {
                "comentario": {"id": 5, "contenido": "¿Por qué?", "padre_id": 4},
                "hijos": [],
            },
            {
                "comentario": {
                    "id": 6,
                    "contenido": "No me ha parecido interesante.",
                    "padre_id": 4,
                },
                "hijos": [],
            },
        ],
    },
    {
        "comentario": {
            "id": 7,
            "contenido": "Tengo una duda. ¿Podrías ayudarme?",
            "padre_id": None,
        },
        "hijos": [
            {
                "comentario": {
                    "id": 8,
                    "contenido": "Claro, Ana. ¿En qué puedo ayudarte?",
                    "padre_id": 7,
                },
                "hijos": [],
            },
            {
                "comentario": {
                    "id": 9,
                    "contenido": "¿Puedo usar Linux?",
                    "padre_id": 7,
                },
                "hijos": [
                    {
                        "comentario": {
                            "id": 10,
                            "contenido": "Aprovecho la pregunta, ¿qué distribución recomiendas?",
                            "padre_id": 9,
                        },
                        "hijos": [],
                    }
                ],
            },
        ],
    },
]

Si tuviéramos una columna con la fecha de creación de cada comentario, podríamos devolver los hijos ordenados. Actualmente se devuelven por el orden en el que se encuentran en la lista original. Podemos solucionarlo de 2 formas: ordenando la lista original, muy sencillo si los datos se obtienen de una base de datos (por ejemplo en Django Comentario.objects.order_by("created_at")), o ordenando los hijos en la función filtrar_nodos_por_padres antes de devolverlos.

def filtrar_nodos_por_padres(arbol_de_nodos, id=None):
    return tuple(sorted(
        filter(lambda nodo: nodo["padre_id"] == id, arbol_de_nodos),
        key=lambda nodo: nodo["created_at"]
    ))

Hemos aprendido a convertir una lista de nodos en un árbol de datos. En el siguiente artículo veremos cómo hacer lo contrario, convertir un árbol en una lista de nodos.

Flattening o aplanando árbol en una profundidad

Es común cuando estamos dibujando, o renderizando datos, invertir el proceso anterior: convertir un árbol en una lista o aplanar el árbol.

Volvemos a usar un poco de recursividad.

def aplanar_arbol(arbol, lista_plana=[]):
    for nodo_actual in arbol:
        lista_plana.append(nodo_actual["comentario"])
        if nodo_actual["hijos"]:
            aplanar_arbol(nodo_actual["hijos"], lista_plana)
    return lista_plana

La función aplanar_arbol recibe un árbol y una lista vacía por defecto donde se irá añadiendo cada nodo. Según se itera la lista, se añade cada nodo. En caso de tener hijos, se llama a la misma función (recursividad) con los hijos del nodo actual para que se repita el mismo proceso en el siguiente nivel de profundidad. Cuando se termine de iterar todos los nodos, se devolverá la lista plana.

El resultado será el diccionario inicial.

print(aplanar_arbol(crear_arbol_de_nodos(comentarios)))

"""
[
    {"id": 1, "contenido": "Gracias por el artículo.", "padre_id": None},
    {"id": 2, "contenido": "Me ha gustado mucho.", "padre_id": None},
    {"id": 3, "contenido": "Gracias, María.", "padre_id": 2},
    {"id": 4, "contenido": "No me ha gustado.", "padre_id": None},
    {"id": 5, "contenido": "¿Por qué?", "padre_id": 4},
    {"id": 6, "contenido": "No me ha parecido interesante.", "padre_id": 4},
    {"id": 7, "contenido": "Tengo una duda. ¿Podrías ayudarme?", "padre_id": None},
    {"id": 8, "contenido": "Claro, Ana. ¿En qué puedo ayudarte?", "padre_id": 7},
    {"id": 9, "contenido": "¿Puedo usar Linux?", "padre_id": 7},
    {
        "id": 10,
        "contenido": "Aprovecho la pregunta, ¿qué distribución recomiendas?",
        "padre_id": 9,
    },
]
"""

Ya hemos aprendido a trabajar con la transformación de una lista de nodos referenciados en un árbol y viceversa.

Espero que te ayude en tus proyectos y puedas aplicarlo al lenguaje con el cual trabajes.

Quedan muchas labores que realizar, como la eliminación de nodos, la actualización, la búsqueda, entre otras. Pero eso lo dejo para ti. Estoy seguro que lo lograrás.