Árboles de Búsqueda Binaria (BST)

¿Qué es un BST?

Un Árbol de Búsqueda Binaria (Binary Search Tree) es un árbol binario donde:

• Todo nodo en el subárbol izquierdo tiene un valor menor que la raíz.
• Todo nodo en el subárbol derecho tiene un valor mayor que la raíz.

        8
       / \
      3   10
     / \    \
    1   6   14
       / \  /
      4  7 13

Analogía: Es como un árbol de decisiones: en cada nodo preguntas "¿es menor o mayor?" e vas a la izquierda o derecha.

¿Por qué es útil?

Buscar, insertar y eliminar son $O(h)$ donde $h$ es la altura. En un árbol balanceado, $h = O(\log n)$.

Implementación básica

struct Nodo {
    int valor;
    Nodo* izq;
    Nodo* der;
    Nodo(int v) : valor(v), izq(nullptr), der(nullptr) {}
};

// Insertar
Nodo* insertar(Nodo* raiz, int val) {
    if (raiz == nullptr) return new Nodo(val);

    if (val < raiz->valor) {
        raiz->izq = insertar(raiz->izq, val);
    } else if (val > raiz->valor) {
        raiz->der = insertar(raiz->der, val);
    }
    // Si val == raiz->valor, no insertar (sin duplicados)

    return raiz;
}

// Buscar
bool buscar(Nodo* raiz, int val) {
    if (raiz == nullptr) return false;
    if (val == raiz->valor) return true;
    if (val < raiz->valor) return buscar(raiz->izq, val);
    return buscar(raiz->der, val);
}

// Encontrar el mínimo
Nodo* minimo(Nodo* raiz) {
    while (raiz->izq != nullptr) {
        raiz = raiz->izq;
    }
    return raiz;
}

// Eliminar
Nodo* eliminar(Nodo* raiz, int val) {
    if (raiz == nullptr) return nullptr;

    if (val < raiz->valor) {
        raiz->izq = eliminar(raiz->izq, val);
    } else if (val > raiz->valor) {
        raiz->der = eliminar(raiz->der, val);
    } else {
        // Caso 1: Hoja
        if (raiz->izq == nullptr && raiz->der == nullptr) {
            delete raiz;
            return nullptr;
        }
        // Caso 2: Un hijo
        if (raiz->izq == nullptr) {
            Nodo* temp = raiz->der;
            delete raiz;
            return temp;
        }
        if (raiz->der == nullptr) {
            Nodo* temp = raiz->izq;
            delete raiz;
            return temp;
        }
        // Caso 3: Dos hijos - reemplazar con el sucesor inorden
        Nodo* suc = minimo(raiz->der);
        raiz->valor = suc->valor;
        raiz->der = eliminar(raiz->der, suc->valor);
    }

    return raiz;
}

Propiedad del inorden

Si recorres un BST en inorden (izquierda → nodo → derecha), obtienes los valores ordenados:

void inorden(Nodo* raiz) {
    if (raiz == nullptr) return;
    inorden(raiz->izq);
    cout << raiz->valor << " ";
    inorden(raiz->der);
}
// Para el ejemplo: 1 3 4 6 7 8 10 13 14

El problema del desbalanceo

Si insertas elementos en orden (1, 2, 3, 4, 5), el BST degenera en una lista:

1
 \
  2
   \
    3
     \
      4
       \
        5

Altura = $n$, y todas las operaciones son $O(n)$. Solución: usar árboles autobalanceados (AVL, Red-Black) o simplemente std::set de C++.

En la práctica: usa std::set

std::set en C++ es un BST autobalanceado (Red-Black Tree):

#include <set>
using namespace std;

set<int> s;
s.insert(8);
s.insert(3);
s.insert(10);

s.count(3);        // 1 (existe)
s.erase(3);        // Eliminar
*s.begin();        // Mínimo
*s.rbegin();       // Máximo
s.lower_bound(5);  // Primer elemento >= 5

Todas las operaciones son $O(\log n)$ garantizado.

K-ésimo elemento más pequeño

int kesimo(Nodo* raiz, int &k) {
    if (raiz == nullptr) return -1;

    int resultado = kesimo(raiz->izq, k);
    if (k == 0) return resultado;

    k--;
    if (k == 0) return raiz->valor;

    return kesimo(raiz->der, k);
}

Ejercicio de práctica

Inserta N números en un BST e imprime el recorrido inorden (que debería ser la secuencia ordenada).

#include <iostream>
using namespace std;

struct Nodo {
    int val;
    Nodo *izq, *der;
    Nodo(int v) : val(v), izq(nullptr), der(nullptr) {}
};

Nodo* insertar(Nodo* r, int v) {
    if (!r) return new Nodo(v);
    if (v < r->val) r->izq = insertar(r->izq, v);
    else if (v > r->val) r->der = insertar(r->der, v);
    return r;
}

void inorden(Nodo* r) {
    if (!r) return;
    inorden(r->izq);
    cout << r->val << " ";
    inorden(r->der);
}

int main() {
    int n;
    cin >> n;

    Nodo* raiz = nullptr;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        raiz = insertar(raiz, x);
    }

    inorden(raiz);
    cout << endl;

    return 0;
}