Árboles Binarios de Búsqueda (BST)

¿Qué es un BST?

Un Árbol Binario de Búsqueda (Binary Search Tree) es un árbol binario donde para cada nodo:

• Todos los valores en el subárbol izquierdo son menores
• Todos los valores en el subárbol derecho son mayores

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

Propiedad BST:
- Izquierda de 8: {1, 3, 4, 6, 7} (todos < 8)
- Derecha de 8: {10, 13, 14} (todos > 8)

Operaciones y complejidad

⚠️ El peor caso ocurre cuando el árbol está degenerado (parece una lista).

Estructura del nodo

struct Nodo {
    int valor;
    Nodo* izquierdo;
    Nodo* derecho;

    Nodo(int v) : valor(v), izquierdo(nullptr), derecho(nullptr) {}
};

Operaciones básicas

Búsqueda

Nodo* buscar(Nodo* raiz, int valor) {
    if (raiz == nullptr || raiz->valor == valor) {
        return raiz;
    }

    if (valor < raiz->valor) {
        return buscar(raiz->izquierdo, valor);
    } else {
        return buscar(raiz->derecho, valor);
    }
}

// Versión iterativa
Nodo* buscarIterativo(Nodo* raiz, int valor) {
    while (raiz != nullptr && raiz->valor != valor) {
        if (valor < raiz->valor) {
            raiz = raiz->izquierdo;
        } else {
            raiz = raiz->derecho;
        }
    }
    return raiz;
}

Inserción

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

    if (valor < raiz->valor) {
        raiz->izquierdo = insertar(raiz->izquierdo, valor);
    } else if (valor > raiz->valor) {
        raiz->derecho = insertar(raiz->derecho, valor);
    }
    // Si valor == raiz->valor, no hacemos nada (sin duplicados)

    return raiz;
}

Mínimo y Máximo

Nodo* minimo(Nodo* raiz) {
    if (raiz == nullptr) return nullptr;

    while (raiz->izquierdo != nullptr) {
        raiz = raiz->izquierdo;
    }
    return raiz;
}

Nodo* maximo(Nodo* raiz) {
    if (raiz == nullptr) return nullptr;

    while (raiz->derecho != nullptr) {
        raiz = raiz->derecho;
    }
    return raiz;
}

Eliminación

La eliminación tiene tres casos:

Nodo* eliminar(Nodo* raiz, int valor) {
    if (raiz == nullptr) return nullptr;

    if (valor < raiz->valor) {
        raiz->izquierdo = eliminar(raiz->izquierdo, valor);
    } else if (valor > raiz->valor) {
        raiz->derecho = eliminar(raiz->derecho, valor);
    } else {
        // Encontramos el nodo a eliminar

        // Caso 1: Hoja (sin hijos)
        if (raiz->izquierdo == nullptr && raiz->derecho == nullptr) {
            delete raiz;
            return nullptr;
        }

        // Caso 2: Un solo hijo
        if (raiz->izquierdo == nullptr) {
            Nodo* temp = raiz->derecho;
            delete raiz;
            return temp;
        }
        if (raiz->derecho == nullptr) {
            Nodo* temp = raiz->izquierdo;
            delete raiz;
            return temp;
        }

        // Caso 3: Dos hijos
        // Reemplazar con el sucesor inorder (mínimo del subárbol derecho)
        Nodo* sucesor = minimo(raiz->derecho);
        raiz->valor = sucesor->valor;
        raiz->derecho = eliminar(raiz->derecho, sucesor->valor);
    }

    return raiz;
}

Visualización de eliminación

Eliminar 3:

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

Caso 3: 3 tiene dos hijos
→ Reemplazar con sucesor (4)
→ Eliminar 4 de su posición original

Recorrido Inorder = Ordenado

Una propiedad fundamental: el recorrido inorder de un BST produce los elementos ordenados:

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

    inorder(raiz->izquierdo);
    cout << raiz->valor << " ";
    inorder(raiz->derecho);
}

// Para el árbol de ejemplo: 1, 3, 4, 6, 7, 8, 10, 13, 14

Sucesor y Predecesor

Sucesor Inorder

El menor valor mayor que el dado:

Nodo* sucesor(Nodo* raiz, int valor) {
    Nodo* sucesor = nullptr;
    Nodo* actual = raiz;

    while (actual != nullptr) {
        if (valor < actual->valor) {
            sucesor = actual;  // Posible sucesor
            actual = actual->izquierdo;
        } else {
            actual = actual->derecho;
        }
    }

    return sucesor;
}

Predecesor Inorder

El mayor valor menor que el dado:

Nodo* predecesor(Nodo* raiz, int valor) {
    Nodo* predecesor = nullptr;
    Nodo* actual = raiz;

    while (actual != nullptr) {
        if (valor > actual->valor) {
            predecesor = actual;
            actual = actual->derecho;
        } else {
            actual = actual->izquierdo;
        }
    }

    return predecesor;
}

Validar si es BST

bool esBSTUtil(Nodo* nodo, long long minVal, long long maxVal) {
    if (nodo == nullptr) return true;

    if (nodo->valor <= minVal || nodo->valor >= maxVal) {
        return false;
    }

    return esBSTUtil(nodo->izquierdo, minVal, nodo->valor) &&
           esBSTUtil(nodo->derecho, nodo->valor, maxVal);
}

bool esBST(Nodo* raiz) {
    return esBSTUtil(raiz, LLONG_MIN, LLONG_MAX);
}

Operaciones adicionales

K-ésimo elemento más pequeño

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

    // Buscar en subárbol izquierdo
    int izq = kEsimo(raiz->izquierdo, k);
    if (izq != -1) return izq;

    // Verificar nodo actual
    k--;
    if (k == 0) return raiz->valor;

    // Buscar en subárbol derecho
    return kEsimo(raiz->derecho, k);
}

// Uso
int k = 3;
int resultado = kEsimo(raiz, k);  // 3er elemento más pequeño

Contar nodos en rango [lo, hi]

int contarEnRango(Nodo* raiz, int lo, int hi) {
    if (raiz == nullptr) return 0;

    if (raiz->valor < lo) {
        return contarEnRango(raiz->derecho, lo, hi);
    }

    if (raiz->valor > hi) {
        return contarEnRango(raiz->izquierdo, lo, hi);
    }

    return 1 + contarEnRango(raiz->izquierdo, lo, hi) +
               contarEnRango(raiz->derecho, lo, hi);
}

LCA (Lowest Common Ancestor)

Nodo* lca(Nodo* raiz, int p, int q) {
    if (raiz == nullptr) return nullptr;

    if (p < raiz->valor && q < raiz->valor) {
        return lca(raiz->izquierdo, p, q);
    }

    if (p > raiz->valor && q > raiz->valor) {
        return lca(raiz->derecho, p, q);
    }

    return raiz;  // p y q están en diferentes lados
}

Usando set/map de STL

En competencias, set y map de C++ son BST balanceados (red-black trees):

#include <set>
#include <map>

int main() {
    set<int> s;

    s.insert(5);
    s.insert(3);
    s.insert(8);
    s.insert(1);

    // Iteración en orden
    for (int x : s) {
        cout << x << " ";  // 1 3 5 8
    }

    // Búsqueda O(log n)
    if (s.count(3)) {
        cout << "3 existe" << endl;
    }

    // Lower bound: primer elemento >= x
    auto it = s.lower_bound(4);  // Apunta a 5

    // Upper bound: primer elemento > x
    auto it2 = s.upper_bound(3);  // Apunta a 5

    // Mínimo y máximo
    cout << *s.begin() << endl;   // 1 (mínimo)
    cout << *s.rbegin() << endl;  // 8 (máximo)

    // Eliminar
    s.erase(5);

    return 0;
}

multiset (permite duplicados)

multiset<int> ms;
ms.insert(5);
ms.insert(5);
ms.insert(5);

cout << ms.count(5) << endl;  // 3

ms.erase(ms.find(5));  // Eliminar UNA ocurrencia
cout << ms.count(5) << endl;  // 2

ms.erase(5);  // Eliminar TODAS las ocurrencias
cout << ms.count(5) << endl;  // 0

Clase BST completa

class BST {
private:
    Nodo* raiz;

    Nodo* insertarRec(Nodo* nodo, int valor) {
        if (nodo == nullptr) return new Nodo(valor);
        if (valor < nodo->valor) nodo->izquierdo = insertarRec(nodo->izquierdo, valor);
        else if (valor > nodo->valor) nodo->derecho = insertarRec(nodo->derecho, valor);
        return nodo;
    }

    Nodo* eliminarRec(Nodo* nodo, int valor) {
        if (nodo == nullptr) return nullptr;

        if (valor < nodo->valor) {
            nodo->izquierdo = eliminarRec(nodo->izquierdo, valor);
        } else if (valor > nodo->valor) {
            nodo->derecho = eliminarRec(nodo->derecho, valor);
        } else {
            if (nodo->izquierdo == nullptr) {
                Nodo* temp = nodo->derecho;
                delete nodo;
                return temp;
            }
            if (nodo->derecho == nullptr) {
                Nodo* temp = nodo->izquierdo;
                delete nodo;
                return temp;
            }
            Nodo* sucesor = nodo->derecho;
            while (sucesor->izquierdo) sucesor = sucesor->izquierdo;
            nodo->valor = sucesor->valor;
            nodo->derecho = eliminarRec(nodo->derecho, sucesor->valor);
        }
        return nodo;
    }

    void inorderRec(Nodo* nodo) {
        if (nodo == nullptr) return;
        inorderRec(nodo->izquierdo);
        cout << nodo->valor << " ";
        inorderRec(nodo->derecho);
    }

public:
    BST() : raiz(nullptr) {}

    void insertar(int valor) { raiz = insertarRec(raiz, valor); }
    void eliminar(int valor) { raiz = eliminarRec(raiz, valor); }

    bool buscar(int valor) {
        Nodo* actual = raiz;
        while (actual) {
            if (valor == actual->valor) return true;
            actual = valor < actual->valor ? actual->izquierdo : actual->derecho;
        }
        return false;
    }

    void imprimir() { inorderRec(raiz); cout << endl; }
};

int main() {
    BST arbol;
    arbol.insertar(8);
    arbol.insertar(3);
    arbol.insertar(10);
    arbol.insertar(1);
    arbol.insertar(6);

    arbol.imprimir();  // 1 3 6 8 10

    cout << arbol.buscar(6) << endl;  // 1 (true)

    arbol.eliminar(3);
    arbol.imprimir();  // 1 6 8 10

    return 0;
}

Resumen

💡 En competencias: Usa set y map de STL. Son BST balanceados con garantía de $O(\log n)$.

Ejercicios recomendados

1. LeetCode - Validate BST
2. LeetCode - Kth Smallest Element in BST
3. LeetCode - LCA of BST
4. LeetCode - Delete Node in BST
5. CSES - Distinct Numbers