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

Arbres Binaris

Següent ►
►

A la lliçó anterior vam construir arbres genèrics on cada node pot tenir qualsevol nombre de fills: perfectes per a jerarquies lliures com la de TaskFlow, però sense propietats matemàtiques fortes per explotar. Aquesta lliçó restringeix l'arbre a com a màxim dos fills per node, amb posicions distingides (esquerre i dret), i aquesta restricció tan simple obre la porta a gairebé tot el que queda de mòdul: sobre els arbres binaris es construeixen els arbres de cerca (06-04), els AVL (06-05) i els monticles (06-07). Aquí aprendràs la classe NodeBinari, els tipus d'arbre binari (ple, complet, perfecte, degenerat), els comptes que relacionen nodes i altura — la clau de per què "O(log n)" apareixerà tantes vegades — i una representació sorprenent: un arbre complet guardat en un array pla.

Contingut

  1. Definició: dos fills, amb nom i cognom
  2. La classe NodeBinari
  3. Tipus d'arbres binaris: ple, complet, perfecte i degenerat
  4. Els comptes de l'arbre binari: nodes, nivells i altura
  5. Representació en array d'un arbre complet
  6. TaskFlow: un arbre binari de decisió per classificar tasques

Definició: dos fills, amb nom i cognom

Un arbre binari és un arbre en què cada node té com a màxim dos fills, i — detall crucial — cada fill ocupa una posició amb nom propi: fill esquerre o fill dret. No és el mateix un node amb només un fill esquerre que amb només un fill dret: són arbres binaris diferents.

graph TD
    subgraph "Arbre A"
        A1((5)) --> B1((3))
        A1 -.x.-> C1(( ))
    end
    subgraph "Arbre B (diferent d'A)"
        A2((5)) -.x.-> B2(( ))
        A2 --> C2((3))
    end

A l'arbre genèric, fills = [x] era simplement "un fill". Aquí la posició importa, i aquest matís serà or pur a 06-04: "esquerra = menors, dreta = majors" només té sentit si esquerra i dreta existeixen com a conceptes separats.

La classe NodeBinari

En lloc d'una llista de fills, dues referències amb nom — el mateix salt que vam fer del Node al NodeDoble al mòdul 2, però amb un altre significat: allà anterior/seguent encadenaven en línia; aquí esquerre/dret ramifiquen.

class NodeBinari:
    """Un node d'arbre binari: valor i dos fills amb posició."""

    def __init__(self, valor):
        self.valor = valor
        self.esquerre = None    # subarbre esquerre (None = no n'hi ha)
        self.dret = None        # subarbre dret     (None = no n'hi ha)

I ja està: no necessita més mètodes, perquè els fills s'assignen directament. Construïm a mà el primer arbre:

graph TD
    R((10)) --> I((6))
    R --> D((15))
    I --> II((3))
    I --> ID((8))
    D --> DI((12))
arrel = NodeBinari(10)
arrel.esquerre = NodeBinari(6)
arrel.dret = NodeBinari(15)
arrel.esquerre.esquerre = NodeBinari(3)
arrel.esquerre.dret = NodeBinari(8)
arrel.dret.esquerre = NodeBinari(12)

La definició recursiva de la lliçó anterior s'afina: un arbre binari és buit (None), o un node amb un arbre binari esquerre i un arbre binari dret. D'aquí que les funcions sobre arbres binaris tinguin gairebé sempre aquesta silueta:

def comptar(node):
    if node is None:                                   # arbre buit
        return 0
    return 1 + comptar(node.esquerre) + comptar(node.dret)

def altura(node):
    """Altura del subarbre. Convenció: arbre buit = -1, fulla = 0."""
    if node is None:
        return -1
    return 1 + max(altura(node.esquerre), altura(node.dret))

print(comptar(arrel))   # 6
print(altura(arrel))    # 2

Detall d'altura: retornar -1 per a l'arbre buit fa que el compte quadri sol — una fulla té dos fills None d'altura -1, així que la seva altura és 1 + max(-1, -1) = 0, com ha de ser. I max perquè l'altura la marca el camí més llarg cap a una fulla.

Tipus d'arbres binaris: ple, complet, perfecte i degenerat

No tots els arbres binaris amb els mateixos nodes tenen la mateixa forma, i la forma determina el rendiment. Els quatre noms que cal conèixer:

Tipus Definició Idea visual
Ple (full) Cada node té 0 o 2 fills (mai exactament 1) Sense "braços a mitges"
Complet (complete) Tots els nivells plens llevat potser de l'últim, que s'omple d'esquerra a dreta sense forats S'omple com un teatre, per files
Perfecte Tots els nivells completament plens (totes les fulles a la mateixa profunditat) El triangle ideal
Degenerat Cada node té un sol fill: l'arbre és una cadena Una llista enllaçada disfressada 
graph TD
    subgraph "Ple"
        L1((A)) --> L2((B))
        L1 --> L3((C))
        L2 --> L4((D))
        L2 --> L5((E))
    end
    subgraph "Complet"
        C1((A)) --> C2((B))
        C1 --> C3((C))
        C2 --> C4((D))
        C2 --> C5((E))
        C3 --> C6((F))
    end
graph TD
    subgraph "Perfecte"
        P1((A)) --> P2((B))
        P1 --> P3((C))
        P2 --> P4((D))
        P2 --> P5((E))
        P3 --> P6((F))
        P3 --> P7((G))
    end
    subgraph "Degenerat"
        D1((A)) --> D2((B))
        D2 --> D3((C))
        D3 --> D4((D))
    end

Observacions que convé interioritzar:

  • Tot arbre perfecte és complet i ple; les categories se solapen.
  • El complet — omplir per nivells i d'esquerra a dreta, sense forats — sembla una definició capriciosa, però és exactament la forma que permet la representació en array de la secció 5, i per això és la forma dels monticles de 06-07.
  • El degenerat és el malson: estructuralment és una llista enllaçada del mòdul 2, amb cost O(n) per arribar al final. A 06-04 veurem que n'és, de fàcil, crear-ne un sense voler, i 06-05 existeix per impedir-ho.

Els comptes de l'arbre binari: nodes, nivells i altura

Tres fets numèrics, tots derivats de "cada node té com a màxim 2 fills":

  • El nivell k té com a màxim 2^k nodes: 1 al nivell 0 (l'arrel), 2 a l'1, 4 al 2, 8 al 3... Cada nivell pot duplicar l'anterior. (Et sona? Al mòdul 4, l'exercici binaris_fins(n) generava "1, 10, 11, 100..." amb una cua: estaves recorrent per nivells un arbre binari perfecte sense saber-ho. A 06-03 tancarem aquest cercle.)
  • Un arbre d'altura h té com a màxim 2^(h+1) − 1 nodes: la suma 1 + 2 + 4 + ... + 2^h. Un arbre perfecte d'altura 10 acull 2 047 nodes; d'altura 20, més de dos milions.
  • A l'inrevés — i aquest és el compte important — un arbre amb n nodes té altura mínima ⌊log₂ n⌋: per guardar n nodes necessites almenys log₂(n) nivells, perquè menys nivells no donen prou capacitat. I altura màxima n − 1 (el degenerat).
n nodes Altura mínima (equilibrat) Altura màxima (degenerat)
7 2 6
1 000 9 999
1 000 000 19 999 999

Aquesta taula és el mapa de la resta del mòdul. Gairebé totes les operacions que veurem (cercar a 06-04, inserir/extreure a 06-07) costen O(altura): caminen de l'arrel cap avall, un node per nivell. Si l'arbre està equilibrat, altura ≈ log₂ n i l'operació és logarítmica — 20 passos per a un milió d'elements, la mateixa màgia que la cerca binària del mòdul 1. Si està degenerat, altura ≈ n i tornem a l'O(n) de la llista enllaçada. Tota la batalla de 06-04 i 06-05 és mantenir l'altura logarítmica.

Representació en array d'un arbre complet

Sorpresa: un arbre binari complet no necessita nodes ni referències — cap en una llista de Python. Es numeren els nodes per nivells, d'esquerra a dreta, començant per 0, i aquest número és el seu índex a l'array:

graph TD
    A["10 (i=0)"] --> B["6 (i=1)"]
    A --> C["15 (i=2)"]
    B --> D["3 (i=3)"]
    B --> E["8 (i=4)"]
    C --> F["12 (i=5)"]
arbre = [10, 6, 15, 3, 8, 12]

L'aritmètica que substitueix les referències — aprèn-te-la, perquè és el cor del monticle de 06-07:

Des del node a l'índex i Fórmula
Fill esquerre 2*i + 1
Fill dret 2*i + 2
Pare (i - 1) // 2 
def fill_esquerre(arbre, i):
    j = 2 * i + 1
    return arbre[j] if j < len(arbre) else None

def fill_dret(arbre, i):
    j = 2 * i + 2
    return arbre[j] if j < len(arbre) else None

def pare(arbre, i):
    return arbre[(i - 1) // 2] if i > 0 else None

print(fill_esquerre(arbre, 0))  # 6   (fills de 10: índexs 1 i 2)
print(fill_dret(arbre, 1))      # 8   (fills de 6: índexs 3 i 4)
print(pare(arbre, 5))           # 15  ((5-1)//2 = 2)

Comprova les fórmules amb el diagrama: els fills de l'índex 1 són el 3 i el 4; els del 2 són el 5 i el 6. Avantatges d'aquesta representació: zero memòria en referències (compara amb els dos punters per node de NodeBinari), dades contigües en memòria (la localitat de memòria cau de 01-05), i navegació pare↔fill amb una divisió. La lletra petita: només funciona sense forats, és a dir, amb arbres complets. Si l'arbre tingués un forat intermedi caldria omplir amb None i malgastar posicions — en un degenerat de 20 nodes, més d'un milió de forats. Per això el monticle de 06-07 es manté sempre complet: per viure en un array.

TaskFlow: un arbre binari de decisió per classificar tasques

On encaixa un arbre binari a TaskFlow, més enllà de preparar 06-04? En un arbre de decisió: cada node intern és una pregunta de sí/no, esquerra = no, dreta = sí, i les fulles són veredictes. Classifiquem tasques entrants:

graph TD
    A{"prioritat == 1?"} -->|no| B{"estat == bloquejada?"}
    A -->|sí| C{"estat == bloquejada?"}
    B -->|no| D["Safata normal"]
    B -->|sí| E["Revisar dependències"]
    C -->|no| F["Atendre JA!"]
    C -->|sí| G["Escalar al responsable"]
def crear_pregunta(text_pregunta, condicio):
    """Node intern: guarda la pregunta i la funció que l'avalua."""
    node = NodeBinari(text_pregunta)
    node.condicio = condicio         # funció tasca -> bool
    return node

# Fulles: el veredicte és el valor
safata   = NodeBinari("Safata normal")
revisar  = NodeBinari("Revisar dependències")
atendre  = NodeBinari("Atendre JA!")
escalar  = NodeBinari("Escalar al responsable")

# Nodes interns (convenció: esquerre = no, dret = sí)
urgent = crear_pregunta("prioritat == 1?", lambda t: t["prioritat"] == 1)
bloq_no_urg = crear_pregunta("bloquejada?", lambda t: t["estat"] == "bloquejada")
bloq_urg    = crear_pregunta("bloquejada?", lambda t: t["estat"] == "bloquejada")

urgent.esquerre, urgent.dret = bloq_no_urg, bloq_urg
bloq_no_urg.esquerre, bloq_no_urg.dret = safata, revisar
bloq_urg.esquerre, bloq_urg.dret = atendre, escalar

def classificar(node, tasca):
    """Baixa per l'arbre responent preguntes fins a arribar a una fulla."""
    while node.esquerre is not None:           # les fulles no tenen fills
        if node.condicio(tasca):
            node = node.dret                   # sí -> dreta
        else:
            node = node.esquerre               # no -> esquerra
    return node.valor

t1 = {"id": "T-07", "titol": "Caiguda del servidor", "prioritat": 1, "estat": "pendent"}
t2 = {"id": "T-08", "titol": "Actualitzar el logo", "prioritat": 3, "estat": "bloquejada"}
print(classificar(urgent, t1))   # Atendre JA!
print(classificar(urgent, t2))   # Revisar dependències

Fixa't en dues coses. Primera: classificar és iterativa i O(altura) — respon una pregunta per nivell i descendeix; amb l'arbre equilibrat, classificar entre 2^h veredictes costa només h preguntes. Segona: el patró "comparar al node i triar esquerra o dreta" que acabes d'escriure és, gest a gest, el mateix amb què cercarem a l'ABC de 06-04 — només canviarà la pregunta ("la meva clau és menor que la teva?").

Errors Comuns i Consells

  • Tractar esquerre i dret com a intercanviables. Un node amb només fill esquerre i un altre amb només fill dret són arbres diferents. A partir de 06-04, confondre'ls trenca directament la correcció.
  • Confondre "ple" i "complet". Són traduccions traïdores de full i complete, i ni tan sols la literatura en anglès és sempre consistent. Queda't amb les definicions de la taula; en aquest curs "complet" sempre vol dir "sense forats, omplert per nivells d'esquerra a dreta" — la forma del heap.
  • Usar la representació en array amb arbres no complets. Les fórmules 2i+1/2i+2 pressuposen que no hi ha forats. Amb un arbre arbitrari hauries d'inserir None de farciment, i en el pitjor cas (degenerat) l'array creix exponencialment respecte als nodes reals.
  • Descuidar la convenció d'altura de l'arbre buit. Hi ha textos on la fulla té altura 1 i el buit 0 (compten nodes en lloc d'arestes). Qualsevol de les dues funciona si ets consistent; en aquest curs: buit = −1, fulla = 0.
  • Consell: quan dubtis d'una fórmula d'índexs, dibuixa un arbre de 6-7 nodes, numera'l per nivells i comprova-la a mà en 30 segons. És infinitament millor que memoritzar.

Exercicis

Exercici 1: és un arbre ple?

Escriu es_ple(node) que retorni True si cada node de l'arbre té 0 o 2 fills. Prova-la amb l'arbre de la secció 2 (que no és ple: el 15 té un sol fill) i amb l'arbre de decisió de TaskFlow (que sí que ho és).

Exercici 2: de l'array al recompte de fulles, sense construir nodes

Donat un arbre complet en representació d'array, escriu fulles_array(arbre) que retorni la llista de valors de les seves fulles usant només les fórmules d'índexs (un node és fulla si el seu fill esquerre cauria fora de l'array). Per a [10, 6, 15, 3, 8, 12] ha de retornar [3, 8, 12].

Exercici 3: nivells mínims per a les tasques de TaskFlow

Sense executar codi: TaskFlow gestiona 5 000 tasques i les vols guardar en un arbre binari. (a) Quina és l'altura mínima possible de l'arbre? (b) I la màxima? (c) Si una operació costa O(altura), quants passos són en cada cas? Després comprova (a) amb una línia de Python.

Solucions

Solució 1

def es_ple(node):
    if node is None:
        return True                                   # el buit compleix trivialment
    if (node.esquerre is None) != (node.dret is None):
        return False                                  # exactament un fill: no és ple
    return es_ple(node.esquerre) and es_ple(node.dret)

print(es_ple(arrel))     # False (el 15 només té fill esquerre)
print(es_ple(urgent))    # True  (l'arbre de decisió)

Comentari: la línia clau usa != entre dos booleans com a "o exclusiu": és False quan tots dos fills existeixen o tots dos falten, i True (→ no ple) quan n'hi ha exactament un. I l'and final talla tan bon punt un subarbre falla. Nota de disseny: en un arbre de decisió ser ple no és casualitat — una pregunta amb una sola resposta possible no seria una pregunta.

Solució 2

def fulles_array(arbre):
    resultat = []
    for i in range(len(arbre)):
        if 2 * i + 1 >= len(arbre):      # sense fill esquerre => sense fills => fulla
            resultat.append(arbre[i])
    return resultat

print(fulles_array([10, 6, 15, 3, 8, 12]))   # [3, 8, 12]

Comentari: en un arbre complet no pot existir fill dret sense esquerre (l'últim nivell s'omple d'esquerra a dreta), així que n'hi ha prou de comprovar 2i+1. Bonus que pots verificar: la primera fulla és sempre a l'índex len(arbre) // 2 — en un array de 6 elements, els índexs 0, 1 i 2 són interns i el 3, 4 i 5 són fulles. El heapify de 06-07 explotarà exactament aquest fet.

Solució 3

(a) L'altura mínima és ⌊log₂ 5000⌋ = 12 (2¹³ − 1 = 8 191 ≥ 5 000 nodes caben en 13 nivells, i 2¹² − 1 = 4 095 < 5 000 demostren que 12 nivells no basten). (b) La màxima és 4 999: l'arbre degenerat, una tasca penjant d'una altra. (c) O(altura) vol dir uns 12 passos a l'arbre equilibrat davant de fins a 4 999 al degenerat — més de 400 vegades pitjor amb les mateixes dades.

import math
print(math.floor(math.log2(5000)))   # 12

Comentari: aquesta diferència no és teòrica: a 06-04 la provocarem amb codi real (inserint ids ja ordenats) i a 06-05 la mesurarem. Guarda aquests números al cap.

Conclusió

L'arbre binari afegeix a la jerarquia de 06-01 una disciplina: dos fills com a màxim, cadascun amb posició pròpia. D'aquesta disciplina n'has tret la classe NodeBinari, la taxonomia de formes (ple, complet, perfecte, degenerat), els comptes que lliguen nodes i altura — amb la conclusió central del mòdul: operació O(altura) + arbre equilibrat = O(log n); arbre degenerat = O(n) — i la representació en array amb índexs 2i+1/2i+2 que reapareixerà al monticle de 06-07. També has escrit el teu primer descens comparant a cada node, amb l'arbre de decisió de TaskFlow. Però fins ara hem visitat els nodes una mica "a demanda", sense mètode. La lliçó següent hi posa ordre: els quatre recorreguts sistemàtics d'un arbre — preordre, inordre, postordre i per nivells — que són als arbres el que el bucle for és a les llistes, i on per fi la cua del mòdul 4 i aquell exercici binaris_fins mostraran la seva cara veritable.

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