Árboles Binarios de Búsqueda

En la siguiente figura se muestran dos árboles binarios. El de la izquierda es un ABB válido: su raíz es (7), el hijo izquierdo es (3) y el derecho es (9). A su vez, (3) tiene como hijos a (2) y (5), mientras que (9) tiene a (8) y (10). En todos los nodos se cumple que los valores del subárbol izquierdo son menores que la raíz y los del derecho son mayores.

El árbol de la derecha, en cambio, no es un ABB. Su raíz también es (7), con subárbol izquierdo de raíz (2) y subárbol derecho de raíz (9). El subárbol con raíz (2) tiene como hijos a (1) y (8), y el de raíz (9) tiene a (10) como hijo derecho. Si bien los subárboles izquierdo (con raíz 2) y derecho (con raíz 9) son ABB válidos, el árbol completo no lo es: el nodo (8) —marcado en rojo— está en el subárbol izquierdo de la raíz (7) pero (8) es mayor que (7), violando la propiedad fundamental del ABB.

El recorrido inorden de un árbol binario de búsqueda produce una secuencia ordenada de los valores almacenados en el árbol. Esto se debe a que, al visitar el subárbol izquierdo, el nodo raíz y luego el subárbol derecho, se garantiza que los nodos se procesen en orden ascendente.

Por ejemplo, en la siguiente figura se muestran dos árboles binarios de búsqueda que tienen el mismo recorrido inorden: 1, 2, 3, 5, 7, 9. Los árboles son diferentes porque los elementos se insertaron en diferente orden; sin embargo, al ser un ABB, el recorrido inorden es el mismo.

1Operaciones en un árbol binario de búsqueda¶

Las operaciones más comunes en un árbol binario de búsqueda son:

• Inserción: Agregar un nuevo nodo al árbol manteniendo la propiedad de ABB.

• Búsqueda: Encontrar un nodo en el árbol.

• Eliminación: Quitar un nodo del árbol manteniendo la propiedad de ABB.

1.1Inserción¶

La inserción en un árbol binario de búsqueda se realiza de manera recursiva. Se compara el valor a insertar con el valor del nodo actual y se decide si ir al subárbol izquierdo o derecho. Si el subárbol correspondiente está vacío, se inserta el nuevo nodo.

Para insertar un nuevo nodo en un árbol binario de búsqueda, se sigue el siguiente algoritmo:

1
2
3
4
5
6
7
8
9
10
FUNCION InsertarABB(raiz, valor)
    SI raiz ES nula ENTONCES
        raiz ← CrearNodo(valor)
    SINO SI valor < raiz.valor ENTONCES
        raiz.izquierdo ← InsertarABB(raiz.izquierdo, valor)
    SINO SI valor > raiz.valor ENTONCES
        raiz.derecho ← InsertarABB(raiz.derecho, valor)
    FIN SI
    RETORNAR raiz
FIN FUNCION

1. Se compara el valor a insertar con la raíz. Si es menor se desciende al subárbol izquierdo; si es mayor, al derecho.

2. Se repite el proceso recursivamente hasta encontrar un subárbol vacío donde insertar el nuevo nodo.

3. Una vez encontrada la posición, se inserta el nodo como hoja del árbol.

1.2Búsqueda¶

La búsqueda en un árbol binario de búsqueda también se realiza de manera recursiva. Se compara el valor buscado con el valor del nodo actual y se decide si ir al subárbol izquierdo o derecho. Si el valor es igual al del nodo actual, se ha encontrado el nodo, si en cambio se llega a un nodo nulo, el valor no está en el árbol.

1
2
3
4
5
6
7
8
9
10
11
FUNCION BuscarABB(raiz, valor)
    SI raiz ES nula ENTONCES
        RETORNAR nula
    SINO SI raiz.valor = valor ENTONCES
        RETORNAR raiz
    SINO SI valor < raiz.valor ENTONCES
        RETORNAR BuscarABB(raiz.izquierdo, valor)
    SINO
        RETORNAR BuscarABB(raiz.derecho, valor)
    FIN SI
FIN FUNCION

1.3Eliminación¶

La eliminación de un nodo en un árbol binario de búsqueda es un poco más compleja que la inserción y la búsqueda. Existen tres casos a considerar:

El nodo a eliminar es una hoja (no tiene hijos)

En este caso, simplemente se elimina el nodo. En el ejemplo se elimina la hoja (6).

El nodo a eliminar tiene un solo hijo

En este caso, se reemplaza el nodo a eliminar por su hijo. Esto se hace actualizando el puntero del padre del nodo a eliminar para que apunte al hijo del nodo a eliminar. En el ejemplo se elimina el nodo (5) que tiene sólo un hijo izquierdo (3) y se reemplaza por su hijo.

El nodo a eliminar tiene dos hijos

En este caso, se busca el nodo más pequeño en el subárbol derecho del nodo a eliminar (sucesor) o el nodo más grande en el subárbol izquierdo (predecesor). Luego, se reemplaza el valor del nodo a eliminar por el valor del sucesor o predecesor y se elimina el sucesor o predecesor (que siempre va a ser una hoja o a lo sumo va a tener un solo hijo).

En la siguiente figura se observa la eliminación de la raíz del árbol, el nodo (7).

Para ubicar al predecesor (es decir, el mayor elemento del subárbol izquierdo), se debe bajar al subárbol izquierdo y luego seguir bajando por las ramas derechas hasta llegar a un nodo que no tenga hijo derecho. En este caso el predecesor es (6).

En cambio, para ubicar al sucesor (es decir, el menor elemento del subárbol derecho), se debe bajar al subárbol derecho y luego seguir bajando por las ramas izquierdas hasta llegar a un nodo que no tenga hijo izquierdo. En este caso el sucesor es (9).

En el ejemplo se eligió reemplazar la raíz con el predecesor y eliminar el nodo (6).

A continuación se presenta el algoritmo de eliminación de un nodo en un árbol binario de búsqueda:

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
FUNCION EliminarABB(raiz, valor)
    SI raiz ES nula ENTONCES
        RETORNAR nula
    SINO SI valor < raiz.valor ENTONCES
        raiz.izquierdo ← EliminarABB(raiz.izquierdo, valor)
    SINO SI valor > raiz.valor ENTONCES
        raiz.derecho ← EliminarABB(raiz.derecho, valor)
    SINO
        // Nodo encontrado
        SI raiz.izquierdo ES nula Y
           raiz.derecho ES nula ENTONCES
            // Caso 1: es una hoja
            RETORNAR nula
        SINO SI raiz.izquierdo ES nula ENTONCES
            // Caso 2: tiene solo hijo derecho
            RETORNAR raiz.derecho
        SINO SI raiz.derecho ES nula ENTONCES
            // Caso 2: tiene solo hijo izquierdo
            RETORNAR raiz.izquierdo
        SINO
            // Caso 3: tiene dos hijos,
            // se reemplaza por el predecesor
            predecesor ← BuscarMaximo(raiz.izquierdo)
            raiz.valor ← predecesor.valor
            raiz.izquierdo ← EliminarABB(
                raiz.izquierdo, predecesor.valor)
        FIN SI
    FIN SI
    RETORNAR raiz
FIN FUNCION

1
2
3
4
5
6
7
FUNCION BuscarMaximo(raiz)
    SI raiz.derecho ES nula ENTONCES
        RETORNAR raiz
    SINO
        RETORNAR BuscarMaximo(raiz.derecho)
    FIN SI
FIN FUNCION

1.4Árbol binario de búsqueda interactivo¶

Ingresar un valor y presionar Enter para ejecutar la operación seleccionada (insertar, buscar o eliminar). La animación avanza automáticamente paso a paso. Usar el control de velocidad para ajustar la rapidez de la animación.

1.5Orden de las operaciones¶

En un árbol binario de búsqueda, las operaciones de inserción, búsqueda y eliminación tienen un tiempo de ejecución que depende de la altura del árbol. Por lo tanto, es importante tratar de mantener el árbol equilibrado para que la altura no crezca demasiado.

Un árbol binario de búsqueda equilibrado tiene una altura aproximada de $O(log (n))$, donde $n$ es el número de nodos en el árbol. En este caso, las operaciones de inserción, búsqueda y eliminación tienen un tiempo de ejecución promedio de $O(log (n))$.

Formalmente la altura $h$ de un árbol binario de búsqueda se define como:

En la siguiente figura se observa un árbol binario de búsqueda completo (con todos los nodos en todos los niveles) y perfectamente balanceado, donde cada nodo tiene dos hijos y la altura del árbol es mínima. En este caso, el árbol tiene una altura de 3 y contiene 15 nodos.

La altura $h$ de un árbol binario completo y balanceado se puede calcular como:

Por otro lado, en el peor de los casos, un árbol binario de búsqueda puede degenerar en una lista enlazada, lo que resulta en una altura de $O(n)$ y un tiempo de ejecución de $O(n)$ para las operaciones. Esto ocurre cuando los nodos se insertan en orden ascendente o descendente, lo que provoca que el árbol se convierta en una estructura lineal. En la siguiente figura se observa un árbol binario que degeneró en una lista.

La altura $h$ de un árbol binario degenerado en una lista se puede calcular como:

2Implementación de un árbol binario de búsqueda¶

Existen dos enfoques principales para implementar un ABB: construir la estructura desde cero, definiendo explícitamente los nodos, o aprovechar una implementación de árbol binario genérica existente mediante composición. A continuación se analizan ambas alternativas.

En los ejemplos se utiliza una función de comparación func(T, T) int que permite trabajar con cualquier tipo de dato, sin restringir a cmp.Ordered. Esta función debe devolver un valor negativo si el primer argumento es menor, cero si son iguales, y positivo si es mayor.

2.1Implementación desde cero¶

Este enfoque consiste en definir un nodo binario que contenga el valor, el hijo izquierdo y el hijo derecho, y luego construir el ABB alrededor de ese nodo. Es la implementación más directa y no depende de ninguna otra estructura.

1
2
3
4
5
6
7
8
package binarysearchtree

// BinaryNode representa un nodo del árbol binario de búsqueda.
type BinaryNode[T any] struct {
    Value T
    Left  *BinaryNode[T]
    Right *BinaryNode[T]
}

1
2
3
4
5
6
7
8
9
10
11
12
package binarysearchtree

// BinarySearchTree representa un árbol binario de búsqueda.
type BinarySearchTree[T any] struct {
    Root *BinaryNode[T]
    cmp  func(T, T) int
}

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

El árbol posee una raíz que apunta al primer nodo. Las operaciones de inserción, búsqueda y eliminación se implementan como métodos recursivos que navegan por los nodos comparando valores. La lógica de ordenamiento está intrínsecamente ligada a la estructura del nodo.

Ventajas:

• Control total sobre la representación interna de los datos.

• Sin dependencias externas.

• Ideal para aprendizaje y comprensión del algoritmo.

Desventajas:

• Duplica lógica estructural que podría reutilizarse (recorridos, altura, etc.).

• Acopla la validación de la propiedad de orden con la estructura del árbol.

• Menor abstracción: cualquier cambio en la estructura del nodo impacta directamente en las operaciones del ABB.

Delegación de operaciones¶

En la implementación anterior las operaciones se manejan desde el árbol (bst.Insert, bst.Search, etc.), que delega en métodos privados recursivos. Una alternativa es delegar la lógica en los propios nodos:

1
2
3
4
5
6
7
8
9
10
11
func (n *BinaryNode[T]) Insert(value T, cmp func(T, T) int) *BinaryNode[T] {
    if n == nil {
        return &BinaryNode[T]{Value: value}
    }
    if cmp(value, n.Value) < 0 {
        n.Left = n.Left.Insert(value, cmp)
    } else if cmp(value, n.Value) > 0 {
        n.Right = n.Right.Insert(value, cmp)
    }
    return n
}

Delegar en los nodos hace que el árbol actúe solo como un envoltorio (bst.Root = bst.Root.Insert(value, bst.cmp)). La función de comparación se pasa como parámetro para que el nodo pueda decidir hacia dónde navegar. Esto acerca la implementación al paradigma de objetos donde cada nodo es responsable de su propia manipulación, pero puede dificultar el control de errores y la trazabilidad.

2.2Implementación por composición¶

El segundo enfoque consiste en construir el ABB a partir de una implementación genérica de árbol binario existente, como la que se encuentra en el paquete tree del repositorio data-structures. La idea es que el ABB contenga un árbol binario y le agregue la semántica de orden.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package binarysearchtree

import "github.com/untref-ayp2/data-structures/tree"

// BinarySearchTree representa un árbol binario de búsqueda
// construido sobre un árbol binario genérico.
type BinarySearchTree[T any] struct {
    binaryTree *tree.BinaryTree[T]
    cmp        func(T, T) int
}

// NewBinarySearchTree crea un ABB vacío con la función de comparación dada.
func NewBinarySearchTree[T any](cmp func(T, T) int) *BinarySearchTree[T] {
    return &BinarySearchTree[T]{
        binaryTree: tree.NewBinaryTree[T](),
        cmp:        cmp,
    }
}

En esta variante, el árbol binario subyacente provee las operaciones estructurales (insertar nodo, recorrer, calcular altura), mientras que el ABB se encarga únicamente de dónde insertar según el orden de los valores. La lógica de recorridos se hereda del árbol binario y no necesita reimplementarse.

Ventajas:

• Reutilización de código: los recorridos y la gestión estructural del árbol binario ya están implementados.

• Separación de responsabilidades: el árbol binario maneja cómo se almacenan los nodos; el ABB maneja dónde van según el orden.

• Menor cantidad de código que mantener y testear.

• Mayor abstracción: si cambia la implementación interna del árbol binario, el ABB no se ve afectado.

Desventajas:

• Dependencia de una biblioteca externa.

• Menor control sobre la representación interna.

• Curva de aprendizaje adicional si no se conoce la API del árbol binario subyacente.

• Puede introducir overhead si la interfaz genérica no se ajusta perfectamente a las necesidades del ABB.

2.3Comparación¶

3Ejercicios¶

Los ejercicios de este capítulo están en 09-abb/ejercicios/ del repositorio taller-tad.

Antes de comenzar, asegurate de tener implementadas las estructuras necesarias en data-structures, que está dentro del repositorio taller-tad. Ambas tareas se trabajan en paralelo: primero completás las implementaciones en data-structures y después las usás acá.