GUÍA 09-11-26 Estructuras de Datos

CN122 · lunes 09/11/2026 · 13:00-14:15 · Sesión 26

Recorridos iterativos · Árboles balanceados

RECORRIDOS SIN RECURSIÓN

La recursión usa la pila del sistema. Hacerlo con una pila explícita permite controlar la memoria y evita el desbordamiento en árboles muy profundos.

PREORDEN ITERATIVO

1. Apilar la raíz.

2. Mientras la pila no esté vacía: desapilar, visitar.

3. Apilar el hijo derecho y luego el izquierdo.

El derecho se apila primero para que el izquierdo salga antes, que es lo que el preorden exige.

INORDEN ITERATIVO

Se baja por la izquierda apilando todo el camino; al llegar a NULL se desapila, se visita y se pasa al subárbol derecho. Es el más útil de los tres porque produce las claves ordenadas.

LA NECESIDAD DEL BALANCEO

Un ABB solo garantiza O(log n) si su altura es logarítmica, y eso depende del orden de inserción. Los árboles balanceados reacomodan automáticamente para garantizar la altura.

ÁRBOLES AVL

• Se exige que en todo nodo las alturas de los subárboles difieran a lo sumo en 1.
• Al insertar o eliminar se restaura la propiedad con rotaciones simples o dobles.
• Garantizan altura O(log n) y por tanto búsqueda, inserción y eliminación en O(log n).

ROTACIONES

Una rotación reacomoda tres nodos cambiando algunos enlaces, sin alterar el orden inorden. Los cuatro casos —izquierda-izquierda, derecha-derecha, izquierda-derecha, derecha-izquierda— se reducen a rotación simple o doble.

PRÁCTICA

Implementar los recorridos iterativos y las rotaciones simples de un AVL.