Taller de Árboles AVL

Plan para esta noche

Parcial a las 10:00. Lo más valioso es repetir rotaciones hasta que salgan sin pensar, y luego el código.

22:45–23:15

Esta guía: la receta AVL y la regla del medio.

23:15–00:30

Rotaciones rápidas → Inserción hasta acertar 10 seguidas.

00:30–01:15

Rotaciones rápidas → Eliminación (con predecesor).

01:15–02:15

Parcial simulado completo, a mano en papel, y la página le corrige.

02:15–02:30

Descanso. Agua, estirarse.

02:30–04:30

Python: ejercicios 1 a 10. Escriba cada uno en papel antes de llenarlo.

04:30–05:15

Tuplas con prioridad (el punto 2 del parcial).

05:15–05:45

2-3 y Rojo-Negro: solo las reglas y la inserción.

05:45–08:15

Dormir. Aunque sean 2 horas: mientras duerme, el cerebro fija lo que practicó.

08:15–09:00

Un último parcial simulado + releer esta guía.

BST en un minuto

En cada nodo: todo lo de la izquierda es menor, todo lo de la derecha es mayor. Se inserta bajando desde la raíz (menor → izquierda, mayor → derecha) hasta encontrar un hueco.

Eliminar: tres casos

Hoja: se quita y listo.
Un hijo: el hijo sube a ocupar su lugar.
Dos hijos: se reemplaza por su predecesor = el mayor del subárbol izquierdo. Para encontrarlo: un paso a la izquierda, y luego todo a la derecha hasta que no se pueda más. Ese predecesor se quita de donde estaba (allí siempre es hoja o tiene un solo hijo, a la izquierda).

Medidas del árbol (raíz en nivel 0)

Medida	Qué es	Ejemplo (árbol de abajo)

Si el profe cuenta la altura en nodos (y no en aristas), es la misma más 1. Con raíz = nivel 0, lo normal es contar aristas: una hoja tiene altura 0.

AVL: la receta mecánica

FB (factor de balance) = altura(izquierda) − altura(derecha). Árbol vacío = −1, hoja = 0. Un AVL está bien si todos los nodos tienen FB −1, 0 o +1.

Inserte el número como en un BST normal.
Suba desde el nodo nuevo hacia la raíz recalculando FB. El primer nodo con FB +2 o −2 que encuentre es el pivote (el más profundo desbalanceado). En inserción solo se arregla ese y el resto se arregla solo.

Desde el pivote, mire los dos primeros pasos del camino hacia el nodo nuevo:

Camino	Caso	Qué se hace
izquierda, izquierda	`LL`	Una rotación a la derecha sobre el pivote
derecha, derecha	`RR`	Una rotación a la izquierda sobre el pivote
izquierda, derecha	`LR`	Izquierda sobre el hijo, luego derecha sobre el pivote
derecha, izquierda	`RL`	Derecha sobre el hijo, luego izquierda sobre el pivote

Línea recta = 1 rotación. Zig-zag = 2 rotaciones.

Rote y verifique que todos los FB quedaron en −1, 0 o +1.

Los nombres cambian según el profe: a LL algunos le dicen "rotación simple a la derecha" o "II". Lo que importa es la forma.

Regla del medio (el truco para hacerlo a mano sin perderse). Tome los 3 nodos del camino: pivote, hijo y nieto. Ordénelos por valor: a < b < c. El del medio (b) queda arriba, a a su izquierda y c a su derecha. Los subárboles que colgaban de esos tres (máximo 4) se cuelgan de nuevo en orden de izquierda a derecha: T1 y T2 bajo a, T3 y T4 bajo c. Funciona igual para los 4 casos.

Los 4 casos, con el ejemplo más pequeño

Eliminar en AVL

Elimine como en BST (hoja / un hijo / predecesor).
Suba desde el padre del nodo que se quitó físicamente hasta la raíz, revisando FB.
Si un nodo queda en ±2, el hijo que se mira es el del lado más alto (el lado contrario de donde se borró). Si ese hijo tiene FB 0, se trata como línea recta: rotación simple.
No pare después de la primera rotación. En eliminación puede haber más de una: siga subiendo hasta la raíz.

Errores típicos

Escoger como pivote la raíz cuando el desbalanceado más profundo está más abajo.
En LR o RL hacer solo una rotación.
Perder el subárbol del medio (T2 o T3) al rotar: siempre se reubica, nunca desaparece.
Usar el sucesor en vez del predecesor.
En eliminación, detenerse tras la primera rotación.
En la serie: listar mal un término (revise dos veces; un número malo daña todo el árbol).

Rotaciones rápidas

Árboles pequeños al azar. En Hacerlo yo: ponga el nodo en su hueco y rote arrastrando un nodo encima de su padre. En Elegir respuesta: diga qué rotación toca (Enter revisa).

Taller libre

Inserte números uno por uno. Usted escoge el hueco donde va cada uno y hace las rotaciones arrastrando nodos. La página le dice si quedó un AVL válido.

Recorridos y medidas del árbol actual

De palabras a fórmula

Casi toda serie es una base + algo que le hacen. "Los primos más 1" → base pₙ, le hacen + 1 → aₙ = pₙ + 1, n ≥ 1.

Subraye el sustantivo (primos, pares, cuadrados…). Esa es la base: tabla 1.
Subraye lo que le hacen (más, menos, el doble, signo alternado…): tabla 2.
Escriba aₙ = (lo que le hacen aplicado a la base), n ≥ 1.
Verifique: reemplace n = 1, 2, 3 y mire que dé lo que dice la frase.

Tabla 1 · Bases

Si dice…	Escriba	Da
los naturales	n	1, 2, 3, 4
los pares	2n	2, 4, 6, 8
los impares	2n − 1	1, 3, 5, 7
los múltiplos de 5	5n	5, 10, 15, 20
los cuadrados (perfectos)	n²	1, 4, 9, 16
los cubos	n³	1, 8, 27, 64
los primos	pₙ (el n-ésimo primo)	2, 3, 5, 7, 11
las potencias de 2	2ⁿ	2, 4, 8, 16
los triangulares	n(n + 1)/2	1, 3, 6, 10
los factoriales	n!	1, 2, 6, 24
Fibonacci	a₁ = 1, a₂ = 1, aₙ = aₙ₋₁ + aₙ₋₂	1, 1, 2, 3, 5

Tabla 2 · Lo que le hacen (X = la base)

Si dice…	Escriba	Ejemplo
más 3	X + 3	pₙ + 3
menos 1	X − 1	n² − 1
el doble de	2·X	2·(2n − 1)
la mitad de	X / 2	2ⁿ / 2
al cuadrado	X²	(2n − 1)²
100 menos…	100 − X	100 − 5n
signo alternado, empieza negativo	(−1)ⁿ · X	−1, 2, −3, 4
signo alternado, empieza positivo	(−1)ⁿ⁺¹ · X	1, −2, 3, −4
el residuo de dividir X entre 7	X mod 7	n² mod 7
cada término es … del anterior	a₁ = …, aₙ = … aₙ₋₁	a₁ = 3, aₙ = 2·aₙ₋₁

Paréntesis: si la base tiene un + o un − adentro (como 2n − 1) y le hace algo encima (cuadrado, doble, restarla), enciérrela: (2n − 1)², 100 − (2n − 1).
Signo alternado: (−1)ⁿ con n = 1 da −1, así que empieza negativo. Si debe empezar positivo, súmele 1 al exponente: (−1)ⁿ⁺¹.
"El anterior": si la frase habla del término anterior, la fórmula es recursiva: se da a₁ y la regla usa aₙ₋₁.

Cinco ejemplos resueltos

Frase	Base → le hacen	Fórmula	Verificación
Todos los primos más 1	pₙ → + 1	aₙ = pₙ + 1, n ≥ 1	3, 4, 6, 8, 12
Los impares al cuadrado	2n − 1 → ²	aₙ = (2n − 1)², n ≥ 1	1, 9, 25, 49
Cien menos los múltiplos de 5	5n → 100 −	aₙ = 100 − 5n, n ≥ 1	95, 90, 85
Los naturales con signo alternado, empezando en negativo	n → (−1)ⁿ ·	aₙ = (−1)ⁿ · n, n ≥ 1	−1, 2, −3, 4
Cada término es el doble del anterior, empezando en 3	recursiva	a₁ = 3, aₙ = 2·aₙ₋₁, n ≥ 2	3, 6, 12, 24

También vale escribirlo como conjunto: { p + 1 : p es primo }. Pero la forma aₙ = … es mejor, porque con ella puede listar "hasta n = 15" directamente.

Práctica

Lea la frase, escoja la fórmula y escriba los primeros 6 términos. Enter revisa y pasa a la siguiente.

Parcial simulado: punto 1

Serie en palabras → fórmula → lista → insertar en AVL → eliminar 3 nodos (predecesor) → recorridos y medidas. Hágalo en papel y vaya digitando.

Python mínimo para árboles

Solo lo que necesita para escribir un árbol en papel. Lo de la izquierda es lo que usted ya conoce de otros lenguajes.

Lo que más se olvida: los dos puntos : al final de if, def, class, while, for, else; y la sangría (4 espacios) que reemplaza las llaves { }.

Escribir desde cero

Como en el parcial: hoja en blanco. Escríbalo primero en papel, luego aquí, y presione Revisar. La página revisa los errores típicos de sintaxis y los puntos clave, y le muestra la solución al lado. Lo que escriba se guarda en este navegador.

Su código

Tab = 4 espacios · Shift+Tab quita sangría · Enter mantiene la sangría y agrega 4 después de ":".

Ejercicios de completar

Primero escriba la función completa en papel. Luego llene los espacios y presione Revisar. No importan los espacios en blanco.

Código completo de referencia

El mismo archivo arboles.py que quedó en su carpeta. Se puede correr con python arboles.py.

# ============================================================
#  ARBOLES BST y AVL en Python (version para estudiar a mano)
#
#  Convenciones (las de su profe):
#    - profundidad de la raiz = 0
#    - altura de una hoja = 0, arbol vacio = -1
#    - eliminar nodo con dos hijos -> PREDECESOR
#      (el mayor del subarbol izquierdo)
#    - FB (factor de balance) = altura(izq) - altura(der)
# ============================================================


class Nodo:
    def __init__(self, valor):
        self.valor = valor
        self.izq = None
        self.der = None
        self.altura = 0          # solo lo usa el AVL


# ======================== BST ========================

def insertar_bst(nodo, valor):
    if nodo is None:
        return Nodo(valor)
    if valor < nodo.valor:
        nodo.izq = insertar_bst(nodo.izq, valor)
    elif valor > nodo.valor:
        nodo.der = insertar_bst(nodo.der, valor)
    return nodo


def buscar(nodo, valor):
    if nodo is None:
        return False
    if valor == nodo.valor:
        return True
    if valor < nodo.valor:
        return buscar(nodo.izq, valor)
    return buscar(nodo.der, valor)


def maximo(nodo):
    # el predecesor de X es maximo(X.izq)
    while nodo.der is not None:
        nodo = nodo.der
    return nodo


def eliminar_bst(nodo, valor):
    if nodo is None:
        return None
    if valor < nodo.valor:
        nodo.izq = eliminar_bst(nodo.izq, valor)
    elif valor > nodo.valor:
        nodo.der = eliminar_bst(nodo.der, valor)
    else:
        # caso 1 y 2: hoja o un solo hijo
        if nodo.izq is None:
            return nodo.der
        if nodo.der is None:
            return nodo.izq
        # caso 3: dos hijos -> predecesor
        pred = maximo(nodo.izq)
        nodo.valor = pred.valor
        nodo.izq = eliminar_bst(nodo.izq, pred.valor)
    return nodo


# ===================== RECORRIDOS =====================

def inorden(nodo, res):
    if nodo is not None:
        inorden(nodo.izq, res)
        res.append(nodo.valor)
        inorden(nodo.der, res)


def preorden(nodo, res):
    if nodo is not None:
        res.append(nodo.valor)
        preorden(nodo.izq, res)
        preorden(nodo.der, res)


def postorden(nodo, res):
    if nodo is not None:
        postorden(nodo.izq, res)
        postorden(nodo.der, res)
        res.append(nodo.valor)


def anchura(raiz):
    # recorrido por niveles (BFS) usando una lista como cola
    res = []
    if raiz is None:
        return res
    cola = [raiz]
    while len(cola) > 0:
        actual = cola.pop(0)
        res.append(actual.valor)
        if actual.izq is not None:
            cola.append(actual.izq)
        if actual.der is not None:
            cola.append(actual.der)
    return res


def altura(nodo):
    if nodo is None:
        return -1
    return 1 + max(altura(nodo.izq), altura(nodo.der))


def profundidad(nodo, valor):
    d = 0
    while nodo is not None:
        if valor == nodo.valor:
            return d
        if valor < nodo.valor:
            nodo = nodo.izq
        else:
            nodo = nodo.der
        d += 1
    return -1                    # no esta


def contar_hojas(nodo):
    if nodo is None:
        return 0
    if nodo.izq is None and nodo.der is None:
        return 1
    return contar_hojas(nodo.izq) + contar_hojas(nodo.der)


# ======================== AVL ========================

def h(nodo):
    if nodo is None:
        return -1
    return nodo.altura


def actualizar(nodo):
    nodo.altura = 1 + max(h(nodo.izq), h(nodo.der))


def fb(nodo):
    return h(nodo.izq) - h(nodo.der)


def rotar_derecha(y):
    x = y.izq
    t2 = x.der
    x.der = y
    y.izq = t2
    actualizar(y)                # primero el que quedo abajo
    actualizar(x)
    return x                     # x es la nueva raiz del subarbol


def rotar_izquierda(x):
    y = x.der
    t2 = y.izq
    y.izq = x
    x.der = t2
    actualizar(x)
    actualizar(y)
    return y


def balancear(nodo):
    actualizar(nodo)
    b = fb(nodo)
    if b > 1:                            # pesa a la izquierda
        if fb(nodo.izq) < 0:             # zig-zag: caso LR
            nodo.izq = rotar_izquierda(nodo.izq)
        return rotar_derecha(nodo)       # caso LL
    if b < -1:                           # pesa a la derecha
        if fb(nodo.der) > 0:             # zig-zag: caso RL
            nodo.der = rotar_derecha(nodo.der)
        return rotar_izquierda(nodo)     # caso RR
    return nodo


def insertar_avl(nodo, valor):
    if nodo is None:
        return Nodo(valor)
    if valor < nodo.valor:
        nodo.izq = insertar_avl(nodo.izq, valor)
    elif valor > nodo.valor:
        nodo.der = insertar_avl(nodo.der, valor)
    else:
        return nodo                      # repetido: no se inserta
    return balancear(nodo)


def eliminar_avl(nodo, valor):
    if nodo is None:
        return None
    if valor < nodo.valor:
        nodo.izq = eliminar_avl(nodo.izq, valor)
    elif valor > nodo.valor:
        nodo.der = eliminar_avl(nodo.der, valor)
    else:
        if nodo.izq is None:
            return nodo.der
        if nodo.der is None:
            return nodo.izq
        pred = maximo(nodo.izq)
        nodo.valor = pred.valor
        nodo.izq = eliminar_avl(nodo.izq, pred.valor)
    return balancear(nodo)


class ArbolAVL:
    def __init__(self):
        self.raiz = None

    def insertar(self, valor):
        self.raiz = insertar_avl(self.raiz, valor)

    def eliminar(self, valor):
        self.raiz = eliminar_avl(self.raiz, valor)


# ============ NODOS CON TUPLAS Y PRIORIDAD ============
# Python compara tuplas campo por campo, de izquierda a derecha:
#   (3, 1, 20) < (3, 2, 5)   -> True  (empatan en 3, decide el 1 < 2)
# Entonces: ponga primero el campo MAS importante.
# Si un campo es "mayor primero", pongale signo menos.

class Evento:
    def __init__(self, prioridad, magnitud, id):
        self.prioridad = prioridad
        self.magnitud = magnitud
        self.id = id

    def clave(self):
        # 1. magnitud (mayor primero)  2. prioridad (menor primero)  3. id
        return (-self.magnitud, self.prioridad, self.id)

    def __lt__(self, otro):
        # con esto "a < b" funciona directo entre eventos
        return self.clave() < otro.clave()

    def __repr__(self):
        return f"#{self.id}(p={self.prioridad}, m={self.magnitud})"


def insertar_evento(nodo, ev):
    if nodo is None:
        return Nodo(ev)
    if ev.clave() < nodo.valor.clave():
        nodo.izq = insertar_evento(nodo.izq, ev)
    else:                                # el id es unico: nunca empatan
        nodo.der = insertar_evento(nodo.der, ev)
    return nodo


# ======================== DIBUJO ========================

def imprimir(nodo, nivel=0):
    # dibuja el arbol de lado: la raiz a la izquierda, la derecha arriba
    if nodo is not None:
        imprimir(nodo.der, nivel + 1)
        print("      " * nivel + str(nodo.valor))
        imprimir(nodo.izq, nivel + 1)


# ======================== DEMO ========================

def primos(n):
    res = []
    x = 2
    while len(res) < n:
        es_primo = True
        for d in range(2, x):
            if x % d == 0:
                es_primo = False
        if es_primo:
            res.append(x)
        x += 1
    return res


if __name__ == "__main__":
    serie = [p + 1 for p in primos(15)]      # "los primos mas 1"
    print("Serie:", serie)

    arbol = ArbolAVL()
    for x in serie:
        arbol.insertar(x)
    imprimir(arbol.raiz)

    for x in [20, 4, 32]:
        arbol.eliminar(x)
    print("\nDespues de eliminar 20, 4 y 32:")
    imprimir(arbol.raiz)

    r = []
    inorden(arbol.raiz, r)
    print("Inorden:  ", r)
    r = []
    preorden(arbol.raiz, r)
    print("Preorden: ", r)
    r = []
    postorden(arbol.raiz, r)
    print("Postorden:", r)
    print("Anchura:  ", anchura(arbol.raiz))
    print("Altura:   ", altura(arbol.raiz))
    print("Profundidad de 44:", profundidad(arbol.raiz, 44))
    print("Hojas:    ", contar_hojas(arbol.raiz))

    print("\nEventos (magnitud mayor primero, luego prioridad, luego id):")
    eventos = [Evento(1, 3, 25), Evento(2, 5, 11), Evento(1, 5, 40), Evento(3, 3, 7)]
    raiz = None
    for e in eventos:
        raiz = insertar_evento(raiz, e)
    r = []
    inorden(raiz, r)
    print(r)

Nodos con tuplas y prioridad

Python compara tuplas campo por campo, de izquierda a derecha, y el primer campo distinto decide:

(3, 1, 20) < (3, 2, 5)    # True: empatan en 3, decide 1 < 2 (el 20 y el 5 ni se miran)
(5, 9, 9)  < (6, 0, 0)    # True: decide el primero, 5 < 6
(-5, 1) < (-3, 1)         # True: -5 < -3

Ponga en la tupla primero el campo más importante, luego el segundo, y al final el id (desempate).
Si en un campo "el mayor va primero", póngale signo menos: así el mayor se vuelve el más pequeño.
En el BST, "va primero" = más pequeño = más a la izquierda = sale primero en inorden.
Inserte comparando claves: if ev.clave() < nodo.valor.clave(): va a la izquierda.

class Evento:
    def __init__(self, prioridad, magnitud, id):
        self.prioridad = prioridad
        self.magnitud = magnitud
        self.id = id

    def clave(self):
        # 1° magnitud (mayor primero), 2° prioridad (menor primero), 3° id
        return (-self.magnitud, self.prioridad, self.id)

Calentamiento: ¿a < b?

Árbol 2-3

Cada nodo tiene 1 clave y 2 hijos (nodo-2) o 2 claves y 3 hijos (nodo-3).
Todas las hojas están en el mismo nivel. Siempre está perfectamente balanceado.
Se inserta siempre en una hoja (bajando como en BST: menor que la 1ª clave → hijo izquierdo; entre las dos → hijo del medio; mayor → derecho).
Si la hoja queda con 3 claves, se parte: la del medio sube al padre, la menor y la mayor quedan como dos nodos separados.
Si el padre también queda con 3, se parte igual (se repite hacia arriba).
Si se parte la raíz, la clave del medio es la nueva raíz: el árbol crece hacia arriba, no hacia abajo.

Rojo-Negro

Cada nodo es rojo o negro.
La raíz es negra.
Las hojas nulas (NIL) cuentan como negras.
Un rojo no puede tener hijos rojos.
Desde cualquier nodo, todos los caminos hasta un NIL tienen la misma cantidad de negros.

Insertar

El nuevo entra ROJO. Si el padre es negro, listo. Si el padre es rojo, mire al tío (el hermano del padre):

Tío rojo → recolorear: padre y tío a negro, abuelo a rojo. Repita el análisis desde el abuelo.
Tío negro y zig-zag → rote sobre el padre para dejarlo en línea recta (y siga al caso de abajo).
Tío negro y línea recta → rote sobre el abuelo; el que sube queda negro y el abuelo rojo.
Al final, la raíz siempre se pinta negra.

Visualizador paso a paso

Escriba una secuencia, haga cada inserción en papel y luego compare.