Árboles binarios de búsqueda

Un array ordenado busca en O(log n) con búsqueda binaria… pero insertar en él es O(n) — hay que desplazar. Una tabla hash inserta en O(1)… pero pierde el orden. El árbol binario de búsqueda (BST) es la estructura que se niega a elegir: mantiene los datos ordenados y admite buscar, insertar y borrar en O(log n).

La invariante que lo es todo

Un árbol binario es una jerarquía donde cada nodo tiene como mucho dos hijos. Lo que lo convierte en árbol de búsqueda es una regla global:

Todo lo que cuelga a la izquierda de un nodo es menor; todo lo que cuelga a la derecha, mayor.

¿Te suena la mecánica? Un BST es la búsqueda binaria convertida en estructura: en lugar de calcular el medio de un array, el “medio” ya está materializado como raíz de cada subárbol.

Buscar e insertar

La invariante hace que ambas operaciones sean una caminata guiada — y la definición recursiva del árbol (cada hijo es raíz de su propio subárbol) hace natural escribirlas con recursión:

interface Nodo {
  valor: number;
  izq: Nodo | null;
  der: Nodo | null;
}

function buscar(nodo: Nodo | null, x: number): boolean {
  if (nodo === null) return false; // caso base: rama agotada
  if (x === nodo.valor) return true;
  return x < nodo.valor ? buscar(nodo.izq, x) : buscar(nodo.der, x);
}

function insertar(nodo: Nodo | null, x: number): Nodo {
  if (nodo === null) return { valor: x, izq: null, der: null };
  if (x < nodo.valor) nodo.izq = insertar(nodo.izq, x);
  else if (x > nodo.valor) nodo.der = insertar(nodo.der, x);
  return nodo; // duplicados: ignorados en esta versión
}

El coste de ambas es O(altura) — y ahí está la letra pequeña del BST.

El árbol degenerado: la trampa del O(log n)

O(altura) solo es O(log n) si el árbol está equilibrado. Inserta 1, 2, 3, 4, 5 en orden y mira lo que construyes: cada valor va a la derecha del anterior. El “árbol” es una lista enlazada inclinada, altura n, y toda operación cae a O(n).

Recorridos: cuatro maneras de visitar todo

• Inorden (izquierda → nodo → derecha): visita los valores en orden ascendente. Es el superpoder del BST — “dame todo ordenado” sale gratis.
• Preorden (nodo → hijos): útil para copiar o serializar el árbol.
• Postorden (hijos → nodo): útil para liberar/borrar (los hijos antes que el padre).
• Por niveles (BFS): con una cola, visita nivel a nivel — la base de “imprimir el árbol por plantas”.

function inorden(nodo: Nodo | null, visita: (v: number) => void): void {
  if (nodo === null) return;
  inorden(nodo.izq, visita);
  visita(nodo.valor);
  inorden(nodo.der, visita);
}
// Sobre el árbol del diagrama: 1, 3, 6, 8, 10, 12, 14 — ordenado ✓

Un truco de entrevista que sale de aquí: verificar si un árbol es un BST válido = comprobar que su recorrido inorden sale ordenado.

Árboles más allá del BST

La forma jerárquica aparece en cuanto miras alrededor: el DOM de esta página, el sistema de ficheros, el JSON que parsea tu API, el árbol de sintaxis que tu compilador construye con cada build. No todos son de búsqueda — pero todos se recorren con las mismas cuatro estrategias que acabas de aprender, y esa es la habilidad transferible.