Iteradores en Árboles Binarios de Búsqueda (ABB)

En este anexo, vamos a implementar iteradores para un Árbol Binario de Búsqueda (ABB) en Go. Los iteradores nos permiten recorrer los nodos del árbol de manera ordenada, facilitando la obtención de los valores almacenados. Elegimos implementarlos sobre un ABB para aprovechar su estructura ordenada.

1Interfaz del Iterador¶

En el siguiente fragmento de código definimos la interfaz Iterator que contendrá los métodos necesarios para iterar cualquier colección de elementos y en particular los nodos de un ABB.

1
2
3
4
5
// La interfaz Iterator define los métodos para iterar sobre una colección
type Iterator[T any] interface {
    HasNext() bool
    Next() (T, error)
}

Los métodos que debe implementar un iterador son los siguientes

HasNext

Indica si hay un siguiente elemento en la colección. Devuelve true si hay más elementos por recorrer, o false si se ha llegado al final de la colección.

Next

Devuelve el siguiente elemento de la colección. El comportamiento de Next consiste en avanzar al próximo elemento y devolverlo. Si no hay más elementos para iterar devuelve un elemento nulo y un error.

2Árbol Binario de Búsqueda (ABB)¶

En esta implementación de ABB la funcionalidad del árbol se encuentra en el árbol propiamente dicho y no en los nodos, con el propósito de simplificar el código y mejorar la legibilidad.

Los métodos incluidos son los mínimos y necesarios para crear un árbol, insertar elementos y obtener los distintos iteradores.

El árbol usa un tipo genérico con una función de comparación, lo que permite usar cualquier tipo que provea un criterio de orden.

A continuación se muestra la estructura del nodo del ABB.

1
2
3
4
5
6
// BinaryNode representa un nodo en el árbol binario
type BinaryNode[T any] struct {
    value T
    left  *BinaryNode[T]
    right *BinaryNode[T]
}

El tipo BinaryNode solo tiene los métodos necesarios para crear un nodo y obtener su valor. No contiene métodos para insertar o eliminar nodos, ya que toda la funcionalidad del árbol está implementada en BinarySearchTree directamente.

En la implementación del ABB tenemos los métodos para obtener los iteradores:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// BinarySearchTree implementa un árbol binario de búsqueda genérico
type BinarySearchTree[T any] struct {
    root *BinaryNode[T]
    cmp  func(T, T) int
}

// NewBinarySearchTree crea un nuevo ABB con la función de comparación dada
func NewBinarySearchTree[T any](cmp func(T, T) int) *BinarySearchTree[T] {
    return &BinarySearchTree[T]{cmp: cmp}
}

// Insert agrega un valor al árbol
func (t *BinarySearchTree[T]) Insert(value T) { ... }

// InorderIterator retorna un iterador inorder
func (t *BinarySearchTree[T]) InorderIterator() Iterator[T] { ... }

Al crear un iterador se ejecuta un setup inicial que depende de cada tipo de iterador.

3Implementación de los iteradores. El Desafío de Mantener el Estado: ¿Por qué no solo recursión?¶

Cuando estudiamos los recorridos de árboles (inorder, preorder, postorder), la forma más intuitiva y elegante de implementarlos es usando recursión, ya que el código queda conciso, limpio y fácil de entender.

Sin embargo, cuando hablamos de un iterador, la situación cambia. Un iterador, por definición (según el patrón Iterador), debe permitirnos obtener el “siguiente” elemento de la colección a demanda, sin tener que procesar el resto de la colección de antemano. Es decir, queremos que nuestro método Next() devuelva un único valor y luego HasNext() nos diga si hay más, esperando una nueva llamada a Next().

Aquí es donde la recursión directa presenta un desafío:

Manejo del estado

Una función recursiva completa su ejecución y devuelve un resultado. No “pausa” su estado para ser reanudada en el mismo punto más tarde. Cada llamada recursiva crea un nuevo stack frame (marco de pila) que se destruye al finalizar.

Devolución de un solo elemento

Si intentáramos adaptar la recursión para devolver un solo elemento en cada llamada a Next(), nos encontraríamos con que la función recursiva ya ha avanzado en el recorrido, y sería muy difícil mantener el “punto exacto” en el que nos quedamos para la siguiente llamada.

Espacio en memoria (stack overflow)

Para árboles muy grandes o muy desbalanceados (degenerados), una implementación recursiva podría consumir una gran cantidad de memoria de la pila de llamadas, llevando a un error de stack overflow.

Para superar estos desafíos y crear un iterador que sea lazy (bajo demanda) y eficiente en memoria, necesitamos una forma de simular la pila de llamadas recursiva de forma explícita. Y la estructura de datos perfecta para esto es, precisamente, una pila (stack).

3.1La Pila como Sustituto de la Recursión Explícita¶

Al usar una pila en nuestros iteradores, nosotros somos los que gestionamos el “estado” de la recursión. En lugar de que el sistema operativo maneje la pila de llamadas por nosotros, nosotros empujamos (Push) y sacamos (Pop) nodos de nuestra propia estructura de pila para recordar qué camino hemos tomado y qué nodos nos quedan por visitar.

Esta técnica nos permite:

Pausar y Reanudar

Cuando Next() es llamado, podemos extraer el siguiente nodo a visitar de la pila, devolverlo, y luego dejar la pila en un estado que representa el “resto” del recorrido. La próxima vez que se llame Next(), la pila nos recordará dónde estábamos.

Eficiencia en Memoria

La profundidad de la pila que necesitamos es proporcional a la altura del árbol ($O(h)$), no al número total de nodos ($O(N)$), lo que es mucho más eficiente para árboles grandes y balanceados ($O(\log{N})$).

Control Explícito

Tenemos un control total sobre el orden en que los nodos se agregan y se eliminan de la pila, lo que es fundamental para implementar correctamente los diferentes tipos de recorridos.

4Iterador Inorder¶

La estrategia para el iterador inorder es la siguiente:

1. Comenzamos desde la raíz del árbol.

2. Vamos hacia la izquierda hasta llegar al nodo más a la izquierda apilando los nodos en la pila.

3. El menor elemento del árbol será el nodo más a la izquierda es el que se encuentra en el tope de la pila.

4. Cuando llamamos a Next(), sacamos el nodo del tope de la pila, chequeamos si tiene un hijo derecho. Si lo tiene, vamos a ese hijo derecho y repetimos el proceso de ir hacia la izquierda, apilando los nodos.

5. Una vez que no hay más nodos a la izquierda, el tope de la pila contendrá el siguiente nodo en orden.

6. Devolvemos el elemento del nodo que acabamos de sacar de la pila.

En el siguiente fragmento de código se puede observar la implementación del iterador Inorder

El setup inicial consiste en apilar la raíz y toda la rama izquierda para iniciar. De esta forma el primer nodo que se desapila es el menor de todo el árbol

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// InorderIterator implementa un iterador inorder
type InorderIterator[T any] struct {
    stack []*BinaryNode[T]  // Pila principal para el recorrido
}

func (t *BinarySearchTree[T]) InorderIterator() Iterator[T] {
    iter := &InorderIterator[T]{stack: make([]*BinaryNode[T], 0)}
    // Setup: apilar raíz y toda la rama izquierda
    node := t.root
    for node != nil {
        iter.stack = append(iter.stack, node)
        node = node.left
    }
    return iter
}

func (iter *InorderIterator[T]) HasNext() bool {
    return len(iter.stack) > 0
}

func (iter *InorderIterator[T]) Next() (T, error) {
    // Implementación del Next...
    var zero T
    return zero, nil
}

5Iterador Preorder¶

La estrategia para el iterador preorder varía un poco, ya que lo primero que debemos listar es la raíz, por lo tanto el setup inicial consiste en apilar sólo la raíz

1. Comenzamos desde la raíz del árbol.

2. Apilamos sólo la raíz

3. Al desapilar un nodo cuando se llama a Next(), se apilan primero su hijo derecho y luego su hijo izquierdo (para que el orden de salida de la pila sea primero el izquierdo y luego el derecho). El próximo en salir de la pila será la raíz del subárbol izquierdo.

4. Devolvemos el elemento del nodo que acabamos de sacar de la pila.

5. Se repite hasta que la pila queda vacía.

En el siguiente fragmento de código se puede observar la implementación del iterador Preorder

El setup inicial consiste en apilar la raíz solamente.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// PreorderIterator implementa un iterador preorder
type PreorderIterator[T any] struct {
    stack []*BinaryNode[T]
}

func (t *BinarySearchTree[T]) PreorderIterator() Iterator[T] {
    iter := &PreorderIterator[T]{stack: make([]*BinaryNode[T], 0)}
    if t.root != nil {
        iter.stack = append(iter.stack, t.root)
    }
    return iter
}

func (iter *PreorderIterator[T]) HasNext() bool {
    return len(iter.stack) > 0
}

func (iter *PreorderIterator[T]) Next() (T, error) {
    // Implementación...
    var zero T
    return zero, nil
}

6Iterador Postorder¶

Para implementar el iterador Postorder se necesitan 2 pilas.

El recorrido postorder visita los nodos en el orden: izquierda, derecha, raíz. Sin embargo, si usamos una sola pila y simplemente apilamos los hijos izquierdo y derecho, no es sencillo garantizar este orden sin usar recursión.

Por eso, se usan dos pilas para simular el recorrido postorder de manera iterativa, la primera pila se usa para recorrer el árbol y la segunda para almacenar los nodos en postorder. La inicialización del iterador implica recorrer todo el árbol y apilar los nodos en la segunda pila. Luego se pueden desapilar los nodos de la segunda pila a demanda.

• Setup inicial:

  • Se apila la raíz en la primera pila.

  • Mientras stack1 no esté vacía:

    • Se desapila un nodo de stack1 y se apila en la segunda pila (stack2).

    • Si el nodo tiene hijo izquierdo, se apila en stack1.

    • Si el nodo tiene hijo derecho, se apila en stack1.

  Así, stack1 sirve para recorrer el árbol y stack2 va guardando los nodos en un orden tal que, al desapilar de stack2, obtenemos el recorrido postorder.

• Iteración:

• Cuando se llama a Next(), simplemente se desapila un nodo de stack2 y se devuelve su valor.

• HasNext() verifica si stack2 aún tiene nodos.

En el siguiente fragmento de código se puede observar la implementación del iterador Postorder

El setup inicial consiste en apilar la raíz en la primera pila y luego procesar el árbol para llenar la segunda pila en orden postorder.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// PostorderIterator implementa un iterador postorder usando dos pilas
type PostorderIterator[T any] struct {
    stack1 []*BinaryNode[T]
    stack2 []*BinaryNode[T]
}

func (t *BinarySearchTree[T]) PostorderIterator() Iterator[T] {
    iter := &PostorderIterator[T]{
        stack1: make([]*BinaryNode[T], 0),
        stack2: make([]*BinaryNode[T], 0),
    }
    if t.root != nil {
        iter.stack1 = append(iter.stack1, t.root)
    }
    for len(iter.stack1) > 0 {
        node := iter.stack1[len(iter.stack1)-1]
        iter.stack1 = iter.stack1[:len(iter.stack1)-1]
        iter.stack2 = append(iter.stack2, node)
        if node.left != nil {
            iter.stack1 = append(iter.stack1, node.left)
        }
        if node.right != nil {
            iter.stack1 = append(iter.stack1, node.right)
        }
    }
    return iter
}

func (iter *PostorderIterator[T]) HasNext() bool {
    return len(iter.stack2) > 0
}

func (iter *PostorderIterator[T]) Next() (T, error) {
    // Implementación...
    var zero T
    return zero, nil
}

7Código completo en Go¶

El código completo de este anexo está disponible en el repositorio guia-iteradores-abb.