33. Iteradores en Árboles Binarios de Busqueda (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.
33.1. Interfaz 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.
1package types
2
3// Iterator es una interfaz genérica que define un iterador para colecciones.
4type Iterator[T any] interface {
5 HasNext() bool
6 Next() (T, error)
7}
Los métodos que debe implementar un iterador son los siguientes
- HasNext
Indica si hay un siguiente elemento en la colección. Devuelve
truesi hay más elementos por recorrer, ofalsesi 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.
33.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 es genérico del tipo constraints.Ordered, lo que significa que los valores deben ser comparables y ordenables, es decir deben soportar las operaciones de comparación como <, <=, >, >=, == y !=.
A continuación se muestra la estructura del nodo del ABB.
7type BinaryNode[T constraints.Ordered] struct {
8 left *BinaryNode[T]
9 right *BinaryNode[T]
10 data T
11}
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:
1package binarytree
2
3import (
4 "apunte/types"
5
6 "golang.org/x/exp/constraints"
7)
8
9// BinarySearchTree implementa un árbol binario de búsqueda
10// (Binary Search Tree, BST).
11// El árbol está compuesto por nodos de tipo BinaryNode, que contienen un valor
12// de tipo T generico pero Ordered.
13type BinarySearchTree[T constraints.Ordered] struct {
14 root *BinaryNode[T]
15}
16
17// NewBinarySearchTree crea un nuevo BinarySearchTree de tipo Ordered.
18//
19// Uso:
20//
21// bst := tree.NewBinarySearchTree[int]()
22//
23// Retorna:
24// - un puntero a un nuevo BinarySearchTree.
25func NewBinarySearchTree[T constraints.Ordered]() *BinarySearchTree[T] {
26 return &BinarySearchTree[T]{root: nil}
27}
28
29// GetRoot obtiene el nodo raíz del árbol.
30//
31// Uso:
32//
33// bst := tree.NewBinarySearchTree[int]()
34// bst.GetRoot()
35//
36// Retorna:
37// - un puntero al nodo raíz del árbol.
38func (bst *BinarySearchTree[T]) GetRoot() *BinaryNode[T] {
39 return bst.root
40}
41
42// Insert inserta un nuevo nodo en el árbol.
43//
44// Uso:
45//
46// bst := tree.NewBinarySearchTree[int]()
47// bst.Insert(4)
48//
49// Parámetros:
50// - `k` un valor de tipo T.
51func (bst *BinarySearchTree[T]) Insert(k T) {
52 bst.root = bst.insertByNode(bst.root, k)
53}
54
55// insertByNode inserta un nuevo nodo en el árbol.
56//
57// Parámetros:
58// - `node` un puntero a un BinaryNode.
59// - `k` un valor de tipo T.
60//
61// Retorna:
62// - un puntero al nodo raíz del árbol.
63func (bst *BinarySearchTree[T]) insertByNode(
64 node *BinaryNode[T], k T) *BinaryNode[T] {
65
66 if node == nil {
67 return NewBinaryNode(k, nil, nil)
68 }
69
70 if k < node.data {
71 node.left = bst.insertByNode(node.left, k)
72 } else if k > node.data {
73 node.right = bst.insertByNode(node.right, k)
74 }
75 return node
76}
77
78func (bst *BinarySearchTree[T]) Clear() {
79 bst.root = nil
80}
81
82// IsEmpty evalúa si el árbol está vacío.
83//
84// Uso:
85//
86// bst := tree.NewBinarySearchTree[int]()
87// bst.IsEmpty()
88//
89// Retorna:
90// - `true` si el árbol está vacío; `false` si no lo está.
91func (bst *BinarySearchTree[T]) IsEmpty() bool {
92 return bst.root == nil
93}
94
95func (bst *BinarySearchTree[T]) InorderIterator() types.Iterator[T] {
96 iter := newInorderIterator(bst.root)
97 return iter
98}
99
100func (bst *BinarySearchTree[T]) PreorderIterator() types.Iterator[T] {
101 iter := newPreorderIterator(bst.root)
102 return iter
103}
104
105func (bst *BinarySearchTree[T]) PostorderIterator() types.Iterator[T] {
106 iter := newPostorderIterator(bst.root)
107 return iter
108}
Al crear un iterador se ejecuta un setup inicial que depende de cada tipo de iterador.
33.3. Implementació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).
Nota
Que sea lazy significa que el iterador no calcula todos los elementos de antemano, sino que los obtiene a medida que se le solicita un nuevo elemento. Esto es fundamental para manejar colecciones grandes o infinitas sin consumir demasiada memoria.
33.3.1. La 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(logN)).
- 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.
33.4. Iterador Inorder#
La estrategia para el iterador inorder es la siguiente:
Comenzamos desde la raíz del árbol.
Vamos hacia la izquierda hasta llegar al nodo más a la izquierda apilando los nodos en la pila.
El menor elemento del árbol será el nodo más a la izquierda es el que se encuentra en el tope de la pila.
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.
Una vez que no hay más nodos a la izquierda, el tope de la pila contendrá el siguiente nodo en orden.
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
1package binarytree
2
3import (
4 "apunte/stack"
5 "errors"
6
7 "golang.org/x/exp/constraints"
8)
9
10// InorderIterator implementa un iterador para recorrer un árbol binario de
11// búsqueda en order (inorder).
12// Utiliza una pila para almacenar los nodos visitados y permite iterar sobre
13// ellos en order ascendente.
14type InorderIterator[T constraints.Ordered] struct {
15 stack *stack.Stack[*BinaryNode[T]]
16}
17
18func newInorderIterator[T constraints.Ordered](root *BinaryNode[T]) *InorderIterator[T] {
19 // Crea un nuevo iterador de tipo InorderIterator.
20 it := &InorderIterator[T]{}
21 // Inicializa el iterador con la raíz del árbol y apila todos los nodos
22 // izquierdos.
23 it.stack = stack.NewStack[*BinaryNode[T]]()
24 if root != nil {
25 it.pushLeftNodes(root)
26 }
27 // Devuelve el iterador inicializado.
28 // Si la raíz es nula, la pila estará vacía y no habrá nodos para iterar.
29 return it
30}
31
32// pushLeftNodes apila todos los nodos izquierdos desde un nodo dado.
33// Parámetros:
34// - node: un puntero al nodo desde el cual comenzar a apilar los nodos
35//
36// izquierdos.
37func (it *InorderIterator[T]) pushLeftNodes(node *BinaryNode[T]) {
38 for node != nil {
39 it.stack.Push(node)
40 node = node.GetLeft()
41 }
42}
43
44// HasNext verifica si hay más elementos para iterar en el árbol.
45// Retorna:
46// - true si hay más elementos, false en caso contrario.
47func (it *InorderIterator[T]) HasNext() bool {
48 return !it.stack.IsEmpty()
49}
50
51// Next devuelve el siguiente elemento del árbol en order inorder.
52// La semántica de Next consiste en avanzar primero al siguiente
53// elemento y luego devolverlo. Si no hay más elementos, devuelve un error.
54// Retorna:
55// - el siguiente elemento del tipo T en el árbol.
56// - un error si no hay más elementos para iterar.
57func (it *InorderIterator[T]) Next() (T, error) {
58 if !it.HasNext() {
59 var zero T // Valor cero para el tipo T
60 return zero, errors.New("no hay más elementos para iterar")
61 }
62
63 // Obtener el nodo actual del tope de la pila.
64 currentNode, _ := it.stack.Pop()
65
66 // Apilar los nodos izquierdos del hijo derecho del nodo actual.
67 it.pushLeftNodes(currentNode.GetRight())
68
69 // Devolver el dato del nodo actual.
70 return currentNode.GetData(), nil
71}
33.5. Iterador 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
Comenzamos desde la raíz del árbol.
Apilamos sólo la raíz
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.
Devolvemos el elemento del nodo que acabamos de sacar de la pila.
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.
1package binarytree
2
3import (
4 "apunte/stack"
5 "errors"
6
7 "golang.org/x/exp/constraints"
8)
9
10type PreorderIterator[T constraints.Ordered] struct {
11 stack *stack.Stack[*BinaryNode[T]]
12}
13
14func newPreorderIterator[T constraints.Ordered](root *BinaryNode[T]) *PreorderIterator[T] {
15 // Crea un nuevo iterador de tipo PreorderIterator.
16 it := &PreorderIterator[T]{}
17 // Inicializa el iterador con la raíz del árbol y apila la raíz.
18 it.stack = stack.NewStack[*BinaryNode[T]]()
19 if root != nil {
20 it.stack.Push(root)
21 }
22 // Devuelve el iterador inicializado.
23 // Si la raíz es nula, la pila estará vacía y no habrá nodos para iterar.
24 return it
25}
26
27// HasNext verifica si hay más elementos para iterar en el árbol.
28func (it *PreorderIterator[T]) HasNext() bool {
29 return !it.stack.IsEmpty()
30}
31
32// Next devuelve el siguiente elemento del árbol en order preorder.
33func (it *PreorderIterator[T]) Next() (T, error) {
34 if !it.HasNext() {
35 var zero T
36 return zero, errors.New("no hay más elementos para iterar")
37 }
38
39 // Obtener el nodo actual del tope de la pila.
40 currentNode, _ := it.stack.Pop()
41
42 // Apilar el hijo derecho primero, luego el izquierdo.
43 if currentNode.GetRight() != nil {
44 it.stack.Push(currentNode.GetRight())
45 }
46
47 if currentNode.GetLeft() != nil {
48 it.stack.Push(currentNode.GetLeft())
49 }
50
51 // Devolver el dato del nodo actual.
52 return currentNode.GetData(), nil
53}
33.6. Iterador 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 Preorder
El setup inicial consiste en apilar la raíz solamente.
1package binarytree
2
3import (
4 "apunte/stack"
5 "errors"
6
7 "golang.org/x/exp/constraints"
8)
9
10// PostorderIterator implementa un iterador para recorrer un árbol binario
11// en postorder (postorden).
12// Utiliza dos pilas para almacenar los nodos visitados y permite iterar sobre
13// ellos en postorden, es decir, primero los hijos izquierdo y derecho, y
14// finalmente el nodo padre.
15type PostorderIterator[T constraints.Ordered] struct {
16 stack1 *stack.Stack[*BinaryNode[T]]
17 stack2 *stack.Stack[*BinaryNode[T]]
18}
19
20// newPostorderIterator crea un nuevo iterador para recorrer un árbol binario
21// inicializa las pilas, apilando en la primera pila los nodos del árbol
22func newPostorderIterator[T constraints.Ordered](root *BinaryNode[T]) *PostorderIterator[T] {
23 it := &PostorderIterator[T]{
24 stack1: stack.NewStack[*BinaryNode[T]](),
25 stack2: stack.NewStack[*BinaryNode[T]](),
26 }
27 if root != nil {
28 it.stack1.Push(root)
29 for !it.stack1.IsEmpty() {
30 node, _ := it.stack1.Pop()
31 it.stack2.Push(node)
32 if node.GetLeft() != nil {
33 it.stack1.Push(node.GetLeft())
34 }
35 if node.GetRight() != nil {
36 it.stack1.Push(node.GetRight())
37 }
38 }
39 }
40 return it
41}
42
43func (it *PostorderIterator[T]) HasNext() bool {
44 return !it.stack2.IsEmpty()
45}
46
47func (it *PostorderIterator[T]) Next() (T, error) {
48 var zero T
49 if it.stack2.IsEmpty() {
50 return zero, errors.New("no hay más elementos para iterar")
51 }
52 node, _ := it.stack2.Pop()
53 return node.GetData(), nil
54}