Árboles binarios de búsqueda

Un árbol binario no es automáticamente rápido para buscar. La ventaja aparece cuando cada nodo mantiene una regla: claves menores de un lado, mayores del otro. Esa regla permite descartar un subárbol entero en cada comparación.

La invariante que ordena el árbol

En un árbol binario de búsqueda, o ABB, todas las claves del subárbol izquierdo son menores que la clave del nodo y todas las del derecho son mayores. La condición vale recursivamente en cada subárbol.

Los duplicados requieren una política explícita: rechazarlos, contar repeticiones dentro del nodo o adaptar una desigualdad para ubicarlos siempre del mismo lado. Sin una regla consistente, búsqueda e inserción dejan de compartir la misma invariante.

Buscar es bajar por un camino

Para buscar una clave, empezamos en la raíz. Si coincide, terminamos. Si es menor, seguimos por la izquierda; si es mayor, por la derecha:

type BinaryNode<T> = {
  value: T;
  left: BinaryNode<T> | null;
  right: BinaryNode<T> | null;
};

const contains = (root: BinaryNode<number> | null, target: number): boolean => {
  let current = root;
  while (current) {
    if (target === current.value) return true;
    current = target < current.value ? current.left : current.right;
  }
  return false;
};

El costo es proporcional a la altura $h$: $O(h)$.

Insertar donde la búsqueda se queda sin lugar

Insertar sigue el mismo camino que buscar hasta encontrar un enlace vacío. Ahí conecta el nuevo nodo. La inserción local cuesta $O(1)$; encontrar su lugar cuesta $O(h)$.

Después de insertar, el recorrido inorden sigue ordenado. Esa es una prueba útil de la invariante, pero no alcanza para detectar todos los errores: también hay que verificar que cada subárbol respete límites heredados de sus ancestros.

Borrar, que tiene tres casos

Borrar tiene tres casos. Una hoja puede desconectarse. Un nodo con un solo hijo se reemplaza por ese hijo. Un nodo con dos hijos se reemplaza por su sucesor en inorden, el menor del subárbol derecho, y luego se elimina ese sucesor de su posición original.

El tercer caso no copia un hijo arbitrario: debe elegir una clave que conserve todas las desigualdades a ambos lados.

Todo depende de la altura

Si el árbol está razonablemente balanceado, $h$ es $O(\log n)$ y las operaciones son logarítmicas. Si insertamos claves ya ordenadas en un ABB común, cada nodo puede quedar como hijo derecho del anterior. La estructura se convierte en una lista y $h=n$.

Por eso decir que un ABB busca en $O(\log n)$ necesita una condición sobre su forma. Sin balanceo, el peor caso es $O(n)$.

Cuándo un ABB y cuándo otra cosa

La pregunta que decide es si el orden importa. «Dame los pedidos de esta semana», «cuál es el próximo turno después de las 14», «los diez productos más caros»: las tres necesitan orden, y una tabla hash no puede contestarlas sin mirar todo. Si en cambio la única pregunta es «dame el usuario con este identificador», el árbol está pagando $O(\log n)$ por una capacidad que nadie usa.

Cierre

El ABB convierte comparaciones en decisiones de izquierda o derecha. Buscar, insertar y borrar cuestan $O(h)$, no automáticamente $O(\log n)$. La invariante mantiene el orden; un mecanismo adicional de balanceo es el que controla la altura.