Binary Search Tree: ordenar para encontrar mejor

Lic. Carlos Enrique Loria Beeche.

Sexto artículo técnico de la saga “Estructuras de datos: cuando la memoria se convierte en inteligencia”

Este artículo forma parte de la saga que inicié con Estructuras de datos: cuando la memoria se convierte en inteligencia, donde presenté las ocho estructuras de datos fundamentales que iremos recorriendo paso a paso.

En las entregas anteriores estudiamos el array, el estacionamiento numerado de la memoria, la linked list, la búsqueda del tesoro en la memoria, la stack, la pila y el recuerdo del último paso, la queue, la cola y la justicia del turno, y la hash table, encontrar sin buscar.

Ahora vamos a estudiar una estructura que introduce una idea muy poderosa: organizar los datos de tal manera que cada comparación nos ayude a descartar una parte del camino.

Se trata del binary search tree, o árbol binario de búsqueda.

Un árbol binario de búsqueda nos enseña que el orden no solo sirve para presentar mejor la información; también puede hacer que encontrarla sea mucho más rápido.

¿Qué es un binary search tree?

Un binary search tree, o árbol binario de búsqueda, es una estructura de datos formada por nodos organizados de forma jerárquica.

Cada nodo puede tener, como máximo, dos hijos:

Un hijo izquierdo.
Un hijo derecho.

La regla fundamental es sencilla:

Los valores menores que el nodo actual van hacia la izquierda.
Los valores mayores que el nodo actual van hacia la derecha.

Por ejemplo, imaginemos este árbol:

          50
        /    \
      30      70
     /  \    /  \
   20   40  60   80

El nodo raíz es 50. Los valores menores que 50 están a la izquierda. Los valores mayores que 50 están a la derecha.

Luego, esa misma regla se repite en cada subárbol. En el lado izquierdo, 20 es menor que 30, y 40 es mayor que 30. En el lado derecho, 60 es menor que 70, y 80 es mayor que 70.

Buscar comparando

La gran ventaja conceptual de un árbol binario de búsqueda es que no necesitamos recorrer todos los elementos para encontrar un valor.

Supongamos que queremos buscar el número 60 en este árbol:

          50
        /    \
      30      70
     /  \    /  \
   20   40  60   80

Empezamos en la raíz:

Comparamos 60 con 50. Como 60 es mayor que 50, vamos a la derecha.
Comparamos 60 con 70. Como 60 es menor que 70, vamos a la izquierda.
Encontramos 60.

No tuvimos que revisar 20, 30, 40 ni 80. Cada comparación nos ayudó a descartar una parte del árbol.

En un árbol binario de búsqueda, cada decisión reduce el camino posible.

Nodo raíz, hojas y subárboles

Para hablar de árboles, conviene conocer algunos términos básicos.

Raíz

La raíz es el primer nodo del árbol. Desde allí comienza la búsqueda.

          50   &lt;- raíz
        /    \
      30      70

Hijos

Los hijos son los nodos que dependen directamente de otro nodo.

          50
        /    \
      30      70

30 y 70 son hijos de 50

Padre

El padre es el nodo que está inmediatamente arriba de otro nodo.

50 es padre de 30 y 70

Hojas

Las hojas son nodos que no tienen hijos.

          50
        /    \
      30      70
     /  \    /  \
   20   40  60   80

20, 40, 60 y 80 son hojas

Subárbol

Un subárbol es una parte del árbol que también puede verse como un árbol más pequeño.

Por ejemplo, el lado derecho de 50 forma este subárbol:

      70
     /  \
   60    80

Inserción en un árbol binario de búsqueda

Insertar un nuevo valor consiste en comparar desde la raíz hasta encontrar el lugar correcto.

Supongamos que queremos insertar el valor 65 en este árbol:

          50
        /    \
      30      70
     /  \    /  \
   20   40  60   80

El proceso sería:

Comparamos 65 con 50. Como 65 es mayor, vamos a la derecha.
Comparamos 65 con 70. Como 65 es menor, vamos a la izquierda.
Comparamos 65 con 60. Como 65 es mayor, va a la derecha de 60.

El árbol queda así:

          50
        /    \
      30      70
     /  \    /  \
   20   40  60   80
             \
              65

La inserción respeta siempre la regla: menores a la izquierda, mayores a la derecha.

Recorridos del árbol

Un árbol puede recorrerse de varias maneras. Tres recorridos clásicos son:

In-order: izquierda, nodo, derecha.
Pre-order: nodo, izquierda, derecha.
Post-order: izquierda, derecha, nodo.

Recorrido in-order

En un árbol binario de búsqueda, el recorrido in-order devuelve los valores ordenados.

Para este árbol:

          50
        /    \
      30      70
     /  \    /  \
   20   40  60   80

El recorrido in-order produce:

20, 30, 40, 50, 60, 70, 80

Esto es muy importante: el árbol no solo permite buscar comparando, también permite recuperar los datos en orden.

Ventaja principal: búsqueda eficiente

Si el árbol está bien balanceado, buscar puede ser muy eficiente.

En un árbol balanceado, cada decisión descarta aproximadamente la mitad del camino restante.

Búsqueda promedio: O(log n)
Inserción promedio: O(log n)
Eliminación promedio: O(log n)

Esto lo hace más eficiente que recorrer una lista completa cuando la cantidad de datos crece.

La idea es similar a buscar una palabra en un diccionario o usar búsqueda binaria en una lista ordenada: cada comparación reduce el espacio de posibilidades.

El problema del árbol desbalanceado

La eficiencia de un árbol binario de búsqueda depende de su forma.

Si insertamos los valores en un orden favorable, el árbol puede quedar equilibrado:

          50
        /    \
      30      70
     /  \    /  \
   20   40  60   80

Pero si insertamos valores ya ordenados, el árbol puede degenerar en una especie de lista:

En ese caso, la búsqueda ya no descarta grandes partes del árbol. Debe avanzar nodo por nodo.

Peor caso: O(n)

Por eso existen árboles balanceados, como AVL, Red-Black Trees y otras variantes, que intentan mantener una forma equilibrada para conservar buen rendimiento.

Un árbol binario de búsqueda es poderoso cuando conserva equilibrio; si se desbalancea demasiado, puede perder gran parte de su ventaja.

Operaciones básicas de un binary search tree

Operación	Descripción	Costo promedio
buscar	Comparar desde la raíz y avanzar izquierda o derecha	O(log n)
insertar	Ubicar la posición correcta y agregar un nodo	O(log n)
eliminar	Quitar un nodo conservando la regla del árbol	O(log n)
recorrer in-order	Visitar los nodos en orden ascendente	O(n)
buscar mínimo	Ir siempre hacia la izquierda	O(log n)
buscar máximo	Ir siempre hacia la derecha	O(log n)

Estos costos promedio asumen que el árbol está razonablemente balanceado. Si el árbol se desbalancea, algunas operaciones pueden degradarse a O(n).

Ejemplo en C++

En C++, podemos implementar un árbol binario de búsqueda usando una estructura para cada nodo y punteros hacia los hijos izquierdo y derecho.

#include &lt;iostream&gt;
using namespace std;

struct Nodo {
    int valor;
    Nodo* izquierda;
    Nodo* derecha;

    Nodo(int v) {
        valor = v;
        izquierda = nullptr;
        derecha = nullptr;
    }
};

Nodo* insertar(Nodo* raiz, int valor) {
    if (raiz == nullptr) {
        return new Nodo(valor);
    }

    if (valor &lt; raiz-&gt;valor) {
        raiz-&gt;izquierda = insertar(raiz-&gt;izquierda, valor);
    } else if (valor &gt; raiz-&gt;valor) {
        raiz-&gt;derecha = insertar(raiz-&gt;derecha, valor);
    }

    return raiz;
}

bool buscar(Nodo* raiz, int valor) {
    if (raiz == nullptr) {
        return false;
    }

    if (valor == raiz-&gt;valor) {
        return true;
    }

    if (valor &lt; raiz-&gt;valor) {
        return buscar(raiz-&gt;izquierda, valor);
    }

    return buscar(raiz-&gt;derecha, valor);
}

void inOrden(Nodo* raiz) {
    if (raiz == nullptr) {
        return;
    }

    inOrden(raiz-&gt;izquierda);
    cout &lt;&lt; raiz-&gt;valor &lt;&lt; " ";
    inOrden(raiz-&gt;derecha);
}

int main() {
    Nodo* raiz = nullptr;

    raiz = insertar(raiz, 50);
    insertar(raiz, 30);
    insertar(raiz, 70);
    insertar(raiz, 20);
    insertar(raiz, 40);
    insertar(raiz, 60);
    insertar(raiz, 80);

    cout &lt;&lt; "Recorrido in-order: ";
    inOrden(raiz);
    cout &lt;&lt; endl;

    cout &lt;&lt; "Buscar 60: "
         &lt;&lt; (buscar(raiz, 60) ? "Encontrado" : "No encontrado")
         &lt;&lt; endl;

    return 0;
}

Este ejemplo inserta valores en el árbol, los recorre en orden y busca un valor específico.

Ejemplo en C#

En C#, podemos representar cada nodo mediante una clase con referencias al hijo izquierdo y al hijo derecho.

using System;

class Nodo
{
    public int Valor { get; set; }
    public Nodo? Izquierda { get; set; }
    public Nodo? Derecha { get; set; }

    public Nodo(int valor)
    {
        Valor = valor;
        Izquierda = null;
        Derecha = null;
    }
}

class ArbolBinarioBusqueda
{
    public Nodo? Raiz { get; private set; }

    public void Insertar(int valor)
    {
        Raiz = Insertar(Raiz, valor);
    }

    private Nodo Insertar(Nodo? nodo, int valor)
    {
        if (nodo == null)
        {
            return new Nodo(valor);
        }

        if (valor &lt; nodo.Valor)
        {
            nodo.Izquierda = Insertar(nodo.Izquierda, valor);
        }
        else if (valor &gt; nodo.Valor)
        {
            nodo.Derecha = Insertar(nodo.Derecha, valor);
        }

        return nodo;
    }

    public bool Buscar(int valor)
    {
        return Buscar(Raiz, valor);
    }

    private bool Buscar(Nodo? nodo, int valor)
    {
        if (nodo == null)
        {
            return false;
        }

        if (valor == nodo.Valor)
        {
            return true;
        }

        if (valor &lt; nodo.Valor)
        {
            return Buscar(nodo.Izquierda, valor);
        }

        return Buscar(nodo.Derecha, valor);
    }

    public void ImprimirInOrden()
    {
        ImprimirInOrden(Raiz);
        Console.WriteLine();
    }

    private void ImprimirInOrden(Nodo? nodo)
    {
        if (nodo == null)
        {
            return;
        }

        ImprimirInOrden(nodo.Izquierda);
        Console.Write(nodo.Valor + " ");
        ImprimirInOrden(nodo.Derecha);
    }
}

class Program
{
    static void Main()
    {
        ArbolBinarioBusqueda arbol = new ArbolBinarioBusqueda();

        arbol.Insertar(50);
        arbol.Insertar(30);
        arbol.Insertar(70);
        arbol.Insertar(20);
        arbol.Insertar(40);
        arbol.Insertar(60);
        arbol.Insertar(80);

        Console.Write("Recorrido in-order: ");
        arbol.ImprimirInOrden();

        Console.WriteLine("Buscar 60: " +
            (arbol.Buscar(60) ? "Encontrado" : "No encontrado"));
    }
}

El árbol mantiene la regla de colocar valores menores a la izquierda y mayores a la derecha. El recorrido in-order imprime los valores ordenados.

Ejemplo en Python

En Python podemos implementar un árbol binario de búsqueda usando una clase para los nodos y funciones recursivas para insertar, buscar y recorrer.

class Nodo:
    def __init__(self, valor):
        self.valor = valor
        self.izquierda = None
        self.derecha = None

def insertar(raiz, valor):
    if raiz is None:
        return Nodo(valor)

    if valor &lt; raiz.valor:
        raiz.izquierda = insertar(raiz.izquierda, valor)
    elif valor &gt; raiz.valor:
        raiz.derecha = insertar(raiz.derecha, valor)

    return raiz

def buscar(raiz, valor):
    if raiz is None:
        return False

    if valor == raiz.valor:
        return True

    if valor &lt; raiz.valor:
        return buscar(raiz.izquierda, valor)

    return buscar(raiz.derecha, valor)

def in_orden(raiz):
    if raiz is None:
        return

    in_orden(raiz.izquierda)
    print(raiz.valor, end=" ")
    in_orden(raiz.derecha)

raiz = None

for valor in [50, 30, 70, 20, 40, 60, 80]:
    raiz = insertar(raiz, valor)

print("Recorrido in-order:")
in_orden(raiz)

print("\nBuscar 60:", "Encontrado" if buscar(raiz, 60) else "No encontrado")

Este ejemplo muestra cómo insertar valores, recorrer el árbol en orden y buscar un elemento específico.

¿Cuándo conviene usar un binary search tree?

Un árbol binario de búsqueda puede convenir cuando necesitamos mantener datos ordenables y realizar búsquedas, inserciones o eliminaciones de forma eficiente.

Algunos casos típicos son:

Datos numéricos o comparables.
Conjuntos ordenados.
Diccionarios ordenados.
Índices que requieren recorrido ordenado.
Búsqueda de mínimos y máximos.
Rangos de valores.
Estructuras donde importa conservar orden.

Sin embargo, si solo queremos buscar por clave de la forma más rápida posible y no nos interesa el orden, una tabla hash puede ser mejor. Si necesitamos orden, rangos o recorrido ascendente, un árbol puede ser más apropiado.

Comparación rápida con hash table

La tabla hash y el árbol binario de búsqueda pueden usarse para buscar datos, pero lo hacen de manera distinta.

Estructura	Fortaleza principal	Limitación
Hash Table	Búsqueda muy rápida por clave	No mantiene orden natural
Binary Search Tree	Búsqueda ordenada y recorridos en orden	Puede degradarse si se desbalancea

La tabla hash pregunta: ¿a qué posición me lleva esta clave?

El árbol binario de búsqueda pregunta: ¿este valor es menor o mayor que el nodo actual?

Ambas estrategias son valiosas, pero responden a necesidades distintas.

Aplicaciones reales

Los árboles binarios de búsqueda y sus variantes aparecen en muchas áreas:

Índices ordenados.
Conjuntos ordenados.
Estructuras internas de bibliotecas estándar.
Búsqueda de rangos.
Compiladores.
Sistemas donde se requiere recorrer datos en orden.
Árboles balanceados usados en estructuras más avanzadas.

En la práctica, muchas bibliotecas modernas utilizan variantes balanceadas de árboles para garantizar buen rendimiento incluso cuando los datos llegan en órdenes poco favorables.

La lección del árbol binario de búsqueda

El árbol binario de búsqueda nos enseña que ordenar también es una forma de pensar.

El array nos enseñó el poder del índice. La lista enlazada nos enseñó el valor del enlace. La pila nos enseñó el valor del retorno. La cola nos enseñó el valor del turno. La tabla hash nos enseñó el poder de la clave. El árbol binario de búsqueda nos enseña el valor de comparar.

En lugar de caminar elemento por elemento, el árbol decide. Compara, descarta y avanza. Cada paso tiene una dirección.

Pero también nos recuerda una advertencia importante: no basta con tener estructura; hay que conservar el equilibrio.

El árbol binario de búsqueda nos recuerda que una buena decisión puede ahorrar muchos pasos, pero una mala organización puede convertir el camino en una simple fila disfrazada de árbol.

Próxima entrega

En el próximo artículo de esta saga estudiaremos el heap, una estructura basada en prioridades. Allí veremos por qué no siempre importa atender primero al que llegó primero, sino al que tiene mayor prioridad.

Pasaremos del orden para buscar al orden para priorizar.