🌲 Árboles Binarios de Búsqueda

init

Pruébalo: Inserta claves; buscar resalta el camino de comparación. Luego presiona rómpelo: insertar valores ordenados colapsa el árbol en una lista enlazada — la altura salta de log n a n.

Por qué importa

Los ABB (árboles binarios de búsqueda) combinan la búsqueda rápida de los arreglos con la inserción flexible de las listas enlazadas. Son la base de conjuntos, mapas y bases de datos. Entender los ABB es clave para entender los árboles balanceados y la búsqueda eficiente.

La idea

¿Recuerdas el juego de adivinar el número? "¿Es mayor o menor?" Cada respuesta elimina la mitad de las posibilidades.

Un ABB es ese juego en forma de árbol. Cada nodo sigue una regla: los hijos izquierdos son menores, los hijos derechos son mayores.

Para encontrar un valor:

1. Empieza en la raíz
2. Si el valor < nodo, ve a la izquierda. Si el valor > nodo, ve a la derecha.
3. Repite hasta encontrarlo o llegar a nulo.

Cada paso elimina la mitad del árbol — eso es O(log n)... si el árbol está balanceado. Si insertas datos ordenados, obtienes una lista enlazada y O(n). Por eso existen los árboles balanceados.

Puntos clave

• Subárbol izquierdo < nodo < subárbol derecho (propiedad del ABB)
• Buscar, insertar y eliminar son O(h) donde h es la altura
• Árbol balanceado: h = O(log n). Desbalanceado: h = O(n)
• El recorrido inorden produce una secuencia ordenada

El invariante del ABB

Toda operación sobre un ABB debe preservar una regla. Enúnciala una vez y podrás probar la correctitud de cada algoritmo verificando que la regla se cumple antes y después:

Invariante del ABB

Para cada nodo n: toda clave en el subárbol de n.left es estrictamente menor que n.key, y toda clave en el subárbol de n.right es estrictamente mayor.

Corolario — el recorrido inorden produce orden ordenado

Visita left recursivamente, luego self, luego right recursivamente. La llamada recursiva sobre left devuelve claves todas menores que self.key; la llamada sobre right devuelve claves todas mayores. Así que la concatenación está ordenada.

Qué significa "preservar" en la práctica

Toda inserción/eliminación debe terminar con el invariante aún verdadero en todas partes. Insertar es fácil — solo agregas en una hoja, así que la regla ya se cumple. Eliminar es el caso difícil; ver abajo.

Profundizando

Eliminación — los tres casos, paso a paso

Esta es la operación que hace que los ingenieros recurran a los árboles AVL o rojo-negro. Quitar un nodo preservando el invariante requiere cuidado.

Caso 1 — hoja. Simplemente desconéctala de su padre. El invariante se preserva trivialmente porque ningún otro nodo dependía de este.

    5                5
   / \              / \
  3   8     →      3
     /
    6           (eliminar 6 a la derecha de 3)

Un momento, ese ejemplo quita el 6 a la izquierda del 8 — el punto es: las hojas salen gratis.

Caso 2 — un hijo. Empalma el hijo hacia arriba, a la ranura del nodo eliminado. El padre del nodo eliminado ahora apunta al hijo; el subárbol del hijo ya cumplía el invariante, así que sigue cumpliéndolo en la nueva posición.

      5                5
     / \              / \
    3   8     →      3   6
        /
       6           (eliminar 8: solo tenía un hijo izquierdo, 6)

Caso 3 — dos hijos. No puedes simplemente promover a cualquiera de los hijos — ambos tienen sus propios subárboles que tendrías que fusionar de algún modo. El truco: encuentra el sucesor inorden — la clave más pequeña del subárbol derecho (equivalentemente, la hoja más a la izquierda de right). Copia su valor en el nodo eliminado, luego elimina ese sucesor del subárbol derecho (llamada recursiva, pero el sucesor en sí tiene a lo sumo un hijo, así que la recursión termina en el caso 1 o 2).

      5                6
     / \              / \
    3   8     →      3   8
       / \              / \
      6   9            7   9
       \
        7              (eliminar 5: el sucesor es 6;
                       copia 6 arriba, luego elimina el
                       6 original — caso 2 con hijo
                       derecho 7)

¿Por qué el sucesor y no el predecesor? Cualquiera de los dos funciona — el predecesor es la clave más grande del subárbol izquierdo. La mayoría de las implementaciones alternan o eligen uno y se mantienen consistentes. El invariante se preserva porque el sucesor era estrictamente mayor que todo lo del subárbol izquierdo (así que sigue siendo mayor tras la promoción) y estrictamente menor que todo lo demás del subárbol derecho (así que el subárbol derecho sigue siendo válido).

Por qué todo esto colapsa sin balance

El botón rómpelo de la demostración inserta valores ya ordenados. Cada nodo nuevo va a la posición más a la derecha — el árbol se convierte en una lista enlazada, la altura sube a n y la búsqueda se degrada a O(n). Esta es la motivación de la lección de árboles balanceados: los algoritmos de ahí reequilibran después de cada inserción y eliminación, de modo que la altura se mantiene en O(log n) sin importar en qué orden lleguen las entradas.

Detalles matemáticos

Complejidad temporal (altura h)

Search: O(h)

Insert: O(h)

Delete: O(h)

Min/Max: O(h)

Cotas de altura

Balanced: h = O(log n)

Unbalanced: h = O(n)

Implementación

Búsqueda en ABB

fn search(node: Option<&Box<BstNode>>, key: i32)
    -> bool
{
    match node {
        None => false,
        Some(n) => {
            if key < n.data {
                search(n.left.as_ref(), key)
            } else if key > n.data {
                search(n.right.as_ref(), key)
            } else {
                true  // ¡Encontrado!
            }
        }
    }
}

Casos de eliminación

• Hoja: Eliminar directamente
• Un hijo: Reemplazar con el hijo
• Dos hijos: Reemplazar con el sucesor

Práctica

Tres problemas construidos sobre el invariante del ABB:

• Validar un ABB — medio · por qué las comprobaciones locales no bastan; el patrón de la ventana (min, max)
• Ancestro común más bajo en un ABB — fácil · recorrido O(h) que explota el orden del ABB — sin estructura auxiliar
• K-ésimo más pequeño en un ABB — medio · inorden iterativo con una pila explícita; la plantilla detrás de todo cursor de índice ordenado

→ Explora todos los problemas de práctica