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

HOME

Tanquem el mòdul 5 amb una confessió: el hash és imbatible quan li dones una clau exacta, però emmudeix davant de preguntes com "dona'm les tasques ordenades per id" o "totes les de prioritat entre 1 i 3". Les seves claus estan escampades a propòsit, sense noció de veïnatge ni d'ordre. Per respondre a això necessitem una estructura que mantingui les dades organitzades, i aquesta estructura és l'arbre. En aquesta lliçó aprendràs què és un arbre, en dominaràs el vocabulari (arrel, fulla, altura, profunditat...), construiràs la classe NodeArbre per a arbres genèrics i la faràs servir per modelar una cosa que TaskFlow demanava a crits: la jerarquia projectes → categories → tasques → subtasques. Tot el que ve en aquest mòdul — arbres binaris, ABC, AVL, arbres B, monticles — es recolza en el vocabulari i la intuïció d'aquesta lliçó.

Contingut

Del hash a l'arbre: per què necessitem jerarquia i ordre
Què és un arbre: definició i propietats
Terminologia: el vocabulari que farem servir tot el mòdul
Arbres genèrics en Python: la classe NodeArbre
TaskFlow jeràrquic: projectes, categories, tasques i subtasques
Recórrer un arbre genèric amb recursió
Arbres a la vida real

Del hash a l'arbre: per què necessitem jerarquia i ordre

Repassem què sap fer cada estructura que ja tens a TaskFlow:

Pregunta	Estructura que la respon	Cost
"Dona'm la tasca amb id T-042"	`TaulaHash` / `dict` (mòdul 5)	O(1)
"Quina és la següent tasca a processar?"	`Cua` (mòdul 4)	O(1)
"Desfés l'últim canvi"	`Pila` (mòdul 3)	O(1)
"Dona'm les tasques ordenades per id"	cap (el hash escampa)	—
"Tasques amb prioritat entre 1 i 3"	cap (no hi ha veïnatge)	—
"La subtasca X, de quin projecte penja?"	cap (tot és pla)	—

Les tres últimes files comparteixen una cosa: demanen relacions entre elements (ordre, interval, pertinença jeràrquica), no un element aïllat. Totes les estructures que coneixes fins ara són lineals: cada element té, com a molt, un anterior i un següent. Els arbres trenquen aquesta linealitat: un element pot tenir diversos següents. Aquesta petita diferència ho canvia tot.

Aquest mòdul atacarà les tres mancances per ordre: la jerarquia avui mateix (arbres genèrics), l'ordre i els intervals a 06-04 (arbres binaris de cerca), i de passada saldarem a 06-07 la promesa del mòdul 4: obrir heapq per dins.

Què és un arbre: definició i propietats

Un arbre és una estructura de dades jeràrquica formada per nodes connectats per arestes, que compleix tres propietats:

Hi ha exactament un node arrel, que no té pare.
Tot node que no és l'arrel té exactament un pare.
No hi ha cicles: seguint arestes mai no tornes a un node ja visitat.

Conseqüència útil: un arbre amb n nodes té exactament n - 1 arestes (cada node llevat de l'arrel aporta l'aresta que l'uneix al seu pare). I entre l'arrel i qualsevol node existeix un únic camí — no hi ha rutes alternatives.

Un apunt que reprendrem al mòdul 7: formalment, un arbre és un cas particular de graf (connex i sense cicles). Ho deixem aquí com a menció; als grafs generals un node podrà tenir diversos "pares" i hi haurà cicles, i això exigirà tècniques noves.

graph TD
    A["TaskFlow (arrel)"] --> B["Projecte: Web"]
    A --> C["Projecte: App mòbil"]
    B --> D["Backend"]
    B --> E["Frontend"]
    C --> F["iOS"]
    D --> G["T-01: API de tasques"]
    D --> H["T-02: Base de dades"]
    E --> I["T-03: Pantalla de login"]

Fixa't que els arbres en informàtica es dibuixen al revés que els botànics: l'arrel a dalt i les fulles a baix. És pura convenció, però és universal.

Terminologia: el vocabulari que farem servir tot el mòdul

Aquest vocabulari apareixerà a les set lliçons següents; val la pena fixar-lo bé. Sobre el diagrama anterior:

Terme	Definició	Exemple al diagrama
Arrel	L'únic node sense pare	`TaskFlow`
Pare	El node del qual en penja un altre directament	`Backend` és pare de `T-01`
Fill	Node que penja directament d'un altre	`Web` i `App mòbil` són fills de l'arrel
Germans	Nodes que comparteixen pare	`T-01` i `T-02`
Fulla	Node sense fills	`T-01`, `T-02`, `T-03`, `iOS`
Node intern	Node amb almenys un fill	`Web`, `Backend`, `Frontend`...
Subarbre	Un node qualsevol juntament amb tots els seus descendents	`Backend` amb `T-01` i `T-02`
Profunditat d'un node	Nre. d'arestes des de l'arrel fins a ell	profunditat de `T-01` = 3
Nivell	Conjunt de nodes a la mateixa profunditat (l'arrel és al nivell 0)	nivell 1 = {`Web`, `App mòbil`}
Altura de l'arbre	Profunditat màxima de qualsevol node	3 (la de `T-01`)
Grau d'un node	El seu nombre de fills	grau de `Web` = 2

Dos matisos que confonen tothom al principi:

La profunditat es mesura des de l'arrel cap avall (és pròpia de cada node); l'altura es mesura des de les fulles cap amunt (l'altura d'un node és la del camí més llarg fins a una fulla sota seu; la de l'arbre és l'altura de l'arrel). L'arrel té profunditat 0 i altura màxima; una fulla té altura 0 i profunditat variable.
La paraula subarbre és la clau de la recursió: cada fill d'un node és, al seu torn, l'arrel d'un arbre complet. Un arbre és "un node + una llista d'arbres més petits". Aquesta definició recursiva és la que fa que gairebé tots els algorismes d'aquest mòdul siguin recursius de forma natural — la recursió del mòdul 3 treballarà de valent aquí.

Arbres genèrics en Python: la classe `NodeArbre`

En un arbre genèric (o n-ari) cada node pot tenir qualsevol nombre de fills. La implementació natural: un valor i una llista de fills. Compara-la amb el Node del mòdul 2 — allà seguent era una referència; aquí fills és una llista de referències. Aquest és tot el salt del lineal al jeràrquic.

class NodeArbre:
    """Un node d'arbre generic: un valor i qualsevol nombre de fills."""

    def __init__(self, valor):
        self.valor = valor      # aquí hi guardarem el dict de la tasca, o un text
        self.fills = []         # llista de NodeArbre (buida => és una fulla)

    def afegir_fill(self, node_fill):
        """Penja un altre node com a fill d'aquest. Retorna el fill
        per poder encadenar la construcció còmodament."""
        self.fills.append(node_fill)
        return node_fill

    def es_fulla(self):
        return len(self.fills) == 0

Punt per punt:

valor pot ser qualsevol cosa: a TaskFlow serà de vegades un text (nom de projecte o categoria) i de vegades el dict d'una tasca.
fills comença com a llista buida: tot node neix fulla i deixa de ser-ho quan rep fills.
afegir_fill retorna el fill afegit: així podem escriure backend = projecte.afegir_fill(NodeArbre("Backend")) i continuar penjant coses de backend.
No hi ha cap classe "Arbre" embolcallant: n'hi ha prou de guardar l'arrel. Des d'ella s'hi arriba a tot, igual que des de self.cap s'arribava a tota la LlistaEnllacada.

TaskFlow jeràrquic: projectes, categories, tasques i subtasques

Fins avui, TaskFlow guardava les tasques en estructures planes: una llista enllaçada, una cua, una taula hash. Però qualsevol usuari real organitza la seva feina en nivells: projectes que contenen categories, que contenen tasques, que al seu torn tenen subtasques (recordes les subtasques niades del mòdul 3, que ens van provocar un RecursionError? Eren un arbre demanant permís per existir). Construïm-lo:

def crear_tasca(id, titol, prioritat, estat="pendent"):
    """Fàbrica de tasques: el mateix dict de sempre."""
    return {"id": id, "titol": titol, "prioritat": prioritat, "estat": estat}

# L'arrel: l'aplicació sencera
arrel = NodeArbre("TaskFlow")

# Nivell 1: projectes
web = arrel.afegir_fill(NodeArbre("Projecte: Web"))
mobil = arrel.afegir_fill(NodeArbre("Projecte: App mòbil"))

# Nivell 2: categories dins del projecte Web
backend = web.afegir_fill(NodeArbre("Backend"))
frontend = web.afegir_fill(NodeArbre("Frontend"))

# Nivell 3: tasques (els dict de sempre, ara com a valor d'un node)
t_api = backend.afegir_fill(NodeArbre(crear_tasca("T-01", "API de tasques", 1)))
backend.afegir_fill(NodeArbre(crear_tasca("T-02", "Dissenyar la base de dades", 2)))
frontend.afegir_fill(NodeArbre(crear_tasca("T-03", "Pantalla de login", 2)))

# Nivell 4: subtasques de T-01
t_api.afegir_fill(NodeArbre(crear_tasca("T-01a", "Endpoint GET /tasques", 1)))
t_api.afegir_fill(NodeArbre(crear_tasca("T-01b", "Endpoint POST /tasques", 1)))

Observa l'elegància: no hem escrit ni una línia nova d'estructura per passar de 2 a 4 nivells. La llista de fills no distingeix entre "projecte que conté categories" i "tasca que conté subtasques"; la jerarquia pot créixer tan endins com l'usuari vulgui.

Recórrer un arbre genèric amb recursió

De què serveix l'arbre si no el podem consultar? Els recorreguts sistemàtics (amb nom, ordre garantit i versió iterativa) són el tema de 06-03; aquí veurem el patró bàsic del qual deriven tots: processar el node i recursar sobre cada fill. Primer, comptar nodes:

def comptar_nodes(node):
    """Quants nodes hi ha al subarbre que penja de `node`."""
    if node is None:
        return 0
    total = 1                         # aquest node compta
    for fill in node.fills:
        total += comptar_nodes(fill)  # més tot el que penja de cada fill
    return total

print(comptar_nodes(arrel))   # 10

Llegeix la funció a la llum de la definició recursiva d'arbre: "la mida d'un arbre és 1 (la seva arrel) més la suma de les mides dels seus subarbres". El cas base (None → 0) i les crides sobre estructures estrictament més petites garanteixen que acaba — exactament els dos requisits que vam estudiar al mòdul 3. Com que no hi ha cicles i cada node té un sol pare, cada node es visita exactament una vegada: cost O(n).

Ara una cosa més vistosa: imprimir l'arbre amb indentació, com fa tree a la terminal. La profunditat de cada node es converteix en sagnia:

def mostrar(node, profunditat=0):
    """Imprimeix el subarbre amb indentació proporcional a la profunditat."""
    if isinstance(node.valor, dict):                     # és una tasca
        etiqueta = f"[{node.valor['id']}] {node.valor['titol']}"
    else:                                                # és un text (projecte/categoria)
        etiqueta = node.valor
    print("    " * profunditat + etiqueta)
    for fill in node.fills:
        mostrar(fill, profunditat + 1)                   # els fills, un nivell més endins

mostrar(arrel)

Sortida:

TaskFlow
    Projecte: Web
        Backend
            [T-01] API de tasques
                [T-01a] Endpoint GET /tasques
                [T-01b] Endpoint POST /tasques
            [T-02] Dissenyar la base de dades
        Frontend
            [T-03] Pantalla de login
    Projecte: App mòbil

El paràmetre profunditat viatja a cada crida recursiva incrementat en 1: és la traducció directa de la definició "profunditat = nre. d'arestes des de l'arrel". I una nota d'honestedat que ja coneixes del mòdul 3: si l'arbre fos absurdament profund (milers de nivells), la pila de crides de Python protestaria amb RecursionError; allà vam aprendre a convertir la recursió en iteració amb una pila explícita, i a 06-03 aplicarem aquesta tècnica als recorreguts.

Arbres a la vida real

Els arbres no són un invent acadèmic; probablement en fas servir uns quants cada minut:

El sistema de fitxers: /home/joan/projectes/taskflow/main.py és un camí arrel→fulla. Les carpetes són nodes interns, els fitxers són fulles, i tree és la nostra funció mostrar.
El DOM d'una pàgina web: <html> és l'arrel, i cada etiqueta niada un fill. Quan JavaScript fa element.children està llegint una llista fills com la nostra.
Organigrames: la direcció general com a arrel, departaments com a subarbres. "Quanta gent depèn (directament o indirectament) de X?" és comptar_nodes(X) - 1.
Menús i categories de qualsevol aplicació o botiga en línia — exactament el nostre TaskFlow jeràrquic.
Sintaxi dels llenguatges: el mateix intèrpret de Python converteix el teu codi en un arbre (AST) abans d'executar-lo.

Quan a la teva feina vegis dades amb relació "conté" o "depèn d'un únic superior", pensa en arbre.

Errors Comuns i Consells

Confondre altura i profunditat. Regla mnemotècnica: la profunditat es mesura des de l'arrel (a quants pisos sota la superfície ets?); l'altura des de les fulles (quant fas des del terra?). A les entrevistes ho pregunten constantment.
Oblidar el cas base a les funcions recursives. Sense l'if node is None: return 0, cridar comptar_nodes(None) (per exemple, sobre un arbre buit) esclata amb AttributeError. Tot algorisme d'arbres ha de decidir què fer amb l'arbre buit.
Crear cicles per accident. Si afegeixes un node com a fill d'un dels seus propis descendents, ja no tens un arbre: els recorreguts recursius no acabaran mai. Les estructures amb cicles legítims existeixen — són els grafs del mòdul 7 — però requereixen altres tècniques.
Compartir la llista de fills entre nodes. Un clàssic de Python: definir def __init__(self, valor, fills=[]) amb llista mutable per defecte fa que tots els nodes comparteixin la mateixa llista. Inicialitza sempre self.fills = [] dins de l'__init__.
Consell: guarda sempre una referència a l'arrel en una variable estable. Perdre l'arrel d'un arbre és perdre l'arbre sencer, igual que perdre cap a la llista enllaçada.

Exercicis

Exercici 1: comptar només les tasques

Escriu comptar_tasques(node) que retorni quants nodes del subarbre contenen una tasca (és a dir, el valor dels quals és un dict), ignorant projectes i categories. Sobre l'arbre de la lliçó ha de retornar 5.

Exercici 2: profunditat d'una tasca

Escriu profunditat_de(node, id_cercat) que retorni la profunditat a què es troba la tasca amb aquest id (l'arrel té profunditat 0), o None si no existeix. profunditat_de(arrel, "T-01a") ha de retornar 4.

Exercici 3: fulles de l'arbre

Escriu fulles(node) que retorni la llista de valors de totes les fulles del subarbre. A l'arbre de la lliçó, Projecte: App mòbil és fulla (encara no té contingut) i també ho són les tasques sense subtasques.

Solucions

Solució 1

def comptar_tasques(node):
    if node is None:
        return 0
    total = 1 if isinstance(node.valor, dict) else 0
    for fill in node.fills:
        total += comptar_tasques(fill)
    return total

print(comptar_tasques(arrel))   # 5  (T-01, T-02, T-03, T-01a, T-01b)

Comentari: és comptar_nodes amb l'"1" condicionat. L'estructura del recorregut no canvia — canvia què fem a cada node. Aquest patró (recorregut fix, acció variable) es repetirà tot el mòdul.

Solució 2

def profunditat_de(node, id_cercat, profunditat=0):
    if node is None:
        return None
    if isinstance(node.valor, dict) and node.valor["id"] == id_cercat:
        return profunditat
    for fill in node.fills:
        resultat = profunditat_de(fill, id_cercat, profunditat + 1)
        if resultat is not None:      # ja trobat en aquest subarbre: parar
            return resultat
    return None

print(profunditat_de(arrel, "T-01a"))  # 4
print(profunditat_de(arrel, "T-99"))   # None

Comentari: el detall important és l'if resultat is not None: return resultat — tan bon punt un subarbre troba la tasca, deixem d'explorar els germans. Sense ell, la funció continuaria cercant i retornaria None encara que hagués trobat l'objectiu abans. Fixa't també que cercar en un arbre genèric és O(n): sense cap regla sobre on és cada valor, cal mirar potencialment tots els nodes. A 06-04 afegirem aquesta regla i la cerca baixarà a O(altura).

Solució 3

def fulles(node):
    if node is None:
        return []
    if node.es_fulla():
        return [node.valor]
    resultat = []
    for fill in node.fills:
        resultat.extend(fulles(fill))
    return resultat

for v in fulles(arrel):
    print(v["id"] if isinstance(v, dict) else v)
# T-01a, T-01b, T-02, T-03, Projecte: App mòbil

Comentari: aquí el cas base útil no és None sinó es_fulla(): una fulla es retorna a si mateixa; un node intern delega i concatena. Que Projecte: App mòbil aparegui entre les fulles és correcte i revelador: "fulla" és una propietat estructural (no tenir fills), no semàntica (ser una tasca).

Conclusió

Ja tens el vocabulari (arrel, fulla, pare, subarbre, altura, profunditat, nivell) i l'eina (NodeArbre amb la seva llista de fills) que sostindran tot el mòdul, i TaskFlow ha guanyat per fi la seva jerarquia de projectes → categories → tasques → subtasques — amb recorreguts recursius que reutilitzen el que vas aprendre al mòdul 3. Però fixa't en la solució de l'exercici 2: cercar en aquest arbre continua costant O(n), i les preguntes d'ordre i interval que va deixar pendents el hash continuen sense resposta. El camí cap a la resposta comença restringint l'arbre: si cada node té com a màxim dos fills, amb posició distingida (esquerre i dret), apareixen propietats matemàtiques potentíssimes — i sobre elles construirem la cerca en O(log n). Aquest arbre restringit és l'arbre binari, protagonista de la lliçó següent.

Introducció als Arbres

Contingut

Del hash a l'arbre: per què necessitem jerarquia i ordre

Què és un arbre: definició i propietats

Terminologia: el vocabulari que farem servir tot el mòdul

Arbres genèrics en Python: la classe `NodeArbre`

TaskFlow jeràrquic: projectes, categories, tasques i subtasques

Recórrer un arbre genèric amb recursió

Arbres a la vida real

Errors Comuns i Consells

Exercicis

Exercici 1: comptar només les tasques

Exercici 2: profunditat d'una tasca

Exercici 3: fulles de l'arbre

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

Introducció als Arbres

Contingut

Del hash a l'arbre: per què necessitem jerarquia i ordre

Què és un arbre: definició i propietats

Terminologia: el vocabulari que farem servir tot el mòdul

Arbres genèrics en Python: la classe NodeArbre

TaskFlow jeràrquic: projectes, categories, tasques i subtasques

Recórrer un arbre genèric amb recursió

Arbres a la vida real

Errors Comuns i Consells

Exercicis

Exercici 1: comptar només les tasques

Exercici 2: profunditat d'una tasca

Exercici 3: fulles de l'arbre

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

Arbres genèrics en Python: la classe `NodeArbre`