El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Arbres Binaris de Cerca

Següent ►
►

Aquesta és la lliçó on el mòdul paga els seus deutes. El hash del mòdul 5 emmudia davant de "dona'm les tasques ordenades per id" i "les de prioritat entre 1 i 3"; l'inordre de 06-03 sortia misteriosament ordenat. Totes dues coses tenen la mateixa explicació: l'arbre binari de cerca (ABC, o BST en anglès), un arbre binari amb una regla de col·locació — menors a l'esquerra, majors a la dreta — que converteix cada comparació en un descart de mig arbre. Aquí implementaràs la classe ArbreCerca completa (inserir, cercar, mínim/màxim, esborrar amb els seus tres casos, recorregut ordenat i cerca per interval), la faràs servir com a índex de tasques de TaskFlow, i en descobriràs també el taló d'Aquil·les: amb dades que arriben ja ordenades, l'ABC degenera en llista i tot es torna O(n) — el problema que motivarà la lliçó següent.

Contingut

  1. La propietat ABC: una regla, totes les conseqüències
  2. Cercar i inserir: descendir comparant
  3. Mínim, màxim i l'inordre que surt ordenat
  4. Esborrar: els tres casos
  5. Cerca per interval: el deute del mòdul 5, saldat
  6. El cost és O(altura): la demo de l'arbre degenerat
  7. dict vs ABC: cadascú a la seva

La propietat ABC: una regla, totes les conseqüències

Un arbre binari de cerca és un arbre binari on, per a tot node amb clau k:

  • Totes les claus del seu subarbre esquerre són menors que k.
  • Totes les claus del seu subarbre dret són majors que k.
graph TD
    A((10)) --> B((6))
    A --> C((15))
    B --> D((3))
    B --> E((8))
    C --> F((12))
    C --> G((20))

L'arbre de 06-03 era això. Comprova la propietat a l'arrel: a l'esquerra del 10 hi ha {6, 3, 8}, tots menors; a la dreta, {15, 12, 20}, tots majors. I ull a l'adverbi totes: no n'hi ha prou que cada fill respecti el seu pare — el 8 és fill dret del 6 (correcte: 8 > 6), però a més ha de ser menor que 10, perquè viu al subarbre esquerre de l'arrel. Aquesta distinció entre "regla local" i "regla sobre el subarbre sencer" és l'error clàssic en validar un ABC, i el caçarem a 06-08.

La conseqüència operativa: aturat a qualsevol node, una sola comparació et diu en quina meitat continuar — igual que la cerca binària del mòdul 1, però sobre una estructura enllaçada que a més admet insercions i esborrats barats (l'array ordenat cercava en O(log n) però inseria en O(n) desplaçant elements). L'ABC és, conceptualment, la cerca binària feta estructura de dades.

Cercar i inserir: descendir comparant

Construïm la classe completa. Cada node guardarà una clau (per la qual s'ordena) i un valor (la tasca de TaskFlow), com a la TaulaHash:

class NodeABC:
    def __init__(self, clau, valor):
        self.clau = clau
        self.valor = valor
        self.esquerre = None
        self.dret = None

class ArbreCerca:
    """Índex ordenat: clau -> valor, amb recorreguts i intervals."""

    def __init__(self):
        self.arrel = None

    def cercar(self, clau):
        """Retorna el valor associat a la clau, o None si no hi és. O(altura)."""
        node = self.arrel
        while node is not None:
            if clau == node.clau:
                return node.valor
            elif clau < node.clau:
                node = node.esquerre       # el menor només pot ser a l'esquerra
            else:
                node = node.dret           # el major, a la dreta
        return None

cercar és el descens de l'arbre de decisió de 06-02, amb la pregunta "la clau cercada és menor que la meva?". Cada comparació baixa un nivell i descarta l'altre subarbre sencer: per això el cost és O(altura), no O(n). Inserir segueix el mateix camí — la posició d'una clau nova és exactament on la cerca hauria caigut de l'arbre:

    def inserir(self, clau, valor):
        """Insereix el parell (o actualitza el valor si la clau ja existeix). O(altura)."""
        if self.arrel is None:
            self.arrel = NodeABC(clau, valor)
            return
        node = self.arrel
        while True:
            if clau == node.clau:
                node.valor = valor                       # clau repetida: actualitzar
                return
            elif clau < node.clau:
                if node.esquerre is None:
                    node.esquerre = NodeABC(clau, valor)
                    return
                node = node.esquerre
            else:
                if node.dret is None:
                    node.dret = NodeABC(clau, valor)
                    return
                node = node.dret

Muntem l'índex de tasques per id (fem servir ids enters per comparar còmodament):

index = ArbreCerca()
tasques = [
    (10, {"id": 10, "titol": "Desplegar l'API", "prioritat": 2, "estat": "pendent"}),
    (6,  {"id": 6,  "titol": "Revisar el login", "prioritat": 1, "estat": "en curs"}),
    (15, {"id": 15, "titol": "Còpia de seguretat", "prioritat": 3, "estat": "pendent"}),
    (3,  {"id": 3,  "titol": "Arreglar el CSS", "prioritat": 2, "estat": "pendent"}),
    (8,  {"id": 8,  "titol": "Migrar les dades", "prioritat": 1, "estat": "bloquejada"}),
    (12, {"id": 12, "titol": "Optimitzar les consultes", "prioritat": 2, "estat": "pendent"}),
    (20, {"id": 20, "titol": "Documentar l'API", "prioritat": 3, "estat": "pendent"}),
]
for id_tasca, tasca in tasques:
    index.inserir(id_tasca, tasca)

print(index.cercar(8)["titol"])      # Migrar les dades
print(index.cercar(99))              # None

L'ordre d'inserció (el 10 primer, després el 6, el 15...) ha construït exactament l'arbre del diagrama. Guarda aquesta dada: la forma de l'ABC depèn de l'ordre d'arribada de les claus. Ens tornarà a mossegar a la secció 6.

Mínim, màxim i l'inordre que surt ordenat

La propietat ABC regala tres operacions que el hash ni somia:

    def minim(self):
        """La clau més petita: tot cap a l'esquerra. O(altura)."""
        if self.arrel is None:
            return None
        node = self.arrel
        while node.esquerre is not None:
            node = node.esquerre
        return node.clau

    def maxim(self):
        """La clau més gran: tot cap a la dreta. O(altura)."""
        if self.arrel is None:
            return None
        node = self.arrel
        while node.dret is not None:
            node = node.dret
        return node.clau

    def inordre(self):
        """Tots els (clau, valor) en ordre ascendent de clau. O(n)."""
        resultat = []
        self._inordre(self.arrel, resultat)
        return resultat

    def _inordre(self, node, resultat):
        if node is None:
            return
        self._inordre(node.esquerre, resultat)
        resultat.append((node.clau, node.valor))
        self._inordre(node.dret, resultat)
print(index.minim(), index.maxim())        # 3 20
print([clau for clau, _ in index.inordre()])   # [3, 6, 8, 10, 12, 15, 20]

I aquí es compleix l'anunci de 06-03: l'inordre d'un ABC retorna les claus ordenades, sempre. La demostració cap en dues línies: l'inordre visita esquerra → node → dreta; per la propietat ABC, tot el de l'esquerra és menor que el node i tot el de la dreta major; aplicant el mateix argument recursivament a cada subarbre, la sortida completa queda ascendent. "Dona'm les tasques ordenades per id" — la primera pregunta que va deixar muda la TaulaHash — és ara una crida a inordre(), en O(n) i sense ordenar res: l'arbre manté l'ordre com a invariant permanent, no el calcula sota demanda com faria sorted() (O(n log n) cada vegada).

Esborrar: els tres casos

Esborrar és l'operació delicada: cal treure el node sense trencar la propietat per als altres. Tres casos, de fàcil a difícil:

Cas Situació Solució
1 El node és fulla Desenganxar-lo del pare, i prou
2 Té un sol fill El fill n'ocupa el lloc (com saltar-se un node a la llista enllaçada)
3 Té dos fills Substituir-lo pel seu successor i esborrar el successor

El cas 3 mereix explicació. No podem deixar un forat amb dos subarbres penjant; necessitem un substitut que mantingui "esquerra menor, dreta major". El candidat perfecte és el successor inordre: la menor clau del subarbre dret (el node que sortiria just després a inordre). És major que tot el subarbre esquerre (és a la dreta) i menor que la resta del subarbre dret (n'és el mínim) — encaixa exactament. I esborrar-lo de la seva posició original és fàcil: sent el mínim d'un subarbre, no té fill esquerre (cas 1 o 2 garantit). El simètric (màxim del subarbre esquerre, el predecessor) funciona igual de bé.

graph TD
    subgraph "Esborrar el 10 (dos fills)"
        A((10)) --> B((6))
        A --> C((15))
        C --> F((12))
        C --> G((20))
    end
    subgraph "El successor 12 el substitueix"
        A2((12)) --> B2((6))
        A2 --> C2((15))
        C2 -.esborrat.-> F2((12))
        C2 --> G2((20))
    end

La implementació recursiva és la més neta — cada crida retorna l'arrel (potser nova) del seu subarbre, i el pare la reenganxa; el mateix patró "reconstruir en tornar" que farem servir a l'AVL:

    def esborrar(self, clau):
        self.arrel = self._esborrar(self.arrel, clau)

    def _esborrar(self, node, clau):
        if node is None:
            return None                              # clau no trobada: res a fer
        if clau < node.clau:
            node.esquerre = self._esborrar(node.esquerre, clau)
        elif clau > node.clau:
            node.dret = self._esborrar(node.dret, clau)
        else:
            # Trobat. Casos 1 i 2: zero o un fill
            if node.esquerre is None:
                return node.dret                     # pot ser None (cas fulla)
            if node.dret is None:
                return node.esquerre
            # Cas 3: dos fills -> successor = mínim del subarbre dret
            successor = node.dret
            while successor.esquerre is not None:
                successor = successor.esquerre
            node.clau, node.valor = successor.clau, successor.valor   # copiar el successor aquí
            node.dret = self._esborrar(node.dret, successor.clau)     # i esborrar-lo d'allà
        return node
index.esborrar(10)    # l'arrel, amb dos fills: el cas difícil
print([c for c, _ in index.inordre()])     # [3, 6, 8, 12, 15, 20] — continua ordenat
print(index.arrel.clau)                    # 12: el successor ha ocupat l'arrel

Llegeix-ho dues vegades, que s'ho val: els casos 1 i 2 es resolen retornant el fill (o None) perquè el pare l'adopti; el cas 3 no esborra el node físic sinó que hi copia dins les dades del successor i delega l'esborrat real en un cas fàcil. Cost total: O(altura) — un descens per trobar, un altre de parcial per al successor.

Cerca per interval: el deute del mòdul 5, saldat

La pregunta que el hash no podia ni plantejar-se: "totes les tasques amb clau entre a i b". A l'ABC, la propietat permet podar: si la clau d'un node ja és menor que a, el seu subarbre esquerre sencer queda fora de l'interval — ni el visitem.

    def interval(self, des_de, fins_a):
        """Parells (clau, valor) amb des_de <= clau <= fins_a, en ordre. O(altura + k)."""
        resultat = []
        self._interval(self.arrel, des_de, fins_a, resultat)
        return resultat

    def _interval(self, node, des_de, fins_a, resultat):
        if node is None:
            return
        if node.clau > des_de:                 # pot haver-hi candidats a l'esquerra
            self._interval(node.esquerre, des_de, fins_a, resultat)
        if des_de <= node.clau <= fins_a:      # aquest node hi entra?
            resultat.append((node.clau, node.valor))
        if node.clau < fins_a:                 # pot haver-hi candidats a la dreta
            self._interval(node.dret, des_de, fins_a, resultat)

És un inordre amb dos frens: només entra en un subarbre si l'interval el pot abastar. El cost és O(altura + k), amb k resultats: baixar fins a l'interval costa l'altura, i a partir d'aquí només es trepitja el que es retorna (més una franja de frontera). Comparat amb el hash: allà l'única opció era recórrer-ho TOT i filtrar, O(n) sempre.

I "prioritat entre 1 i 3"? La prioritat no és única (moltes tasques comparteixen prioritat) i el nostre ABC vol claus diferents. El truc professional, el mateix del (prioritat, comptador, tasca) de la SafataUrgencies del mòdul 4: una clau composta (prioritat, id) — les tuples es comparen lexicogràficament, així que ordena per prioritat i desempata per id, i cada parell és únic:

per_prioritat = ArbreCerca()
for id_tasca, tasca in tasques:
    per_prioritat.inserir((tasca["prioritat"], id_tasca), tasca)

# El deute del mòdul 5: tasques amb prioritat entre 1 i 3
urgents = per_prioritat.interval((1, 0), (3, float("inf")))
for (prio, id_t), tasca in urgents:
    print(prio, id_t, tasca["titol"])
# 1 6  Revisar el login
# 1 8  Migrar les dades
# 2 3  Arreglar el CSS
# ...ordenades per (prioritat, id), de la 1 a la 3

Els extrems (1, 0) i (3, float("inf")) acoten "qualsevol id amb prioritat 1" per baix i "qualsevol id amb prioritat 3" per dalt. Consulta resposta, ordenada de propina, i podant tot el que no toca. Aquesta és la fila de la taula de 06-01 que quedava en blanc.

El cost és O(altura): la demo de l'arbre degenerat

Tot l'anterior costa O(altura) i hem anat insinuant que l'altura ens pot trair. Toca provocar el desastre. Què passa si les claus arriben ja ordenades — el cas més natural del món: ids autoincrementals, tasques creades en ordre?

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

Cada clau nova és major que totes les anteriors, així que sempre baixa per la dreta:

graph TD
    A((1)) --> B((2))
    B --> C((3))
    C --> D((4))
    D --> E((5))
    E --> F((6))
    F --> G((7))

L'arbre degenerat de 06-02: una llista enllaçada amb nom d'arbre. Altura n−1, i tota la taula de costos s'enfonsa:

Operació ABC equilibrat ABC degenerat
cercar O(log n) O(n)
inserir O(log n) O(n)
esborrar O(log n) O(n)
minim / maxim O(log n) O(n)

Mesurem-ho amb timeit, com al mòdul 1 — construir l'índex amb 2 000 ids ordenats davant dels mateixos ids desordenats:

import timeit, random, sys
sys.setrecursionlimit(10000)     # l'inordre recursiu sobre arbre degenerat ho necessita

ids = list(range(2000))
desordenats = ids[:]
random.shuffle(desordenats)

def construir(claus):
    a = ArbreCerca()
    for c in claus:
        a.inserir(c, None)
    return a

print(timeit.timeit(lambda: construir(ids), number=5))          # ~4 s   (O(n²) total!)
print(timeit.timeit(lambda: construir(desordenats), number=5))  # ~0.03 s (O(n log n))

(Els temps exactes depenen de la teva màquina; la proporció — dos ordres de magnitud — no.) Amb claus aleatòries, l'ABC queda raonablement equilibrat de mitjana i les 2 000 insercions costen O(n log n) en total; amb claus ordenades, la inserció i-èsima recorre i nodes i el total és O(n²). I la ironia és cruel: el cas d'ús més habitual (ids autoincrementals) és exactament el pitjor cas de l'ABC. Un índex que es degrada just amb les dades que més rebrà no és un índex seriós. La solució — un arbre que es reequilibra sol a cada inserció — és la propera lliçó.

dict vs ABC: cadascú a la seva

Amb els dos índexs construïts, la comparació honesta (assumint ABC equilibrat; n elements, k resultats):

Operació dict / TaulaHash ABC
Cercar clau exacta O(1) O(log n)
Inserir / esborrar O(1) O(log n)
Recórrer en ordre O(n log n) (cal ordenar) O(n) (inordre)
Mínim / màxim O(n) O(log n)
Interval [a, b] O(n) (recórrer-ho tot i filtrar) O(altura + k)
Requisit sobre claus hashables comparables entre si

La lectura correcta no és "quin guanya" sinó "per a quina pregunta": clau exacta → hash; ordre, extrems i intervals → arbre. Els sistemes reals usen tots dos alhora — TaskFlow també: la TaulaHash de 05-02 per a obtenir(id) en O(1), i aquest ABC per a llistats i intervals. És la mateixa decisió que pren una base de dades en triar entre un índex hash i un índex d'arbre (ho veurem de prop a 06-06).

Errors Comuns i Consells

  • Validar la propietat ABC comparant només amb el pare. Un node ha de respectar tots els seus ancestres, no només l'immediat. El validador correcte propaga cotes (mínim, màxim) en descendir — és l'exercici estrella de 06-08.
  • Esborrar el cas de dos fills "a la brava". Substituir per un fill qualsevol trenca la propietat. El substitut ha de ser el successor (mínim del subarbre dret) o el predecessor (màxim de l'esquerre) — només ells encaixen entre tots dos subarbres.
  • Oblidar reassignar en cridar _esborrar. El patró node.esquerre = self._esborrar(node.esquerre, clau) funciona perquè cada crida retorna la nova arrel del subarbre. Cridar sense assignar deixa l'arbre intacte i el bug és silenciós.
  • Claus no comparables entre si. Barrejar int i str com a claus esclata (TypeError en comparar). I amb claus compostes, vigila l'ordre de la tupla: (prioritat, id) ordena per prioritat primer; (id, prioritat) és un altre índex diferent.
  • Assumir que "de mitjana s'equilibra". Cert amb claus aleatòries, fals amb claus ordenades o gairebé ordenades — que és el que produeixen els sistemes reals (ids, timestamps). No confiïs en la sort: 06-05 existeix per això.

Exercicis

Exercici 1: conte i el successor d'una clau

Afegeix a ArbreCerca (a) conte(clau) que retorni True/False, i (b) successor(clau) que retorni la menor clau de l'arbre estrictament major que la donada (tant si la donada existeix a l'arbre com si no), o None. Amb l'índex de la lliçó (després d'esborrar el 10): successor(8) → 12, successor(9) → 12, successor(20) → None.

Exercici 2: les tasques pendents de l'interval

Usant per_prioritat i interval, escriu urgents_pendents(arbre, prio_max) que retorni els títols de les tasques amb prioritat entre 1 i prio_max l'estat de les quals sigui "pendent", ordenats per (prioritat, id). El filtre d'estat s'aplica sobre el resultat de l'interval (l'arbre indexa per prioritat, no per estat — un índex per consulta).

Exercici 3: quant fa el meu arbre?

Escriu altura_abc(arbre) (reutilitza l'altura de 06-02 sobre arbre.arrel) i compara-la en dos índexs de 1 023 claus: un construït amb claus ordenades range(1023) i un altre amb les mateixes barrejades. Quina altura mínima era possible? Relaciona els tres números.

Solucions

Solució 1

    def conte(self, clau):
        # No n'hi ha prou amb "cercar(clau) is not None": un valor podria SER None.
        node = self.arrel
        while node is not None:
            if clau == node.clau:
                return True
            node = node.esquerre if clau < node.clau else node.dret
        return False

    def successor(self, clau):
        candidat = None
        node = self.arrel
        while node is not None:
            if node.clau > clau:
                candidat = node.clau        # serveix, però potser n'hi ha un de menor...
                node = node.esquerre        # ...cerquem-lo a l'esquerra
            else:
                node = node.dret            # massa petit: cap a la dreta
        return candidat

print(index.successor(9))    # 12
print(index.successor(20))   # None

Comentari: successor és el patró "millor candidat fins ara": cada node major que la clau s'apunta com a candidat i s'intenta millorar baixant a l'esquerra; els nodes menors o iguals es descarten baixant a la dreta. Un sol descens, O(altura), i sense necessitar que la clau existeixi. La pega subtil de conte és al comentari: a l'índex hem guardat alguna tasca com a None a la demo, i cercar no distingeix "no hi és" de "hi és i val None" — el mateix matís que resolia in davant de get al dict.

Solució 2

def urgents_pendents(arbre, prio_max):
    resultat = []
    for (prio, id_t), tasca in arbre.interval((1, 0), (prio_max, float("inf"))):
        if tasca["estat"] == "pendent":
            resultat.append(tasca["titol"])
    return resultat

print(urgents_pendents(per_prioritat, 2))
# ["Arreglar el CSS", "Desplegar l'API", "Optimitzar les consultes"]
# (les de prioritat 1 estaven "en curs" i "bloquejada": filtrades)

Comentari: l'arbre fa la feina grossa (acotar i ordenar, O(altura + k)) i el filtre fi va després en Python, O(k). És l'arquitectura de qualsevol consulta real: l'índex redueix l'univers, la resta es filtra. Indexar per totes les combinacions possibles no compensa; s'indexa la dimensió més selectiva.

Solució 3

import random

def altura_node(node):
    if node is None:
        return -1
    return 1 + max(altura_node(node.esquerre), altura_node(node.dret))

def altura_abc(arbre):
    return altura_node(arbre.arrel)

claus = list(range(1023))
ordenat = construir(claus)
barrejades = claus[:]
random.shuffle(barrejades)
aleatori = construir(barrejades)

print(altura_abc(ordenat))     # 1022  (degenerat: una clau per nivell)
print(altura_abc(aleatori))    # ~20-24 (varia amb la barreja)

Comentari: l'altura mínima possible amb 1 023 = 2¹⁰ − 1 nodes és 9 (l'arbre perfecte de 10 nivells, taula de 06-02). L'aleatori queda en ~20: no és perfecte, però continua sent O(log n) — la teoria diu que l'ABC aleatori fa de mitjana ≈ 1,39·log₂ n... però cap garantia no cobreix el cas ordenat, que dona 1022! Tres números, tres mons: l'ideal (9), el probable (≈20) i el catastròfic (1022). La propera lliçó garanteix quedar-se a un pas de l'ideal, arribi el que arribi.

Conclusió

L'ABC ha saldat els comptes pendents: amb una sola regla — menors a l'esquerra, majors a la dreta — TaskFlow té un índex que cerca en O(altura), llista en ordre amb l'inordre (el misteri de 06-03, resolt), troba mínim i successor d'un cop d'ull i respon intervals amb poda, inclosa la consulta "prioritat entre 1 i 3" que va humiliar el hash, via la clau composta (prioritat, id). També saps esborrar sense trencar res (fulla, un fill, i el cas del successor) i coneixes la lletra petita del contracte: tot és O(altura), i l'altura depèn de l'ordre d'arribada. Amb ids autoincrementals — el pa de cada dia — l'ABC degenera en llista i els seus O(log n) s'evaporen, com acabes de mesurar. La propera lliçó ho arregla d'arrel: l'arbre AVL detecta el desequilibri a cada inserció amb un número per node i el corregeix amb rotacions locals, garantint O(log n) passi el que passi. L'índex de TaskFlow és a una lliçó de tornar-se indestructible.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2026. Tots els drets reservats