El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència

HOME

La lliçó anterior va acabar amb una mesura incòmoda: l'índex de TaskFlow, construït amb ids autoincrementals — el cas més comú del món real —, degenerava en una llista i els seus O(log n) s'evaporaven. L'arbre AVL (pels seus inventors, Adelson-Velskii i Landis, 1962) és un ABC que es nega a degenerar: després de cada inserció comprova un número per node (el factor d'equilibri) i, si detecta desequilibri, el corregeix amb una rotació — una recol·locació local de dos o tres nodes que restaura l'equilibri sense trencar la propietat de cerca. El resultat: altura O(log n) garantida, arribi la dada que arribi i en l'ordre que arribi. En aquesta lliçó entendràs el factor d'equilibri, les quatre rotacions (LL, RR, LR, RL) amb diagrames pas a pas, implementaràs la inserció AVL completa i mesuraràs la diferència amb l'experiment exacte que va enfonsar l'ABC.

Contingut

El problema, quantificat: per què l'ABC no basta
Factor d'equilibri: l'espieta de cada node
Les rotacions simples: LL i RR
Les rotacions dobles: LR i RL
Implementació: inserció AVL amb reequilibratge recursiu
La revenja: mesurar ABC vs AVL amb ids ordenats
Quan compensa un AVL (i què usen les llibreries)

El problema, quantificat: per què l'ABC no basta

Recapitulem la ferida de 06-04 amb números: inserir range(1023) en un ABC produeix altura 1022; barrejat, ~20; l'ideal era 9. El problema no és l'ABC com a idea — és que la seva forma queda a mercè de l'ordre d'arribada, i les dades reals arriben amb ordre (ids creixents, dates, comptadors). Un índex el rendiment del qual depèn de la sort no és un índex: és una loteria.

La idea de l'AVL: mantenir un invariant d'equilibri a més del de cerca. Concretament:

A tot node, les altures dels seus dos subarbres difereixen com a màxim en 1.

No exigeix perfecció (això obligaria a reconstruccions massives); exigeix quasi-equilibri, que és barat de mantenir i suficient: es demostra que un AVL amb n nodes té altura menor que 1,45·log₂(n+2) — per al milió de tasques de la taula de 06-02, altura ≤ 28 en lloc de fins a 999 999. O(log n) amb garantia matemàtica, no estadística.

Factor d'equilibri: l'espieta de cada node

Per vigilar l'invariant sense recalcular altures a cada pas (això seria O(n) per consulta), cada node guarda la seva altura com a atribut, i definim:

factor d'equilibri (FE) = altura(subarbre esquerre) − altura(subarbre dret)

FE	Significat
0	Perfectament equilibrat en aquest node
+1	L'esquerra és un nivell més alta: acceptable
−1	La dreta és un nivell més alta: acceptable
+2	Massa carregat a l'esquerra: rotar
−2	Massa carregat a la dreta: rotar

Inserint d'un en un, el FE només pot arribar a ±2 (partíem de ±1 com a molt i una inserció canvia les altures en 1); mai no veurem un ±3. Per això les correccions són sempre locals i petites.

graph TD
    A["10 (FE=+2) ⚠"] --> B["6 (FE=+1)"]
    A --> Z["(buit)"]
    B --> C["3 (FE=0)"]
    B --> Y["(buit)"]

Aquest arbre (inserir 10, 6, 3) ja viola l'invariant a l'arrel: esquerra d'altura 1, dreta d'altura −1 (buida), FE = +2. En un ABC normal aquí no passa res i la degeneració arrenca; l'AVL, en canvi, actua.

Les rotacions simples: LL i RR

Una rotació reorganitza un node i un dels seus fills de manera que el fill puja, el pare baixa, i — això és el crucial — l'ordre inordre no canvia, així que la propietat de cerca sobreviu intacta. Hi ha quatre casos de desequilibri, anomenats segons on va caure el node nou respecte al node desequilibrat: LL, RR, LR i RL.

Cas LL (left-left): FE = +2 i l'excés és al subarbre esquerre-esquerre. Es corregeix amb una rotació a la dreta: el fill esquerre puja a arrel del subarbre, l'antic pare passa a ser el seu fill dret, i el subarbre B (els valors entre tots dos) canvia de costat:

graph TD
    subgraph "Abans: FE(z)=+2, cas LL"
        Z((z)) --> Y((y))
        Z --> T4[T4]
        Y --> X((x))
        Y --> T3[T3]
        X --> T1[T1]
        X --> T2[T2]
    end
    subgraph "Després: rotació dreta sobre z"
        Y2((y)) --> X2((x))
        Y2 --> Z2((z))
        X2 --> T1b[T1]
        X2 --> T2b[T2]
        Z2 --> T3b[T3]
        Z2 --> T4b[T4]
    end

Comprova l'inordre en tots dos: T1, x, T2, y, T3, z, T4. Idèntic — la cerca no s'assabenta de res, però l'altura del conjunt baixa en 1. Amb l'exemple 10-6-3: z=10, y=6, x=3; després de rotar, el 6 és l'arrel amb el 3 i el 10 com a fills. Equilibri restaurat amb tres reassignacions de referències: O(1).

El cas RR és el mirall exacte (FE = −2, excés a dreta-dreta; inserir 3, 6, 10 el provoca): rotació a l'esquerra, el fill dret puja. En codi, totes dues:

def rotar_dreta(z):
    """Cas LL. Retorna la nova arrel del subarbre (y)."""
    y = z.esquerre
    t3 = y.dret
    y.dret = z             # el pare baixa a fill dret
    z.esquerre = t3        # i el seu antic subarbre dret (T3) canvia d'amo
    actualitzar_altura(z)  # z primer: ara és el de baix
    actualitzar_altura(y)
    return y

def rotar_esquerra(z):
    """Cas RR. Mirall de l'anterior. Retorna la nova arrel (y)."""
    y = z.dret
    t2 = y.esquerre
    y.esquerre = z
    z.dret = t2
    actualitzar_altura(z)
    actualitzar_altura(y)
    return y

El trasllat de t3 és el pas que la gent oblida: els valors de T3 són entre y i z (majors que y, menors que z), i després de la rotació el seu lloc correcte és el forat esquerre de z. I les altures s'actualitzen de baix a dalt: primer z (ara fill), després y (ara arrel del subarbre).

Les rotacions dobles: LR i RL

I si l'excés és "en zig-zag"? Inserir 10, 3, 6: el 10 té FE = +2, però el node nou ha caigut al subarbre esquerre-dret. Una sola rotació dreta no ho arregla (prova-ho en paper: el 3 pujaria amb FE = −2 — el desequilibri només canvia de costat). El cas LR necessita dos moviments: primer una rotació esquerra sobre el fill (converteix el zig-zag en el cas LL) i després la rotació dreta de sempre sobre el node desequilibrat:

graph TD
    subgraph "1. Abans: cas LR"
        Z((10)) --> Y((3))
        Y --> X((6))
    end
    subgraph "2. Rotar esquerra sobre 3"
        Z2((10)) --> X2((6))
        X2 --> Y2((3))
    end
    subgraph "3. Rotar dreta sobre 10"
        X3((6)) --> Y3((3))
        X3 --> Z3((10))
    end

El net (6) acaba d'arrel del subarbre, amb el seu antic avi i el seu antic pare com a fills. El cas RL és el mirall (FE = −2 amb l'excés a dreta-esquerra; inserir 3, 10, 6): rotació dreta sobre el fill, després esquerra sobre el node. Resum dels quatre casos:

Cas	Detecció	Correcció
LL	FE = +2 i FE(fill esq.) ≥ 0	Rotació dreta
LR	FE = +2 i FE(fill esq.) < 0	Rot. esquerra sobre el fill + rot. dreta
RR	FE = −2 i FE(fill dret) ≤ 0	Rotació esquerra
RL	FE = −2 i FE(fill dret) > 0	Rot. dreta sobre el fill + rot. esquerra

Fixa't que la detecció és purament aritmètica: el FE del node diu el costat del problema, i el FE del fill diu si és en línia (simple) o en zig-zag (doble).

Implementació: inserció AVL amb reequilibratge recursiu

Assemblem-ho. L'estratègia és la inserció recursiva de l'ABC amb un pas extra en tornar de cada crida: actualitzar l'altura del node i, si el seu FE ha sortit de [−1, +1], aplicar la rotació del cas corresponent. Com que cada crida retorna la (potser nova) arrel del seu subarbre, el patró "reassignar en tornar" que vam usar a _esborrar de 06-04 encaixa perfecte:

class NodeAVL:
    def __init__(self, clau, valor):
        self.clau = clau
        self.valor = valor
        self.esquerre = None
        self.dret = None
        self.altura = 0                  # fulla acabada de néixer (convenció de 06-02)

def altura_de(node):
    return node.altura if node else -1   # el subarbre buit fa -1

def actualitzar_altura(node):
    node.altura = 1 + max(altura_de(node.esquerre), altura_de(node.dret))

def factor_equilibri(node):
    return altura_de(node.esquerre) - altura_de(node.dret)

class ArbreAVL:
    def __init__(self):
        self.arrel = None

    def inserir(self, clau, valor):
        self.arrel = self._inserir(self.arrel, clau, valor)

    def _inserir(self, node, clau, valor):
        # 1) Inserció ABC normal (recursiva)
        if node is None:
            return NodeAVL(clau, valor)
        if clau == node.clau:
            node.valor = valor
            return node
        elif clau < node.clau:
            node.esquerre = self._inserir(node.esquerre, clau, valor)
        else:
            node.dret = self._inserir(node.dret, clau, valor)

        # 2) En TORNAR: actualitzar altura i comprovar equilibri
        actualitzar_altura(node)
        fe = factor_equilibri(node)

        # 3) Els quatre casos
        if fe > 1 and factor_equilibri(node.esquerre) >= 0:     # LL
            return rotar_dreta(node)
        if fe > 1:                                              # LR
            node.esquerre = rotar_esquerra(node.esquerre)
            return rotar_dreta(node)
        if fe < -1 and factor_equilibri(node.dret) <= 0:        # RR
            return rotar_esquerra(node)
        if fe < -1:                                             # RL
            node.dret = rotar_dreta(node.dret)
            return rotar_esquerra(node)

        return node                       # equilibrat: sense canvis

    def cercar(self, clau):               # idèntic a l'ABC!
        node = self.arrel
        while node is not None:
            if clau == node.clau:
                return node.valor
            node = node.esquerre if clau < node.clau else node.dret
        return None

Punts fins, de dalt a baix:

Tot passa en desfer la recursió: la inserció baixa fins a la fulla, i les actualitzacions d'altura i les rotacions succeeixen camí de tornada, de la fulla cap a l'arrel — just la direcció en què el desequilibri es propaga.
Guardar l'altura al node fa que factor_equilibri sigui O(1); sense ella, cada comprovació costaria recórrer el subarbre.
Un teorema tranquil·litzador: en una inserció, una sola rotació (simple o doble) restaura l'equilibri de tot l'arbre — un cop corregit el primer node desequilibrat, els ancestres recuperen la seva altura prèvia i no cal continuar. (L'esborrat AVL és menys amable: pot necessitar rotacions en cascada fins a l'arrel, continua sent O(log n); la seva implementació combina _esborrar de 06-04 amb aquest mateix reequilibratge i queda fora de l'abast de la lliçó.)
cercar (i inordre, i interval...) són els mateixos de l'ABC, sense tocar-hi una coma: l'AVL és un ABC. Només canvia qui controla la forma.

Verifiquem amb la seqüència assassina:

avl = ArbreAVL()
for i in range(1, 8):
    avl.inserir(i, f"Tasca {i}")

print(avl.arrel.clau)          # 4: l'arrel és la mediana, no l'1!
print(altura_de(avl.arrel))    # 2: el mínim possible amb 7 nodes

Inserint 1…7 en ordre, l'ABC donava altura 6; l'AVL dona 2, l'arbre perfecte. Les rotacions han anat recol·locant: en inserir el 3, la cadena 1-2-3 rota i el 2 puja; en inserir el 5, rota el subarbre del 3... L'arbre es reconstrueix sol, inserció a inserció, sense que el codi client en sàpiga res.

La revenja: mesurar ABC vs AVL amb ids ordenats

Repetim l'experiment exacte que va condemnar l'ABC a 06-04 — 2 000 ids autoincrementals — més una cerca sobre el resultat:

import timeit

def construir_avl(claus):
    a = ArbreAVL()
    for c in claus:
        a.inserir(c, None)
    return a

ids = list(range(2000))

print(timeit.timeit(lambda: construir(ids), number=5))       # ABC:  ~4 s
print(timeit.timeit(lambda: construir_avl(ids), number=5))   # AVL:  ~0.06 s

abc, avl = construir(ids), construir_avl(ids)
print(timeit.timeit(lambda: abc.cercar(1999), number=10000)) # ~1.9 s  (recorre 2000 nodes)
print(timeit.timeit(lambda: avl.cercar(1999), number=10000)) # ~0.02 s (baixa ~11 nivells)
print(altura_abc(abc), altura_de(avl.arrel))                 # 1999  vs  10

Els temps concrets variaran a la teva màquina, però l'estructura del resultat no: construcció ~70 vegades més ràpida, cerca ~100 vegades més ràpida, altura 1999 contra 10. I nota la lletra petita justa: l'AVL paga un sobrecost constant per inserció (actualitzar altures, comprovar FE, rotar de tant en tant) — amb claus aleatòries l'ABC simple fins i tot pot guanyar-li per poc. El que compra l'AVL no és velocitat en el cas bo: és l'eliminació del cas dolent.

Quan compensa un AVL (i què usen les llibreries)

Sempre AVL, doncs? Gairebé, però amb criteri:

Compensa quan les cerques i consultes per interval dominen sobre les escriptures, o quan no controles l'ordre d'arribada de les claus (o sí que el controles: i és ordenat!). L'AVL és el més rígidament equilibrat dels arbres autoequilibrats: altura mínima, cerques màximament ràpides.
Es queda curt quan hi ha moltíssimes escriptures: la seva rigidesa obliga a rotar amb freqüència. Per a aquestes càrregues existeix l'arbre roig-negre, un cosí que tolera una mica més de desequilibri (altura ≤ 2·log₂ n) a canvi de rotar menys; és l'elecció de les llibreries estàndard — el std::map de C++, el TreeMap de Java — precisament per aquest equilibri entre lectures i escriptures. No el desenvoluparem: les idees (invariant + rotacions locals) són les mateixes que acabes d'aprendre, canvia la comptabilitat.
Python, per cert, no porta cap arbre equilibrat a la biblioteca estàndard (la seva cultura ho resol gairebé tot amb dict + sorted); a l'ecosistema existeixen paquets com sortedcontainers que cobreixen el buit amb una altra tècnica. Ara entens exactament quin forat tapen.

Per a TaskFlow, la decisió és clara: l'índex (prioritat, id) de 06-04 rep ids autoincrementals cada dia — la càrrega que degenera l'ABC. Canviar ArbreCerca() per ArbreAVL() (mateixa interfície: inserir, cercar...) dona a TaskFlow un índex ordenat que no es degrada mai, rebi el que rebi.

Errors Comuns i Consells

Oblidar actualitzar les altures, o fer-ho en mal ordre. Després d'una rotació, primer la del node que ha baixat, després la del que ha pujat (el de dalt depèn del de baix). Altures desactualitzades → FE mentiders → rotacions on no toca. És el bug número u de les implementacions casolanes.
Perdre el subarbre del mig (T2/T3) en rotar. La rotació no és "intercanviar pare i fill": el subarbre intermedi ha de canviar de progenitor. Si el teu arbre perd nodes després de rotar, és això.
Tractar un cas zig-zag amb rotació simple. LR i RL necessiten la doble; la simple deixa FE = ∓2 a l'altre costat i, amb mala sort, un bucle de rotacions estèrils. La detecció correcta mira el FE del fill.
Oblidar reassignar el resultat: self.arrel = self._inserir(...) i node.esquerre = rotar_esquerra(...). Les rotacions retornen la nova arrel del subarbre; ignorar el retorn deixa referències apuntant al node que ja no és arrel.
Consell de verificació: després de cada tanda d'insercions a les teves proves, comprova dos invariants: l'inordre surt ordenat (propietat ABC intacta) i tots els FE són a {−1, 0, +1} (equilibri). Un test de deu línies que caça el 95 % dels errors d'AVL.

Exercicis

Exercici 1: la traça de les rotacions

Sense executar codi, dibuixa l'AVL després d'inserir, en aquest ordre, les claus 30, 20, 10, 25, 27. Indica quin cas (LL, RR, LR, RL) es dispara a cada rotació i sobre quin node. Després verifica-ho amb codi imprimint l'inordre i l'arrel.

Exercici 2: auditor d'equilibri

Escriu es_avl_valid(node) que retorni True si tots els FE de l'arbre són a {−1, 0, +1}, calculant les altures pel seu compte (sense refiar-se de l'atribut altura, que és precisament el que podria estar malament). Prova-ho sobre l'AVL d'1…7 i sobre un ABC degenerat.

Exercici 3: l'índex indestructible de TaskFlow

Reconstrueix l'índex (prioritat, id) de 06-04 sobre ArbreAVL, inserint 30 tasques amb ids 1…30 i prioritats (i % 3) + 1. Comprova: (a) que l'altura és ≤ 1,45·log₂(32) ≈ 7; (b) que un inordre filtrat retorna les tasques de prioritat 1 ordenades per id. (Si has afegit interval a l'AVL copiant-lo de l'ABC, encara millor: usa'l.)

Solucions

Solució 1

Pas a pas:

30, 20: sense problemes (FE(30) = +1).
10: cadena 30-20-10, FE(30) = +2 amb excés esquerra-esquerra → LL, rotació dreta sobre el 30. Queda el 20 com a arrel, fills 10 i 30.
25: baixa a fill esquerre del 30. FE(20) = −1, FE(30) = +1: tot dins de rang, sense rotació.
27: baixa sota el 25, a la seva dreta. Ara FE(30) = +2 i l'excés és a esquerra-dreta → LR sobre el 30: rotació esquerra sobre el 25 (el 27 puja) i dreta sobre el 30. El subarbre queda 27 amb fills 25 i 30.

Arbre final: arrel 20, esquerra 10, dreta 27, i sota el 27 els nodes 25 i 30. Verificació:

avl = ArbreAVL()
for c in [30, 20, 10, 25, 27]:
    avl.inserir(c, None)
print(avl.arrel.clau)                        # 20
print(avl.arrel.dret.clau)                   # 27
# inordre: [10, 20, 25, 27, 30] — ordenat, propietat intacta

Comentari: el pas 4 és el que separa qui entén l'AVL de qui el memoritza — la primera intuïció ("rotar dreta sobre el 30 i ja està") deixa l'arbre igual de desequilibrat. Dibuixa sempre el FE del fill abans de decidir.

Solució 2

def _altura_i_validesa(node):
    """Retorna (altura real, es_valid) del subarbre, en una sola passada."""
    if node is None:
        return -1, True
    alt_esq, ok_esq = _altura_i_validesa(node.esquerre)
    alt_dret, ok_dret = _altura_i_validesa(node.dret)
    fe = alt_esq - alt_dret
    return 1 + max(alt_esq, alt_dret), ok_esq and ok_dret and abs(fe) <= 1

def es_avl_valid(node):
    return _altura_i_validesa(node)[1]

print(es_avl_valid(avl.arrel))          # True
print(es_avl_valid(construir(list(range(10))).arrel))   # False (ABC degenerat)

Comentari: la funció retorna dues coses alhora (altura i veredicte) perquè la passada sigui O(n) — la versió ingènua que crida altura() a cada node és O(n²), exactament la trampa de rendiment que l'atribut altura de l'AVL evita en producció. És un postordre pur: la informació (altures) flueix de fills a pares, com les hores acumulades de 06-03. Aquest auditor és el test de deu línies del consell final; l'auditor bessó de la propietat de cerca cau a 06-08.

Solució 3

import math

index = ArbreAVL()
for i in range(1, 31):
    tasca = {"id": i, "titol": f"Tasca {i}", "prioritat": (i % 3) + 1,
             "estat": "pendent"}
    index.inserir((tasca["prioritat"], i), tasca)

# (a) altura garantida
print(altura_de(index.arrel))                      # 5 o 6 segons la seqüència
print(1.45 * math.log2(32))                        # 7.25: dins de la garantia

# (b) prioritat 1, ordenades per id (inordre + filtre)
resultat = []
def inordre(node):
    if node is None:
        return
    inordre(node.esquerre)
    resultat.append(node)
    inordre(node.dret)
inordre(index.arrel)
prio1 = [n.valor["id"] for n in resultat if n.clau[0] == 1]
print(prio1)     # [3, 6, 9, 12, 15, 18, 21, 24, 27, 30] — ascendent, garantit

Comentari: les claus (prioritat, id) arriben amb id estrictament creixent — dins de cada prioritat, la seqüència que degenerava l'ABC. L'AVL ni s'immuta: altura 5-6 amb 30 nodes, dins de la cota 1,45·log₂(n+2). I l'inordre surt agrupat per prioritat i per id dins de cada grup, perquè així comparen les tuples. Aquest és, ja en la seva versió definitiva, l'índex ordenat de TaskFlow: la interfície de 06-04, la garantia de 06-05.

Conclusió

L'AVL tanca la vulnerabilitat que l'ABC portava de sèrie: guardant una altura per node, vigilant el factor d'equilibri i corregint amb les quatre rotacions (LL i RR simples, LR i RL dobles — totes O(1), totes preservant l'inordre), garanteix altura O(log n) passi el que passi — i ho has comprovat amb la mateixa seqüència d'ids ordenats que enfonsava l'ABC: altura 10 on hi havia 1999. TaskFlow té per fi un índex ordenat indestructible, i de regal coneixes el mapa del territori: roig-negre quan les escriptures estrenyen (l'elecció de les llibreries), i el perquè del buit a la biblioteca estàndard de Python. Però tota aquesta lliçó ha donat per fet una cosa: que l'arbre sencer viu a la RAM, on saltar d'un node a un altre és gratis. I si les tasques de TaskFlow són milions i viuen a disc, on cada accés es paga a preu d'or i per blocs? Allà els arbres binaris — fins i tot perfectes — fan massa salts, i cal un arbre més baix i molt més ample: l'arbre B, el que sosté les bases de dades, i la propera lliçó.

Arbres AVL

Contingut

El problema, quantificat: per què l'ABC no basta

Factor d'equilibri: l'espieta de cada node

Les rotacions simples: LL i RR

Les rotacions dobles: LR i RL

Implementació: inserció AVL amb reequilibratge recursiu

La revenja: mesurar ABC vs AVL amb ids ordenats

Quan compensa un AVL (i què usen les llibreries)

Errors Comuns i Consells

Exercicis

Exercici 1: la traça de les rotacions

Exercici 2: auditor d'equilibri

Exercici 3: l'índex indestructible de TaskFlow

Solucions

Solució 1

Solució 2

Solució 3

Conclusió

Curs d'Estructures de Dades

Mòdul 1: Introducció a les Estructures de Dades

Mòdul 2: Llistes

Mòdul 3: Piles

Mòdul 4: Cues

Mòdul 5: Taules Hash i Diccionaris

Mòdul 6: Arbres

Mòdul 7: Grafs

Mòdul 8: Conclusions i Recursos Addicionals