GUÍA 02-11-26 Estructuras de Datos

CN122 · lunes 02/11/2026 · 13:00-14:15 · Sesión 24

Árboles binarios de búsqueda

LA PROPIEDAD

Un árbol binario de búsqueda cumple, en todo nodo, que las claves del subárbol izquierdo son menores y las del derecho mayores. Esa invariante es lo que permite descartar la mitad del árbol en cada comparación.

BÚSQUEDA

1. Comparar con la raíz.

2. Si es igual, se encontró.

3. Si es menor, bajar a la izquierda; si es mayor, a la derecha.

4. Si se llega a NULL, no está.

El costo es la altura del árbol: O(log n) si está balanceado, O(n) si está degenerado.

EL PROBLEMA DE LA DEGENERACIÓN

Insertar claves ya ordenadas produce un árbol que es una lista: cada nodo tiene un solo hijo. La búsqueda se vuelve secuencial y se pierde toda la ventaja.

Ese es el caso peor y no es raro: cargar datos ordenados es lo más natural del mundo. Por eso existen los árboles balanceados —AVL, rojinegro, B— que reacomodan al insertar.

INSERCIÓN

Se busca la posición y se enlaza como hoja. Nunca se inserta en medio: la estructura del árbol depende del orden de llegada.

ELIMINACIÓN: TRES CASOS

• Hoja — se elimina directamente.
• Un hijo — el hijo ocupa su lugar.
• Dos hijos — se reemplaza por su sucesor en orden (el mínimo del subárbol derecho) y se elimina ese sucesor, que a lo sumo tiene un hijo.

El tercer caso es el único delicado y es el que se pregunta en el examen. Vale la pena hacerlo a mano varias veces antes de programarlo.

PRÁCTICA

Implementar inserción, búsqueda y los tres casos de eliminación; construir un árbol con datos ordenados y observar la degeneración.