De Árbol Binario a Lista Doblemente Enlazada

En el mundo de la programación y las estructuras de datos, los árboles binarios y las listas enlazadas son dos de los pilares fundamentales. Cada uno tiene sus propias fortalezas y debilidades. Los árboles son excelentes para búsquedas rápidas y representación de datos jerárquicos, mientras que las listas son ideales para secuencias lineales y operaciones de inserción/eliminación sencillas. Pero, ¿qué sucede cuando necesitas las propiedades de ambos? Una tarea común y un excelente ejercicio algorítmico es convertir un árbol binario en una lista doblemente enlazada (DLL). Esta operación, conocida como "aplanar" el árbol, nos permite recorrer los nodos de forma secuencial, tanto hacia adelante como hacia atrás, manteniendo un orden específico. En este artículo, exploraremos a fondo cómo realizar esta conversión "in-place", es decir, reutilizando los propios nodos del árbol sin asignar memoria adicional, utilizando diferentes enfoques con sus respectivas ventajas y complejidades.

La Clave del Éxito: El Recorrido Inorden

Antes de sumergirnos en los algoritmos, es crucial entender el concepto que gobierna esta transformación: el recorrido inorden (Inorder Traversal). En un recorrido inorden, procesamos un árbol siguiendo la secuencia: Izquierda -> Raíz -> Derecha. Cuando aplicamos este recorrido a un Árbol Binario de Búsqueda (BST), obtenemos los nodos en orden ascendente. Para cualquier árbol binario, nos proporciona una secuencia lineal única y predecible. Este orden es precisamente el que queremos preservar en nuestra lista doblemente enlazada final. El nodo más a la izquierda del árbol se convertirá en la cabeza (head) de la lista, y el nodo más a la derecha será la cola (tail).

El objetivo es modificar los punteros `left` y `right` de cada nodo del árbol para que actúen como los punteros `previous` y `next` de una lista doblemente enlazada.

• El puntero `left` de un nodo apuntará al nodo que lo precede en el recorrido inorden.
• El puntero `right` de un nodo apuntará al nodo que lo sucede en el recorrido inorden.

Enfoque 1: Recursión Simple con Búsqueda de Predecesor

Este es uno de los primeros enfoques que pueden venir a la mente. La idea es utilizar la recursión para aplicar el recorrido inorden y, en cada paso, conectar el nodo actual con sus vecinos inmediatos en la secuencia final. Para un nodo `N`, su predecesor inorden es el nodo más a la derecha en su subárbol izquierdo, y su sucesor inorden es el nodo más a la izquierda en su subárbol derecho.

Lógica del Algoritmo

1. Procesar subárbol izquierdo: Realiza una llamada recursiva sobre el subárbol izquierdo. Esto convertirá esa porción del árbol en una DLL parcial.
2. Conectar con el predecesor: Si el nodo actual (`root`) tiene un subárbol izquierdo, encuentra su predecesor inorden (el nodo más a la derecha del subárbol izquierdo). Una vez encontrado, establece la conexión: `predecesor->right = root` y `root->left = predecesor`.
3. Procesar subárbol derecho: Realiza una llamada recursiva sobre el subárbol derecho.
4. Conectar con el sucesor: Si el nodo actual (`root`) tiene un subárbol derecho, encuentra su sucesor inorden (el nodo más a la izquierda del subárbol derecho). Establece la conexión: `root->right = sucesor` y `sucesor->left = root`.
5. Obtener la cabeza: Una vez que la recursión ha terminado, la cabeza de la lista será el nodo más a la izquierda de todo el árbol original.

Implementación de Ejemplo (Python)

A continuación se muestra una implementación en Python que sigue esta lógica.

class Node: def __init__(self, new_value): self.data = new_value self.left = None self.right = None def inorder_connect(root): # Si el subárbol izquierdo existe if root.left: # 1. Procesar recursivamente el subárbol izquierdo inorder_connect(root.left) # 2. Encontrar el predecesor (el más a la derecha del subárbol izquierdo) pred = root.left while pred.right: pred = pred.right # 3. Conectar predecesor con la raíz actual pred.right = root root.left = pred # Si el subárbol derecho existe if root.right: # 4. Procesar recursivamente el subárbol derecho inorder_connect(root.right) # 5. Encontrar el sucesor (el más a la izquierda del subárbol derecho) succ = root.right while succ.left: succ = succ.left # 6. Conectar la raíz actual con el sucesor root.right = succ succ.left = root def binary_tree_to_dll(root): if not root: return None # Realiza la conversión in-place inorder_connect(root) # Encuentra la cabeza de la lista (el nodo más a la izquierda) head = root while head.left: head = head.left return head 

Análisis de Complejidad

• Complejidad Temporal: O(n), donde 'n' es el número de nodos. Aunque parece que buscar el predecesor y sucesor en cada paso podría ser costoso, cada nodo es visitado un número constante de veces en el proceso global.
• Complejidad Espacial: O(h), donde 'h' es la altura del árbol. Este espacio es consumido por la pila de recursión. En el peor de los casos (un árbol degenerado), esto puede ser O(n).

Enfoque 2: La Solución Óptima - Recorrido de Morris

Si bien el enfoque recursivo es funcional, su dependencia de la pila de recursión lo hace subóptimo en términos de espacio, especialmente para árboles muy altos. Aquí es donde brilla el Recorrido de Morris. Es un algoritmo ingenioso que permite recorrer un árbol binario sin usar recursión ni una pila explícita, logrando una complejidad espacial de O(1).

¿Qué es el Recorrido de Morris?

La idea central es crear "hilos" o enlaces temporales en el árbol para poder regresar a los nodos padres después de visitar sus subárboles izquierdos. Específicamente, para un nodo `current`, antes de moverse a su hijo izquierdo, encuentra su predecesor inorden. Luego, crea un enlace temporal desde `predecesor.right` hacia `current`. Este hilo nos permitirá volver a `current` después de haber recorrido todo su subárbol izquierdo.

Paso a Paso del Algoritmo de Conversión

Adaptamos el Recorrido de Morris para no solo visitar los nodos, sino también para re-cablear sus punteros y construir la DLL sobre la marcha.

1. Inicializa un puntero `head = None` y `tail = None` para nuestra DLL.
2. Inicializa `current = root`.
3. Mientras `current` no sea nulo:
• Caso 1: `current` no tiene hijo izquierdo.
  Esto significa que `current` es el siguiente nodo en el recorrido inorden. Lo procesamos: lo añadimos a nuestra DLL. Si `head` es nulo, `current` es el primer nodo (`head = tail = current`). De lo contrario, lo enlazamos al final (`tail.right = current`, `current.left = tail`, `tail = current`). Después, avanzamos a la derecha: `current = current.right`.
• Caso 2: `current` tiene hijo izquierdo.
  Aquí es donde ocurre la magia. Encontramos el predecesor inorden de `current` (el nodo más a la derecha en el subárbol izquierdo de `current`).
• Subcaso 2a: El predecesor no tiene un hilo. Si `predecesor.right` es nulo, creamos el hilo: `predecesor.right = current`. Luego, nos movemos al subárbol izquierdo: `current = current.left`.
• Subcaso 2b: El predecesor ya tiene un hilo. Si `predecesor.right` apunta a `current`, significa que ya hemos visitado todo el subárbol izquierdo. Ahora es el momento de procesar `current`. Lo añadimos a la DLL (igual que en el Caso 1). Rompemos el hilo (`predecesor.right = None`) para restaurar el árbol y avanzamos hacia la derecha: `current = current.right`.
4. Al final, `head` apuntará al inicio de la lista doblemente enlazada.

Implementación de Ejemplo (Python)

def morris_traversal_to_dll(root): if not root: return None head = None tail = None curr = root while curr is not None: if curr.left is None: # Procesar el nodo actual if head is None: head = tail = curr else: tail.right = curr curr.left = tail tail = curr curr = curr.right else: # Encontrar el predecesor inorden pred = curr.left while pred.right is not None and pred.right != curr: pred = pred.right if pred.right is None: # Crear el hilo pred.right = curr curr = curr.left else: # El subárbol izquierdo ya fue visitado, romper el hilo pred.right = None # Procesar el nodo actual tail.right = curr curr.left = tail tail = curr curr = curr.right return head 

Análisis de Complejidad

• Complejidad Temporal: O(n). Aunque parece que hay bucles anidados, cada borde del árbol se atraviesa un máximo de dos veces (una para crear el hilo y otra para eliminarlo). Por lo tanto, el tiempo total es lineal.
• Complejidad Espacial:O(1). Esta es la gran ventaja. No usamos pila de recursión ni estructuras de datos auxiliares. La conversión es verdaderamente "in-place".

Tabla Comparativa de Enfoques

¿Por Qué es Útil esta Conversión? Aplicaciones Prácticas

Convertir un árbol en una DLL puede no parecer una tarea cotidiana, pero tiene aplicaciones importantes:

• Iteración Eficiente: Una vez aplanado, puedes iterar sobre todos los elementos del árbol en orden, tanto hacia adelante como hacia atrás, con una simple operación de puntero, lo cual es mucho más rápido que realizar un recorrido completo cada vez.
• Balanceo de Árboles: Algunos algoritmos para balancear árboles (como convertir un BST en una vid y luego en un árbol balanceado) utilizan una estructura lineal intermedia.
• Serialización: Guardar el estado de un árbol en un formato lineal para almacenamiento o transmisión puede ser más sencillo si primero se convierte en una lista.
• Puente entre Estructuras: Facilita la interoperabilidad con otras partes de un sistema que esperan una estructura de datos secuencial en lugar de una jerárquica.

Preguntas Frecuentes (FAQ)

¿Qué significa una conversión "in-place"?

Significa que la operación se realiza modificando la estructura de datos existente (el árbol) sin asignar memoria nueva para crear la lista. Los mismos nodos del árbol se reutilizan para formar los nodos de la lista doblemente enlazada.

¿Por qué se usa el recorrido inorden y no otro?

El recorrido inorden es el estándar porque para un Árbol Binario de Búsqueda, produce una secuencia ordenada de elementos. Para un árbol binario general, proporciona una secuencia predecible y lógica. Sin embargo, la misma técnica podría adaptarse para producir una lista en orden de preorden o postorden si la aplicación lo requiere.

¿Cuál es la principal ventaja del Recorrido de Morris?

Su increíble eficiencia espacial. Al no usar recursión ni una pila, su consumo de memoria auxiliar es constante (O(1)), lo que lo hace ideal para árboles masivos o en entornos con memoria restringida donde un desbordamiento de pila (stack overflow) es un riesgo.

¿La estructura original del árbol se pierde después de la conversión?

Sí. Dado que los punteros `left` y `right` se reutilizan para `prev` y `next`, la estructura jerárquica original del árbol se destruye. La operación es, en general, irreversible a menos que se almacene la estructura original de alguna manera.