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

Exercicis amb Arbres

Següent ►
►

Mòdul carregat: arbres genèrics i la seva terminologia (06-01), arbres binaris i els seus comptes (06-02), els quatre recorreguts (06-03), l'ABC amb intervals (06-04), l'AVL que no degenera (06-05), l'arbre B de les bases de dades (06-06) i el monticle que va obrir heapq (06-07). Aquesta lliçó no afegeix teoria: és el gimnàs on aquestes peces es combinen sobre TaskFlow en sis exercicis progressius — d'escalfar amb recorreguts a tres clàssics absoluts d'entrevista tècnica (validar un ABC amb la seva trampa cèlebre, reconstruir un arbre des dels seus recorreguts, i el top-k amb monticle de mida k). Intenta cadascun seriosament abans de mirar la solució: l'enunciat inclou pistes, i barallar-se deu minuts amb un arbre ensenya més que llegir deu solucions.

Contingut

  1. Exercici 1: radiografia de l'arbre de projectes (altura i recompte)
  2. Exercici 2: auditar la propietat ABC (amb la trampa clàssica)
  3. Exercici 3: la k-èsima tasca més prioritària (inordre parcial)
  4. Exercici 4: pressupost per subarbre (postordre)
  5. Exercici 5: reconstruir un arbre des de preordre + inordre
  6. Exercici 6: top-k urgents amb monticle de mida k
  7. Solucions comentades

Les dades de partida

Tots els exercicis usen les classes del mòdul: NodeArbre (06-01, amb valor i llista fills), NodeBinari (06-02), ArbreCerca/NodeABC (06-04) i Monticle (06-07). Per als dos primers exercicis sobre arbre genèric, aquest projecte:

def T(id, titol, prioritat, hores):
    return {"id": id, "titol": titol, "prioritat": prioritat,
            "estat": "pendent", "hores": hores}

projecte = NodeArbre(T(1, "Llançar TaskFlow 2.0", 1, 8))
backend = projecte.afegir_fill(NodeArbre(T(2, "Backend", 1, 5)))
frontend = projecte.afegir_fill(NodeArbre(T(3, "Frontend", 2, 3)))
docs = projecte.afegir_fill(NodeArbre(T(4, "Documentació", 3, 6)))
api = backend.afegir_fill(NodeArbre(T(5, "API v2", 1, 12)))
bd = backend.afegir_fill(NodeArbre(T(6, "Migrar la BD", 2, 9)))
api.afegir_fill(NodeArbre(T(7, "Autenticació", 1, 4)))
frontend.afegir_fill(NodeArbre(T(8, "Redisseny del panell", 2, 10)))
graph TD
    A["1: Llançar 2.0 (8h)"] --> B["2: Backend (5h)"]
    A --> C["3: Frontend (3h)"]
    A --> D["4: Documentació (6h)"]
    B --> E["5: API v2 (12h)"]
    B --> F["6: Migrar la BD (9h)"]
    E --> G["7: Autenticació (4h)"]
    C --> H["8: Redisseny del panell (10h)"]

Exercicis

Exercici 1: radiografia de l'arbre de projectes

Escriu dues funcions sobre l'arbre genèric: altura_generic(node) (altura del subarbre, amb la convenció del mòdul: buit = −1, fulla = 0) i comptar_per_nivell(arrel) (un dict nivell → nombre de nodes). Per a projecte han de donar altura 3 i {0: 1, 1: 3, 2: 3, 3: 1}. Pista: la primera demana postordre (l'altura puja de fills a pares); la segona surt sola amb el recorregut per nivells de 06-03 o amb un preordre que arrossegui la profunditat.

Exercici 2: auditar la propietat ABC

Escriu es_abc(node) que decideixi si un arbre binari (nodes amb clau) compleix la propietat de cerca. Comença escrivint la versió incorrecta — la que només compara cada node amb els seus fills directes — i troba un arbre que l'enganyi; després escriu la correcta propagant cotes (minim, maxim). Arbre de prova obligatori:

graph TD
    A((10)) --> B((5))
    A --> C((15))
    B --> D((3))
    B --> E((12))

Cada pare és major que el seu fill esquerre i menor que el dret... i tanmateix no és un ABC. Per què?

Exercici 3: la k-èsima tasca més prioritària

Sobre l'índex AVL/ABC per clau (prioritat, id) de 06-04/06-05, escriu k_esima(arbre, k) que retorni la tasca que ocupa la posició k (1-indexada) en ordre d'urgència — sense materialitzar la llista completa: l'inordre s'ha d'aturar tan bon punt troba la k-èsima. Pista: un comptador que viatja per la recursió i un valor de retorn que talla l'exploració (el mateix patró de parada primerenca que profunditat_de a 06-01).

Exercici 4: pressupost per subarbre

Sobre l'arbre projecte, escriu pressupostar(node) que retorni un dict id → hores acumulades del seu subarbre (les pròpies més tots els descendents) en una sola passada O(n). Per a l'arrel ha de sortir 57; per a Backend (id 2), 30. Pista: postordre pur — és hores_acumulades de 06-03 generalitzada a n fills, guardant a més cada resultat intermedi.

Exercici 5: reconstruir un arbre des de preordre + inordre

Un company va exportar un arbre binari de TaskFlow com dues llistes: preordre = [10, 6, 3, 8, 15, 12, 20] i inordre = [3, 6, 8, 10, 12, 15, 20]. Escriu reconstruir(preordre, inordre) que retorni l'arrel de l'únic arbre binari compatible amb totes dues (claus sense duplicats). Pistes: la primera clau del preordre és sempre l'arrel (06-03); la seva posició a l'inordre parteix aquesta llista en subarbre esquerre i dret; recursió sobre les meitats. Pregunta extra: per què el preordre tot sol no basta?

Exercici 6: top-k urgents amb monticle de mida k

TaskFlow arxiva centenars de milers de tasques i el tauler només mostra les k més urgents (menor (prioritat, id)). Ordenar-ho tot costa O(n log n) i materialitza el que no es veu. Escriu top_k(tasques, k) — amb tasques un iterable de dicts — que ho faci en O(n log k) mantenint un monticle de mida k com a màxim. Pista: si el heap és un min-heap, què ha de viure a la seva arrel per poder decidir en O(1) si una tasca nova entra al top? (Repassa la nota max-heap de 06-07: negar és la teva amiga.)

Solucions

Solució 1: radiografia de l'arbre

def altura_generic(node):
    if node is None:
        return -1
    if not node.fills:                     # fulla: altura 0
        return 0
    return 1 + max(altura_generic(f) for f in node.fills)

from collections import deque

def comptar_per_nivell(arrel):
    recompte = {}
    cua = deque([(arrel, 0)])              # viatgem amb la profunditat, com a 06-03
    while cua:
        node, nivell = cua.popleft()
        recompte[nivell] = recompte.get(nivell, 0) + 1
        for f in node.fills:
            cua.append((f, nivell + 1))
    return recompte

print(altura_generic(projecte))      # 3
print(comptar_per_nivell(projecte))  # {0: 1, 1: 3, 2: 3, 3: 1}

Comentari: altura_generic generalitza l'altura binària de 06-02 canviant max(esq, dret) per max sobre la llista de fills — i necessita el cas fulla explícit, perquè max() sobre una seqüència buida llança ValueError (a la versió binària ho tapava el -1 dels fills None). La informació flueix de fills a pares: postordre. comptar_per_nivell flueix a l'inrevés (la profunditat baixa de pares a fills) i per això hi encaixa el BFS amb tupla (node, nivell) — el deque del mòdul 4 una vegada més; amb defaultdict(int) del mòdul 5 la línia del recompte quedaria encara més neta. Dues preguntes, dues direccions del flux, dos recorreguts: triar recorregut és respondre "cap a on flueix la informació?".

Solució 2: auditar la propietat ABC

La versió ingènua i el seu contraexemple:

def es_abc_MAL(node):
    """INCORRECTA: només compara amb els fills directes."""
    if node is None:
        return True
    if node.esquerre and node.esquerre.clau >= node.clau:
        return False
    if node.dret and node.dret.clau <= node.clau:
        return False
    return es_abc_MAL(node.esquerre) and es_abc_MAL(node.dret)

# L'arbre de l'enunciat: 10 -> (5 -> (3, 12), 15)
arrel = NodeBinari(10); arrel.clau = 10        # o usa NodeABC directament
# ... (construcció anàloga amb clau a cada node)
print(es_abc_MAL(arrel))   # True  <- mentida!

El 12 és fill dret del 5 (12 > 5: la versió ingènua aplaudeix) però viu al subarbre esquerre del 10, on tot ha de ser < 10. La propietat ABC parla de subarbres sencers, no de parelles pare-fill — l'advertència repetida des de 06-04, i la diferència exacta amb el heap, la propietat del qual sí que és local (per això es_min_heap de 06-07 comparava només amb el pare i era correcta). La versió bona propaga el rang permès:

def es_abc(node, minim=float("-inf"), maxim=float("inf")):
    """Cada descens ESTRENY l'interval (minim, maxim) permès."""
    if node is None:
        return True
    if not (minim < node.clau < maxim):
        return False
    return (es_abc(node.esquerre, minim, node.clau) and
            es_abc(node.dret, node.clau, maxim))

print(es_abc(arrel))   # False: en arribar al 12, l'interval era (-inf, 10) — però 5 < 12

Comentari: en baixar a l'esquerra, el node actual es converteix en sostre (maxim); a la dreta, en terra (minim). El 12 s'avalua amb l'interval (5, 10) heretat dels seus dos ancestres i suspèn. Una passada O(n), i el candidat número u a pregunta d'entrevista sobre arbres. Alternativa igual de vàlida: generar l'inordre i comprovar que surt estrictament creixent — mateix cost, tot i que la de cotes talla abans al primer error.

Solució 3: la k-èsima tasca

def k_esima(arbre, k):
    def inordre_parcial(node, restants):
        """Retorna (tasca trobada o None, quantes en queden per saltar)."""
        if node is None:
            return None, restants
        # 1) primer, tot el subarbre esquerre (els més urgents)
        trobada, restants = inordre_parcial(node.esquerre, restants)
        if trobada is not None:
            return trobada, 0                      # ja hi és: propagar sense mirar més
        # 2) el mateix node consumeix un lloc
        restants -= 1
        if restants == 0:
            return node.valor, 0
        # 3) només si encara falta, el subarbre dret
        return inordre_parcial(node.dret, restants)

    return inordre_parcial(arbre.arrel, k)[0]

# Amb l'índex de 30 tasques de 06-05 (prioritats (i % 3) + 1):
print(k_esima(index, 1)["id"])    # 3  (la primera de prioritat 1)
print(k_esima(index, 11)["id"])   # 1  (la primera de prioritat 2)

Comentari: és l'inordre de 06-03 amb dos afegits: un comptador restants que viatja i es descompta al pas "visitar node", i la propagació immediata de la troballa que evita explorar els subarbres pendents — la parada primerenca de profunditat_de (06-01). Cost: O(altura + k) — per a k petit sobre un AVL, logarítmic, davant de l'O(n) de materialitzar l'inordre() complet i indexar. Nota d'arquitecte: els arbres de les llibreries serioses ofereixen aquesta operació en O(log n) pur guardant a cada node la mida del seu subarbre (per saltar subarbres sencers comptant en lloc de recorrent); la idea d'anotar els nodes amb dades agregades és exactament la del següent exercici.

Solució 4: pressupost per subarbre

def pressupostar(node, resultat=None):
    """dict id -> hores acumulades del subarbre. Una passada, O(n)."""
    if resultat is None:
        resultat = {}
    total = node.valor["hores"]                    # les hores pròpies...
    for f in node.fills:
        pressupostar(f, resultat)                  # (els fills omplen el que és seu)
        total += resultat[f.valor["id"]]           # ...més l'acumulat de cada fill
    resultat[node.valor["id"]] = total
    return resultat

pressupost = pressupostar(projecte)
print(pressupost[1])   # 57  (tot el llançament)
print(pressupost[2])   # 30  (Backend: 5 + (12+4) + 9)
print(pressupost[5])   # 16  (API v2: 12 + 4)

Comentari: postordre de manual — un pare no pot conèixer el seu total fins que cada fill ha dipositat el seu a resultat, així que la recursió sobre els fills va abans de la suma final. La finesa és reutilitzar els acumulats dels fills (resultat[f.valor["id"]]) en lloc de recalcular el seu subarbre: cada node es visita una vegada i el cost és O(n); la variant ingènua que crida "sumar subarbre" per a cada node repeteix feina i escala a O(n²) en arbres profunds — la mateixa trampa altura-per-node que vam evitar a _altura_i_validesa (06-05). Amb aquest dict, el gestor de TaskFlow respon "quant costa Backend amb tot el que en penja?" en O(1): un índex hash del mòdul 5 alimentat per un recorregut del mòdul 6, treballant en equip.

Solució 5: reconstruir des de preordre + inordre

def reconstruir(preordre, inordre):
    if not preordre:
        return None
    arrel = NodeBinari(preordre[0])            # preordre: l'arrel SEMPRE va primer
    tall = inordre.index(preordre[0])          # la seva posició parteix l'inordre en dos
    esq_in, dret_in = inordre[:tall], inordre[tall + 1:]
    esq_pre = preordre[1:1 + len(esq_in)]      # el preordre es parteix per MIDA
    dret_pre = preordre[1 + len(esq_in):]
    arrel.esquerre = reconstruir(esq_pre, esq_in)
    arrel.dret = reconstruir(dret_pre, dret_in)
    return arrel

arbre = reconstruir([10, 6, 3, 8, 15, 12, 20], [3, 6, 8, 10, 12, 15, 20])
# Verificació: regenerar tots dos recorreguts amb les funcions de 06-03
pre, ino = [], []
def rec_pre(n):
    if n: pre.append(n.valor); rec_pre(n.esquerre); rec_pre(n.dret)
def rec_ino(n):
    if n: rec_ino(n.esquerre); ino.append(n.valor); rec_ino(n.dret)
rec_pre(arbre); rec_ino(arbre)
print(pre)   # [10, 6, 3, 8, 15, 12, 20]  — coincideix
print(ino)   # [3, 6, 8, 10, 12, 15, 20]  — coincideix: és l'arbre de 06-03/06-04

Comentari: cada recorregut aporta la meitat de la informació — el preordre diu qui mana (el seu primer element és l'arrel), l'inordre diu qui queda a cada costat (l'anterior a l'arrel és el seu subarbre esquerre). Sabuda la mida del costat esquerre per l'inordre, el preordre es parteix en les mateixes proporcions i la recursió fa la resta. Resposta a la pregunta extra: el preordre sol no determina l'arbre — [2, 1] pot ser "2 amb fill esquerre 1" o "2 amb fill dret 1"; cal l'inordre per desambiguar (o saber que l'arbre és un ABC, i en aquest cas l'inordre és gratis: és el preordre ordenat!). Afinament de professional: inordre.index(...) és O(n) a cada crida (O(n²) total en el pitjor cas); amb un dict valor → posició construït una vegada — el mòdul 5 al rescat una altra vegada — la reconstrucció sencera baixa a O(n).

Solució 6: top-k urgents

def top_k(tasques, k):
    """Les k tasques amb menor (prioritat, id), ordenades. O(n log k)."""
    heap = Monticle()           # min-heap de claus NEGADES => max-heap d'urgència
    for t in tasques:
        clau = (-t["prioritat"], -t["id"], t)      # negar: la PITJOR del top queda a l'arrel
        if len(heap) < k:
            heap.inserir(clau)
        elif clau > heap.veure_minim():            # més urgent que la pitjor guardada?
            heap.extreure_minim()                  # fora la pitjor...
            heap.inserir(clau)                     # ...dins la nova. O(log k)
    resultat = []
    while len(heap):
        resultat.append(heap.extreure_minim()[2])  # surten de pitjor a millor...
    resultat.reverse()                             # ...invertir: de millor a pitjor
    return resultat

import random
tasques = [{"id": i, "titol": f"Tasca {i}", "prioritat": random.randint(1, 5),
            "estat": "pendent"} for i in range(1, 100001)]
random.shuffle(tasques)
for t in top_k(tasques, 5):
    print(t["prioritat"], t["id"])    # les 5 de prioritat 1 amb menor id, en ordre

Comentari: la idea que cal interioritzar — per retenir els k menors, el monticle guarda com a molt k elements i la seva arrel és el pitjor dels bons (el major del top actual), gràcies a la negació de claus de 06-07: min-heap de negats = max-heap d'originals. Així, cada tasca nova es compara en O(1) contra aquest llindar viu: si no el millora, ni entra (el cas massivament més freqüent); si el millora, un extreure + inserir en O(log k). Total O(n log k) amb memòria O(k): amb n = 100 000 i k = 5, quatre comptes de no res davant d'ordenar cent mil tasques per pintar-ne cinc. És el patró exacte de qualsevol "top 10" sobre un flux que no cap (o no compensa) ordenar — i la parella (-prioritat, -id) garanteix a més el desempat correcte: entre iguals en prioritat guanya l'id menor.

Errors Comuns i Consells

  • Validar l'ABC contra el pare i quedar-se tan ample (exercici 2): l'error està tan estès que els entrevistadors construeixen a propòsit l'arbre del 12. Cotes heretades o inordre creixent; no hi ha tercera via.
  • Recalcular subarbres en lloc de reutilitzar acumulats (exercicis 1 i 4): cridar "altura/suma del subarbre" dins de cada node dispara el cost a O(n²). La informació que flueix de fills a pares es calcula una vegada, en postordre, i es guarda.
  • Oblidar la parada primerenca a les cerques recursives (exercici 3): sense propagar la troballa, el recorregut continua visitant subarbres sencers per a res — correcte però O(n), que era just el prohibit.
  • Partir malament les llistes en reconstruir (exercici 5): l'inordre es parteix per posició de l'arrel; el preordre, per mida del costat esquerre. Creuar els criteris produeix arbres fantasma que després no reprodueixen els recorreguts — verifica sempre regenerant-los.
  • Usar un min-heap de claus sense negar per al top-k de menors (exercici 6): et deixa a l'arrel el millor, que és exactament el que no vols expulsar. Per retenir els k menors s'expulsa el major: max-heap (negació) obligatori.
  • Consell final: els sis exercicis caben en un mateix fitxer amb les classes del mòdul; guarda'l. El validador, la reconstrucció i el top-k són els tres arbres més preguntats a les entrevistes, i pressupostar + k_esima tornaran com a peces dels projectes del mòdul 8.

Conclusió

Fi del mòdul 6, i el botí és seriós: TaskFlow té jerarquia real de projectes amb pressupostos per subarbre, un índex ordenat per (prioritat, id) que respon intervals i k-èsims sense despentinar-se (i que, gràcies a l'AVL, no es degrada encara que els ids arribin ordenats), la certesa de què fa la seva base de dades per sota (B+), i una safata d'urgències O(log n) el motor de la qual ja no té secrets. I tu tens el criteri: la pregunta decideix l'estructura — clau exacta al hash, ordre i intervals a l'arbre equilibrat, "el següent més urgent" al monticle, disc a l'arbre B. Però fixa't en el supòsit silenciós que ha sostingut tot el mòdul: cada node té exactament un pare. La subtasca pertany a una tasca, la tasca a una categoria, i aquesta unicitat és la que va fer possibles els recorreguts sense visitats, la recursió neta, l'equilibri. Ara pensa en les dependències reals de TaskFlow: "desplegar l'API" no pot començar fins a acabar "Migrar la BD" i "Configurar el servidor" — una tasca que depèn de diverses alhora, i potser dues més depenen d'ella. Això ja no és un arbre: els camins es creuen, apareixen els cicles possibles (A depèn de B que depèn d'A?), i la jerarquia es queda curta. Cal l'estructura més general del curs, aquella de la qual l'arbre era només un cas particular ben educat: el graf. Al mòdul 7 ens esperen la seva representació, el BFS i el DFS que fa dos mòduls que sembrem — amb el conjunt visitats promès al mòdul 5 per fi en acció — i els camins mínims. Ens veiem entre nodes i arestes.

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