05 - Alberi binari, BST, AVL

Hai un insieme di chiavi che cambia nel tempo e ti servono tre cose insieme: sapere se una chiave c'è, inserirne una nuova, rileggere tutto in ordine. Una lista ordinata ti dà la ricerca veloce ma costringe a spostare metà degli elementi a ogni inserimento; una tabella hash inserisce e cerca in fretta ma non conosce l'ordine. L'albero binario di ricerca (BST) tiene insieme le tre operazioni, a una condizione che il codice non scrive da nessuna parte: l'albero deve restare basso. Questo articolo costruisce un BST, lo rompe con un ordine di inserimento sfortunato, e lo ripara con l'AVL, misurando ogni volta quanti nodi vengono esaminati. Ti servono la notazione O di Big-O e complessità e l'idea di ricerca vista in ricerca lineare, binaria e hash; per la coda del livello a livello ti basta la deque dell'articolo precedente.

Che cosa promette un albero binario di ricerca

Un albero binario è una struttura in cui ogni nodo ha una chiave e al massimo due figli, uno a sinistra e uno a destra. Diventa un albero di ricerca quando vale una sola regola, l'invariante: per ogni nodo, tutte le chiavi del sottoalbero sinistro sono minori della sua, tutte quelle del destro sono maggiori. Pensa a un elenco telefonico che a ogni pagina ti dice «prima di questo cognome vai a sinistra, dopo vai a destra»: a ogni passo scarti un intero ramo senza guardarlo.

Ne segue che cercare, inserire e cancellare costano un numero di passi proporzionale all'altezza h dell'albero, cioè O(h). Se l'albero è ben riempito h cresce come il logaritmo del numero di chiavi n, e lo scarto a ogni passo dimezza il lavoro; se l'albero è una catena, h vale n e hai ricostruito una lista con in più i puntatori. Tutto il resto dell'articolo gira intorno a questa distinzione, e la misuriamo contando i nodi esaminati, non i secondi, perché il conteggio non cambia da una macchina all'altra.

Il BST in Python, senza ricorsione dove si può

Il listato che segue è la struttura usata da tutti gli esperimenti successivi, da salvare come bst.py. insert e search sono iterative: scendono con un ciclo e incrementano self.compares a ogni nodo esaminato, quindi funzionano anche su un albero profondo migliaia di livelli. Se le facessi ricorsive, un albero degenere da 4.000 chiavi supererebbe il limite di ricorsione di Python (1.000 per impostazione predefinita, documentato in sys.setrecursionlimit) e fallirebbe con un errore, non con una risposta lenta. delete è ricorsiva perché serve a riscrivere i collegamenti dal basso verso l'alto, e lo si può permettere finché l'albero è basso.

class Node:
    __slots__ = ("key", "left", "right")

    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None


class BST:
    def __init__(self):
        self.root = None
        self.size = 0
        self.compares = 0  # nodi esaminati: la misura usata nell'articolo

    def insert(self, key):
        if self.root is None:
            self.root = Node(key)
            self.size = 1
            return True
        node = self.root
        while True:
            self.compares += 1
            if key == node.key:
                return False  # chiave gia' presente: l'insieme non cambia
            side = "left" if key < node.key else "right"
            child = getattr(node, side)
            if child is None:
                setattr(node, side, Node(key))
                self.size += 1
                return True
            node = child

    def search(self, key):
        node = self.root
        while node is not None:
            self.compares += 1
            if key == node.key:
                return True
            node = node.left if key < node.key else node.right
        return False

    def delete(self, key):
        before = self.size
        self.root = self._delete(self.root, key)
        return self.size < before

    def _delete(self, node, key):  # ricorsiva: profondita' = altezza
        if node is None:
            return None
        if key < node.key:
            node.left = self._delete(node.left, key)
        elif key > node.key:
            node.right = self._delete(node.right, key)
        else:
            self.size -= 1
            if node.left is None:
                return node.right
            if node.right is None:
                return node.left
            succ = node.right  # due figli: il successore e' il minimo a destra
            while succ.left is not None:
                succ = succ.left
            node.key = succ.key
            self.size += 1  # compensa il decremento che farebbe la chiamata sotto
            node.right = self._delete(node.right, succ.key)
        return node

    def height(self):  # numero di nodi sul cammino piu' lungo, iterativa
        best, stack = 0, [(self.root, 1)] if self.root else []
        while stack:
            node, depth = stack.pop()
            best = max(best, depth)
            for child in (node.left, node.right):
                if child is not None:
                    stack.append((child, depth + 1))
        return best

    def in_order(self):
        out, stack, node = [], [], self.root
        while stack or node is not None:
            while node is not None:
                stack.append(node)
                node = node.left
            node = stack.pop()
            out.append(node.key)
            node = node.right
        return out

La cancellazione ha tre casi. Un nodo senza figli sparisce; un nodo con un solo figlio viene sostituito dal figlio; un nodo con due figli prende la chiave del suo successore, il minimo del sottoalbero destro, e poi quel successore (che ha al più un figlio) viene cancellato a sua volta. Il successore è la scelta giusta perché è la chiave immediatamente più grande: messa al posto della cancellata, lascia l'invariante intatto. La riga self.size += 1 compensa un conteggio doppio: il nodo viene contato come cancellato alla prima chiamata e di nuovo quando si rimuove il successore. Togliila e size sbaglia, ma l'albero resta corretto: è il tipo di errore che solo un test contro un riferimento indipendente scopre.

Prima prova: è corretto?

Prima di misurare la velocità serve sapere che l'albero fa ciò che promette. Lo confronto con il tipo set di Python, che è un riferimento indipendente: 3.000 sequenze casuali di inserimenti, cancellazioni e ricerche su chiavi tra 0 e 40 (un intervallo stretto, così le chiavi si ripetono e si cancellano davvero), con il generatore a seme fisso. A fine sequenza la visita in ordine deve coincidere con sorted(ref) e la dimensione con len(ref).

import random
from bst import BST

rng = random.Random(7)
casi = 0
for prova in range(3000):
    t, ref = BST(), set()
    for _ in range(rng.randint(1, 60)):
        k = rng.randint(0, 40)
        op = rng.choice(("ins", "ins", "del", "src"))
        if op == "ins":
            assert t.insert(k) == (k not in ref)
            ref.add(k)
        elif op == "del":
            assert t.delete(k) == (k in ref)
            ref.discard(k)
        else:
            assert t.search(k) == (k in ref)
        casi += 1
    assert t.in_order() == sorted(ref) and t.size == len(ref)
print("prove:", 3000, "operazioni confrontate con set():", casi)

# Output:
# prove: 3000 operazioni confrontate con set(): 92095

Le 92.095 operazioni concordano con set fino all'ultima. Non è una dimostrazione, è una rete a maglie fitte: i bug tipici (il successore sbagliato, un figlio perso nel caso a un solo figlio) hanno molte occasioni di manifestarsi su chiavi che si ripetono, mentre un test con un solo albero scritto a mano ne vedrebbe pochi.

Il caso peggiore: chiavi in ordine

L'esperimento decisivo inserisce le stesse n chiavi in due ordini, casuale e crescente, e poi cerca ognuna una volta, contando i nodi esaminati. L'ordine crescente è il caso peggiore e non è esotico: gli identificatori progressivi, le date di un registro, i timestamp arrivano proprio così.

import math
import random
from bst import BST

rng = random.Random(2026)
print("n      ordine     altezza  confronti/ricerca  rapporto con lg n")
for n in (1000, 4000, 16000):
    for ordine in ("casuale", "crescente"):
        keys = list(range(n))
        if ordine == "casuale":
            rng.shuffle(keys)
        t = BST()
        for k in keys:
            t.insert(k)
        t.compares = 0
        for k in range(n):  # cerca ogni chiave presente una volta
            t.search(k)
        media = t.compares / n
        print(f"{n:<6} {ordine:<10} {t.height():<8} {media:<18.2f} {media / math.log2(n):.2f}")

# Output:
# n      ordine     altezza  confronti/ricerca  rapporto con lg n
# 1000   casuale    22       11.76              1.18
# 1000   crescente  1000     500.50             50.22
# 4000   casuale    25       13.99              1.17
# 4000   crescente  4000     2000.50            167.19
# 16000  casuale    34       17.72              1.27
# 16000  crescente  16000    8000.50            572.86

Con l'ordine casuale l'altezza resta piccola (22, 25 e 34 livelli per 1.000, 4.000 e 16.000 chiavi) e la ricerca esamina in media 11,76, 13,99 e 17,72 nodi. Per un BST costruito da chiavi casuali la pagina sui BST di Algorithms, 4th edition riporta come termine dominante circa 2 ln n confronti per ricerca, cioè circa 1,39 lg n; i miei valori stanno sotto 2 ln n (13,82, 16,59 e 19,36 per questi n), come ti aspetti quando i termini minori della formula sono negativi. Una sola sequenza per ogni n: il confronto è indicativo, non un test della formula. Con l'ordine crescente l'altezza è n e la ricerca esamina in media (n+1)/2 nodi: 500,5 su 1.000, 8.000,5 su 16.000. Il rapporto con lg n passa da 50 a 573, e continua a salire: non è un fattore costante, è un'altra classe di complessità.

Il numero che conta per un progettista è il rapporto fra i due casi: a 16.000 chiavi la stessa struttura costa 17,7 o 8.000 nodi a ricerca, oltre 450 volte di più, solo per l'ordine in cui sono arrivati i dati. Un BST semplice non ti dà una garanzia: ti dà una speranza sulla distribuzione degli ingressi, e nelle applicazioni vere la speranza ogni tanto si rompe.

Le quattro visite

Visitare un albero significa elencare tutte le chiavi con una regola fissa. Le tre visite in profondità differiscono per il momento in cui si legge la radice: prima dei figli (pre-order), in mezzo (in-order), dopo (post-order). La quarta, a livelli, usa una coda e legge tutta la riga di profondità 0, poi quella di profondità 1, e così via. Il listato le applica a un albero di sette chiavi, e poi verifica una proprietà utile: l'elenco in pre-order, reinserito nell'ordine, ricostruisce esattamente lo stesso albero. Dipende dal fatto che nel pre-order ogni radice precede tutti i suoi discendenti, quindi ogni nodo viene reinserito sotto lo stesso genitore.

import random
from collections import deque
from bst import BST, Node

def pre_order(n):
    return [] if n is None else [n.key] + pre_order(n.left) + pre_order(n.right)

def post_order(n):
    return [] if n is None else post_order(n.left) + post_order(n.right) + [n.key]

def level_order(root):
    out, coda = [], deque([root] if root else [])
    while coda:
        n = coda.popleft()
        out.append(n.key)
        coda.extend(c for c in (n.left, n.right) if c is not None)
    return out

def forma(n):  # struttura annidata: due alberi sono uguali se lo sono le forme
    return None if n is None else (n.key, forma(n.left), forma(n.right))

t = BST()
for k in (50, 30, 70, 20, 40, 60, 80):
    t.insert(k)
print("pre  ", pre_order(t.root))
print("in   ", t.in_order())
print("post ", post_order(t.root))
print("level", level_order(t.root))

rng = random.Random(11)
for prova in range(2000):
    keys = rng.sample(range(500), rng.randint(1, 40))
    a = BST()
    for k in keys:
        a.insert(k)
    b = BST()
    for k in pre_order(a.root):  # il pre-order da solo ricostruisce lo stesso albero
        b.insert(k)
    assert forma(a.root) == forma(b.root)
print("ricostruzione dal solo pre-order: 2000 alberi identici")

# Output:
# pre   [50, 30, 20, 40, 70, 60, 80]
# in    [20, 30, 40, 50, 60, 70, 80]
# post  [20, 40, 30, 60, 80, 70, 50]
# level [50, 30, 70, 20, 40, 60, 80]
# ricostruzione dal solo pre-order: 2000 alberi identici

L'in-order di un BST dà le chiavi ordinate, ed è il motivo per cui un BST ordina «gratis» mentre si riempie. Il pre-order è una serializzazione compatta: 2.000 alberi casuali sono stati ricostruiti identici dal solo elenco, senza bisogno dell'in-order che serve invece per alberi senza l'invariante. Il post-order è la visita di chi libera la memoria o calcola un valore dai figli verso il padre, e la visita a livelli è la ricerca in ampiezza che riprende l'articolo sui grafi.

AVL: tenere l'altezza sotto controllo

L'albero AVL (dalle iniziali di Adelson-Velsky e Landis) aggiunge una regola all'invariante di ordine: in ogni nodo le altezze dei due sottoalberi differiscono al più di 1. La differenza, con segno, si chiama fattore di bilanciamento e deve valere -1, 0 o 1. Quando un inserimento o una cancellazione rompe la regola (il fattore diventa 2 o -2), si ripara con una rotazione: un riarrangiamento locale di tre nodi che cambia la forma ma conserva l'ordine in-order. Sono quattro i casi: sinistra-sinistra e destra-destra si risolvono con una rotazione, sinistra-destra e destra-sinistra con due, perché prima va raddrizzato il figlio.

Il listato, da salvare come avl.py, lo implementa. _rebalance ricalcola l'altezza, legge il fattore e sceglie il caso: nel ramo b > 1 il controllo balance(n.left) < 0 distingue sinistra-destra da sinistra-sinistra. _rot_right e _rot_left sono le rotazioni singole, e ognuna aggiorna le altezze del nodo sceso prima di quello salito, perché l'altezza del nodo salito dipende dall'altro. Il metodo check verifica in modo indipendente le tre proprietà: ordine, altezze memorizzate uguali a quelle ricalcolate, fattore nel range.

class Node:
    __slots__ = ("key", "left", "right", "h")

    def __init__(self, key):
        self.key, self.left, self.right, self.h = key, None, None, 1


def h(n):
    return n.h if n else 0

def update(n):
    n.h = 1 + max(h(n.left), h(n.right))

def balance(n):
    return h(n.left) - h(n.right)


class AVL:
    def __init__(self):
        self.root, self.size = None, 0
        self.compares = 0   # nodi esaminati
        self.rotations = 0  # rotazioni singole eseguite (una doppia ne vale due)

    def _rot_right(self, y):
        x = y.left
        y.left, x.right = x.right, y
        update(y)
        update(x)
        self.rotations += 1
        return x

    def _rot_left(self, x):
        y = x.right
        x.right, y.left = y.left, x
        update(x)
        update(y)
        self.rotations += 1
        return y

    def _rebalance(self, n):
        update(n)
        b = balance(n)
        if b > 1:  # pende a sinistra
            if balance(n.left) < 0:  # caso sinistra-destra: prima ruota il figlio
                n.left = self._rot_left(n.left)
            return self._rot_right(n)
        if b < -1:  # pende a destra
            if balance(n.right) > 0:  # caso destra-sinistra
                n.right = self._rot_right(n.right)
            return self._rot_left(n)
        return n

    def insert(self, key):
        before = self.size
        self.root = self._insert(self.root, key)
        return self.size > before

    def _insert(self, n, key):
        if n is None:
            self.size += 1
            return Node(key)
        self.compares += 1
        if key < n.key:
            n.left = self._insert(n.left, key)
        elif key > n.key:
            n.right = self._insert(n.right, key)
        else:
            return n
        return self._rebalance(n)

    def delete(self, key):
        before = self.size
        self.root = self._delete(self.root, key)
        return self.size < before

    def _delete(self, n, key):
        if n is None:
            return None
        if key < n.key:
            n.left = self._delete(n.left, key)
        elif key > n.key:
            n.right = self._delete(n.right, key)
        else:
            if n.left is None or n.right is None:
                self.size -= 1
                return n.left or n.right
            succ = n.right
            while succ.left:
                succ = succ.left
            n.key = succ.key
            n.right = self._delete(n.right, succ.key)
        return self._rebalance(n)

    def search(self, key):
        n = self.root
        while n:
            self.compares += 1
            if key == n.key:
                return True
            n = n.left if key < n.key else n.right
        return False

    def in_order(self):
        out, stack, n = [], [], self.root
        while stack or n:
            while n:
                stack.append(n)
                n = n.left
            n = stack.pop()
            out.append(n.key)
            n = n.right
        return out

    def check(self):
        """Verifica le tre proprieta': ordine, altezze memorizzate, |fattore| <= 1."""
        def rec(n, lo, hi):
            if n is None:
                return 0
            assert (lo is None or n.key > lo) and (hi is None or n.key < hi)
            hl, hr = rec(n.left, lo, n.key), rec(n.right, n.key, hi)
            assert abs(hl - hr) <= 1 and n.h == 1 + max(hl, hr)
            return 1 + max(hl, hr)
        return rec(self.root, None, None)

Se invertissi l'ordine dei due update in una rotazione, l'albero resterebbe ordinato e tutte le ricerche continuerebbero a funzionare, ma le altezze memorizzate sarebbero sbagliate: il difetto si manifesterebbe più tardi, come un'altra rotazione sbagliata. È il motivo per cui check ricalcola tutto da zero invece di fidarsi dei campi. La cancellazione ha la stessa struttura del BST e ribilancia risalendo, a differenza dell'inserimento, anche oltre il primo nodo riparato: una rotazione può accorciare un sottoalbero e rompere l'equilibrio più su.

Seconda prova: l'invariante regge dopo ogni operazione

La prova per l'AVL è più severa: non si controlla solo alla fine, ma dopo ognuna delle operazioni. In 4.000 sequenze casuali, con il 60% di inserimenti e il 40% di cancellazioni su chiavi da 0 a 50, check() verifica ordine, altezze e fattore e il risultato finale va confrontato con set. Nota la differenza con il BST: nell'AVL la cancellazione di un nodo con due figli non ha bisogno della riga di compensazione di size, perché il nodo viene contato una sola volta, quando si rimuove il successore; con quella riga copiata dal BST l'albero resterebbe valido ma size sbaglierebbe, ed è l'asserzione su len(ref) a scoprirlo.

import random
from avl import AVL

rng = random.Random(99)
op_totali = 0
for prova in range(4000):
    t, ref = AVL(), set()
    for _ in range(rng.randint(1, 80)):
        k = rng.randint(0, 50)
        if rng.random() < 0.6:
            assert t.insert(k) == (k not in ref)
            ref.add(k)
        else:
            assert t.delete(k) == (k in ref)
            ref.discard(k)
        t.check()  # le tre proprieta' valgono dopo OGNI operazione
        op_totali += 1
    assert t.in_order() == sorted(ref) and t.size == len(ref)
print("prove: 4000, operazioni con controllo dell'invariante:", op_totali)

# Output:
# prove: 4000, operazioni con controllo dell'invariante: 161499

Le 161.499 operazioni lasciano sempre un albero valido. Il confronto con set prova che nessuna chiave si perde nelle rotazioni, il controllo dopo ogni passo prova che nessun passo intermedio esce dal range, e la scelta di molte chiavi ripetute in un intervallo piccolo garantisce che cancellazioni e rotazioni doppie avvengano davvero.

L'ordine crescente sull'AVL e il suo caso peggiore

Ripetiamo l'esperimento che aveva rotto il BST: chiavi in ordine crescente. Se l'AVL funziona, l'altezza deve restare vicina a lg n e il costo di ricerca deve crollare. Il listato misura anche il numero di rotazioni e costruisce poi il peggior AVL possibile, quello con il minimo numero di nodi per una data altezza. Un albero di altezza h con il minimo di nodi ha un sottoalbero di altezza h-1 e uno di altezza h-2, quindi il minimo N(h) soddisfa N(h) = N(h-1) + N(h-2) + 1, una ricorrenza di tipo Fibonacci: la funzione min_nodi la calcola e albero_fibonacci costruisce davvero l'albero, che viene poi verificato dal check.

import math
from avl import AVL, Node, update

def min_nodi(altezza):  # meno nodi possibili per un AVL di quell'altezza
    a, b = 0, 1
    for _ in range(altezza - 1):
        a, b = b, a + b + 1
    return b if altezza else 0

def albero_fibonacci(altezza, prossima):
    """Costruisce l'AVL piu' sbilanciato permesso: sottoalbero sinistro piu' alto di 1."""
    if altezza == 0:
        return None
    n = Node(None)
    n.left = albero_fibonacci(altezza - 1, prossima)
    n.key = next(prossima)
    n.right = albero_fibonacci(altezza - 2, prossima) if altezza > 1 else None
    update(n)
    return n

print("sequenza crescente 1..n inserita nell'AVL")
print("n        altezza  minimo   rotazioni  confronti/ricerca")
for n in (1000, 10000, 100000):
    t = AVL()
    for k in range(n):
        t.insert(k)
    rot, t.compares = t.rotations, 0
    for k in range(n):
        t.search(k)
    print(f"{n:<8} {t.check():<8} {math.ceil(math.log2(n + 1)):<8} {rot:<10} {t.compares / n:.2f}")

print()
print("AVL di altezza h con il minimo di nodi (alberi di Fibonacci)")
print("h   nodi    altezza/lg(nodi)")
for hh in (5, 10, 15, 20, 25):
    it = iter(range(10**7))
    t = AVL()
    t.root = albero_fibonacci(hh, it)
    n = min_nodi(hh)
    t.size = n
    assert t.check() == hh and len(t.in_order()) == n
    print(f"{hh:<3} {n:<7} {hh / math.log2(n):.3f}")
print("limite teorico 1/lg(phi) =", round(1 / math.log2((1 + 5 ** 0.5) / 2), 4))

# Output:
# sequenza crescente 1..n inserita nell'AVL
# n        altezza  minimo   rotazioni  confronti/ricerca
# 1000     10       10       990        8.99
# 10000    14       14       9986       12.36
# 100000   17       17       99983      15.69
#
# AVL di altezza h con il minimo di nodi (alberi di Fibonacci)
# h   nodi    altezza/lg(nodi)
# 5   12      1.395
# 10  143     1.397
# 15  1596    1.410
# 20  17710   1.417
# 25  196417  1.422
# limite teorico 1/lg(phi) = 1.4404

Inseriti in ordine crescente, 1.000, 10.000 e 100.000 nodi producono alberi alti 10, 14 e 17 livelli: esattamente il minimo possibile, ceil(lg(n+1)), perché l'inserimento ordinato riempie l'albero livello per livello. La ricerca esamina in media 8,99, 12,36 e 15,69 nodi, contro i 500,5 del BST già a 1.000 chiavi. Il prezzo sono le rotazioni: 990, 9.986 e 99.983, quasi una per inserimento. È il lavoro che l'AVL fa per tenere l'altezza al minimo: su questo ingresso è ciò che compra la garanzia.

Nella seconda tabella l'albero di Fibonacci è l'AVL più alto per i suoi nodi: 12 nodi per altezza 5, 17.710 per altezza 20. Il rapporto altezza/lg(n) sale con h (1,395, 1,397, 1,410, 1,417, 1,422) verso il limite 1/lg(φ) = 1,4404, che lo script calcola dalla sezione aurea. Significa che nel caso peggiore un AVL è alto al più circa 1,44 volte il minimo logaritmico: la garanzia è O(log n), con una costante nota e piccola. Non è un risultato che ho preso da una fonte: segue dalla ricorrenza di sopra, e l'albero costruito la rispetta.

Quando non basta, e quando non serve

L'AVL non è l'unica strada: il red-black tree rilassa l'equilibrio in cambio di meno rotazioni in scrittura, e la pagina sugli alberi bilanciati di Algorithms, 4th edition riporta per i suoi alberi rosso-neri un'altezza garantita non superiore a 2 lg n; il B-tree tiene molte chiavi per nodo per ridurre gli accessi al disco. Non li ho implementati qui, quindi non offro misure su di loro. Per decidere fra le opzioni conviene guardare tre domande, che l'elenco seguente mette in ordine di costo di una risposta sbagliata.

• Servono le chiavi in ordine, un intervallo o il successore di una chiave? Se no, una tabella hash basta e un albero è un eccesso.
• Le chiavi arrivano in un ordine che non controlli? Se sì, un BST senza bilanciamento è un rischio, e conviene una struttura con altezza garantita.
• I dati stanno in memoria? Se stanno su disco, l'altezza conta in accessi e il B-tree vince sul binario.

Le domande si ordinano per quanto costa sbagliare: la prima evita di costruire la struttura sbagliata, la seconda evita un degrado che si vede solo con certi dati in produzione, la terza sposta la scelta su un'altra famiglia di alberi. In Python, per i casi piccoli, un elenco ordinato con il modulo bisect resta spesso la risposta più semplice; l'albero entra quando gli inserimenti sono molti e frequenti, e l'ordine serve.

Che cosa sai fare adesso

Sai scrivere un BST con inserimento, ricerca e cancellazione, e sai dimostrare con una misura (nodi esaminati, non secondi) che l'ordine crescente lo trasforma in una lista. Sai scrivere un AVL con le quattro rotazioni, verificarne l'invariante dopo ogni operazione contro un riferimento indipendente, e calcolare il suo caso peggiore con la ricorrenza di Fibonacci. Nell'articolo successivo la struttura smette di essere un albero: i nodi possono avere cicli, e il lavoro cambia.

Nella stessa serie trovi anche gli algoritmi di ordinamento e il riepilogo sulla programmazione dinamica.