Recursivitat i Arbres Binaris

En aquest tema es combinen dues línies importants: la tècnica de la immersió en funcions recursives (per poder passar informació entre crides o retornar més d'un resultat) i l'ús d'arbres binaris com a estructura de dades. La immersió és necessària quan la signatura de la funció que volem oferir no ens permet afegir els paràmetres o retorns que necessitem; llavors introduïm una funció auxiliar recursiva amb més paràmetres o que retorna una tupla.

Els arbres binaris (BinTree<T>) es recorren naturalment amb recursió; veurem cerques, recorreguts en profunditat (preordre, inordre, postordre) i en amplada amb una cua, i opcionalment la reconstrucció d'un arbre a partir d'una seqüència. L'arbre general Tree<T> es veurà al tema següent.

Part I. Immersió

Les variables locals d'una funció recursiva viuen al frame de la funció

Quan una funció es crida a si mateixa, cada crida té el seu propi frame (bloc de memòria) amb les seves variables locals. Per tant, no hi ha una sola variable local compartida: n'hi ha tantes còpies com crides actives. Això vol dir que no podem "deixar anotacions" en una variable local i esperar que la següent crida recursiva les vegi, perquè cada crida té les seves pròpies còpies.

Per compartir informació entre les diverses crides recursives només tenim dues opcions coherents amb el disseny de les funcions: passar més informació mitjançant paràmetres (per valor o per referència), o retornar més d'un resultat (per exemple amb un pair<A,B>, que conté dos valors accessibles amb .first i .second). La immersió és la tècnica que consisteix a introduir una funció recursiva auxiliar amb exactament els paràmetres o retorns addicionals que necessitem.

La funció d'immersió és una funció recursiva auxiliar amb paràmetres o retorns addicionals

Quan el que volem és una funció amb una signatura concreta (per exemple reverse(string s) o balanced(BinTree<int> t)), però per implementar-la recursivament necessitem més informació en cada crida (un acumulador, altures, etc.), no podem canviar la signatura de la funció pública. La solució és definir una segona funció, que anomenem funció d'immersió, amb els paràmetres o tipus de retorn addicionals, implementar la recursió en aquesta funció, i fer que la funció original només cridi la d'immersió amb els valors inicials adequats.

Així doncs, la funció d'immersió no té la mateixa capçalera que la funció original precisament perquè porta els paràmetres (o retorns) extres que la recursió necessita.

Exemple: revessar un string amb un acumulador

Per invertir un string de forma recursiva, podem pensar que el string al revés és el revessat de la resta seguit del primer caràcter. Per exemple, el revés de "abc" és reverse("bc") + "a" = "cba". Aquesta recursió funciona, però si volem construir el resultat progressivament mentre avancem pel string, necessitem un lloc on anar acumulant el que portem invertit. La solució és afegir un paràmetre acumulador reversed: en cada crida, el caràcter actual es posa al davant de l'acumulador i es passa la resta del string; quan el string és buit, l'acumulador conté el resultat.

string reverse__(string s, string reversed) {
    if (s.empty()) {
        return reversed;
    } else {
        return reverse__(s.substr(1), s[0] + reversed);
    }
}

string reverse(string s) {
    return reverse__(s, "");
}

Es veu que reverse__ no té la mateixa capçalera que reverse: té un paràmetre extra (reversed) que actua com a acumulador. Com que aquest paràmetre no forma part de l'interfície pública que volem, implementem la recursió en una funció auxiliar i la funció original es limita a cridar-la amb el valor inicial de l'acumulador (string buit).

Exemple: Nombre $n$-èsim de la seqüència de Fibonacci

La definició recursiva clàssica del $n$-èsim nombre de Fibonacci ($F_0=0$, $F_1=1$, $F_n={}_{}$) porta a un cost exponencial si es programa literalment. Una versió eficient és "anar portant" els dos últims valors com a paràmetres i fer una sola crida recursiva per pas. Això requereix paràmetres extra ( i ), i per tant una funció d'immersió:

int fibonacci__(int n, int a, int b) {
    if (n == 0) {
        return a;
    } else {
        return fibonacci__(n - 1, b, a + b);
    }
}

int fibonacci(int n) {
    return fibonacci__(n, 0, 1);
}

La funció pública fibonacci(n) manté la signatura desitjada; la funció auxiliar fibonacci__ és la que té els paràmetres addicionals necessaris per la recurrència en cua.

Part II. Arbres

Un arbre binari és una estructura buida o un node amb un valor i dos subarbres

Un arbre binari és una estructura de dades recursiva: o bé és buit, o bé consta d'un node (l'arrel) que té un valor i exactament dos subarbres, anomenats fill esquerre i fill dret, que al seu torn són arbres binaris (i poden ser buits). Això permet construir arbres de qualsevol forma: fulles (nodes amb dos subarbres buits), branques asimètriques o arbres molt ramificats.

La classe BinTree<T> de PRO2 modela aquesta idea: el tipus T és el tipus del valor emmagatzemat a cada node (enters, reals, strings, etc.).

La classe BinTree<T> ofereix constructors i mètodes per consultar l'arbre sense modificar-lo

Segons el fitxer bintree.hh, la interfície pública és la següent.

Constructors:

• BinTree() — construeix un arbre buit.
• BinTree(const T& value) — construeix un arbre amb un sol node (valor value) i els dos subarbres buits.
• BinTree(const T& value, const BinTree& left, const BinTree& right) — construeix un arbre amb arrel value, fill esquerre left i fill dret right.

Consultes (només si l'arbre no és buit):

• empty() — retorna true si l'arbre és buit, false en cas contrari. És l'única operació que sempre es pot cridar.
• value() — retorna el valor de l'arrel. Cal que l'arbre no sigui buit.
• left() — retorna el subarbre esquerre. Cal que l'arbre no sigui buit.
• right() — retorna el subarbre dret. Cal que l'arbre no sigui buit.

No hi ha mètodes per modificar un arbre existent; les operacions que "canvien" l'arbre construeixen un nou BinTree (com veurem als exemples).

Exemples molt senzills: crear arbres buits, d'un node i amb fills

Els exemples següents mostren com es construeixen arbres a partir dels constructors. Tots els exemples requereixen:

#include "bintree.hh"
using namespace pro2;

Per crear arbres cal fer servir algun dels 3 constructors:

// Arbre buit
BinTree<int> a;

// Arbre amb un sol node (valor 1), sense fills
BinTree<int> b(1);

// Arbre amb arrel 0, fill esquerre buit (a) i fill dret b (el node 1)
BinTree<int> c(0, a, b);

Ara c és un arbre amb arrel 0, subarbre esquerre buit i subarbre dret format per un únic node amb valor 1. Per consultar-lo:

c.empty()   // false
c.value()   // 0
c.left()    // BinTree<int> buit (equivalent a a)
c.right()   // BinTree<int> amb un sol node de valor 1
c.right().value()         // 1
c.right().empty()         // false
c.right().left().empty()  // true (el fill esquerre del node 1 és buit)

Un altre exemple: un arbre amb tres nodes en forma de "V" (arrel 10, fill esquerre 20, fill dret 30):

BinTree<int> fulla_esq(20);
BinTree<int> fulla_dreta(30);
BinTree<int> arbre(10, fulla_esq, fulla_dreta);

Com que no hi ha operacions per alterar un BinTree després de construir-lo, tot el que fem amb arbres (cerques, recorreguts, càlculs) es fa amb funcions que reben l'arbre (típicament per valor) i retornen un resultat o en construeixen un de nou.

Exemples de funcions sobre arbres binaris

Sobre un BinTree<T> es poden implementar moltes operacions recursives: cerques, transformacions que construeixen un nou arbre, etc.

Alçada d'un arbre

L'alçada d'un arbre binari es defineix recursivament: un arbre buit té alçada 0; un arbre no buit té alçada 1 més el màxim de les alçades dels fills esquerre i dret. Això es tradueix directament en codi:

template<typename T>
int height(BinTree<T> t) {
    if (t.empty()) {
        return 0;
    }
    int hleft = height(t.left());
    int hright = height(t.right());
    return 1 + max(hleft, hright);
}

Aquí fem servir template<typename T> en una funció (no en una classe com hem vist amb Stack<T> o Queue<T>). En funcions, el compilador dedueix automàticament T a partir dels arguments.

En aquest cas no cal immersió perquè la signatura (arbre → enter) és suficient per expressar la recurrència.

Cerca d'un enter

Comprovar si un valor x apareix en l'arbre: si l'arbre és buit, no hi és; si el valor de l'arrel coincideix amb x, hi és; si no, es busca en el fill esquerre o en el fill dret.

bool cerca(const BinTree<int>& t, int x) {
    if (t.empty()) {
        return false;
    } else if (t.value() == x) {
        return true;
    } else {
        return cerca(t.left(), x) || cerca(t.right(), x);
    }
}

En aquest exemple és important recordar que l'operador || de C++, quan a l'esquerra té un valor cert, ja no avalua la part dreta, comportament que realitza una autèntica cerca perquè no recorrerà tots els nodes de l'arbre.

Sumar $k$ a tots els nodes

Construïm un nou arbre amb la mateixa estructura però amb cada valor incrementat en k. Si l'arbre és buit, retornem un arbre buit; si no, construïm un nou node amb value()+k i amb els subarbres transformats recursivament.

BinTree<int> add(const BinTree<int>& t, int k) {
    if (t.empty()) {
        return t;
    }
    auto left = add(t.left(), k);
    auto right = add(t.right(), k);
    return BinTree<int>(t.value() + k, left, right);
}

Intersecció de dos arbres

Donats dos arbres binaris d'enters, podem definir un arbre "intersecció" que només té nodes on ambdós arbres tenen el mateix valor en la mateixa posició estructural. Si un dels dos és buit o els valors de l'arrel no coincideixen, retornem un arbre buit; si no, construïm un node amb el valor comú i amb la intersecció dels fills esquerres i la intersecció dels fills drets.

BinTree<int> intersect(const BinTree<int>& ta, const BinTree<int>& tb) {
    if (ta.empty() || tb.empty() || ta.value() != tb.value()) {
        return BinTree<int>();
    }
    auto left = intersect(ta.left(), tb.left());
    auto right = intersect(ta.right(), tb.right());
    return BinTree<int>(ta.value(), left, right);
}

Recorreguts en arbres

Un recorregut és un ordre en què visitem tots els nodes. En un arbre binari, en cada node podem triar quan visitar l'arrel respecte dels fills. Això dóna tres ordres clàssics: visitar l'arrel abans dels fills (preordre), entre els dos fills (inordre), o després dels fills (postordre).

Preordre

Visitarem primer l'arrel i després recursivament el subarbre esquerre i el subarbre dret. Això s'anomena preordre (el prefix "pre" indica que l'arrel va abans dels fills).

template<typename T>
void preorder(const BinTree<T>& t) {
    if (!t.empty()) {
        cout << t.value() << ' ';
        preorder(t.left());
        preorder(t.right());
    }
}

Aquí hem fet servir template perquè en comptes d'haver de definir preorder per a cada tipus d'arbre, una única plantilla de funció ens generarà totes les que es necessitin en funció de si s'utilitzen en un programa. A més, la plantilla de preorder determina, a partir del primer paràmetre, quin és el tipus T.

Inordre

En inordre visitem primer el fill esquerre, després l'arrel i després el fill dret. En un arbre binari de cerca, l'inordre dóna els elements ordenats.

template<typename T>
void inorder(const BinTree<T>& t) {
    if (!t.empty()) {
        inorder(t.left());
        cout << t.value() << ' ';
        inorder(t.right());
    }
}

Postordre

En postordre visitem primer els dos fills (esquerre i dret) i al final l'arrel. És útil quan el processament del node depèn del resultat dels fills (per exemple alliberar memòria o calcular una propietat des de les fulles cap amunt).

template<typename T>
void postorder(const BinTree<T>& t) {
    if (!t.empty()) {
        postorder(t.left());
        postorder(t.right());
        cout << t.value() << ' ';
    }
}

Reconstrucció d'un arbre binari a partir d'una seqüència

A partir d'una seqüència que representa un arbre (per exemple en preordre o en postordre), amb un símbol per als arbres buits (per exemple #), es pot reconstruir l'arbre amb recursió o amb una pila, segons l'ordre.

Reconstrucció des de preordre

Si tenim la seqüència en preordre (arrel, subarbre esquerre, subarbre dret), podem llegir un token: si és # o no hi ha més dades, retornem un arbre buit; si és un valor, el llegim, construïm recursivament el fill esquerre i el fill dret des del mateix flux, i retornem l'arbre amb aquests tres components. La funció auxiliar read_value utilitza istringstream (de <sstream>) per convertir un string en un valor de tipus T.

template <typename T>
T read_value(string text) {
    istringstream iss(text);
    T elem;
    iss >> elem;
    return elem;
}

template <typename T>
pro2::BinTree<T> bintree_from_preorder(istream& in) {
    string token;
    in >> token;
    if (token == "#" || !in) {
        return pro2::BinTree<T>();
    }
    T value = read_value<T>(token);
    auto left = bintree_from_preorder<T>(in);
    auto right = bintree_from_preorder<T>(in);
    return pro2::BinTree<T>(value, left, right);
}

Reconstrucció des de postordre

Per reconstruir a partir d'una seqüència en postordre (subarbre esquerre, subarbre dret, arrel), no és tan directe amb recursió perquè l'arrel arriba al final. Una manera natural és usar una pila (amb stack de <stack> de la biblioteca estàndard): es llegeixen els tokens; si és #, s'apila un arbre buit; si és un valor, es desapilen dos arbres (primer el dret, després l'esquerre), es construeix l'arbre amb arrel el valor llegit i fills aquests dos arbres, i s'apila. Al final queda un sol element a la pila, que és l'arbre reconstruït.

template <typename T>
pro2::BinTree<T> bintree_from_postorder(istream& in) {
    stack<pro2::BinTree<T>> S;

    string token;
    while (in >> token) {
        if (token == "#" || !in) {
            S.push(pro2::BinTree<T>());
        } else {
            T value = read_value<T>(token);
            assert(S.size() >= 2);
            auto right = S.top();
            S.pop();
            auto left = S.top();
            S.pop();
            S.push(pro2::BinTree<T>(value, left, right));
        }
    }

    assert(S.size() == 1);
    return S.top();
}

La immersió és necessària en moltes funcions recursives d'arbres

Arbre equilibrat

Volem determinar si un arbre binari és equilibrat: un arbre buit es considera equilibrat, i un arbre no buit ho és si la diferència d'alçades entre el fill esquerre i el dret és com a màxim 1 i, a més, ambdós subarbres són equilibrats.

Una implementació directa (ingènua) seria: per cada node, calculem l'alçada del fill esquerre, l'alçada del fill dret, comprovem que la diferència sigui ≤ 1 i que els dos subarbres siguin equilibrats (cridant recursivament balanced).

bool balanced(BinTree<int> t) {
    if (t.empty()) {
        return true;
    } else {
        int hleft = height(t.left());
        int hright = height(t.right());
        return abs(hleft - hright) <= 1 &&
            (balanced(t.left()) && balanced(t.right()));
    }
}

El problema és el cost: en un arbre lineal (per exemple només fills esquerres), per a cada node calculem l'alçada d'un subarbre, i això implica recórrer tot aquell subarbre. En total, es fa una quantitat de treball proporcional a $\Theta(n^2)$ on $n$ és el nombre de nodes (podeu pensar-ho com la suma $1+2+\ldots+n$). Això és massa ineficient.

La solució és retornar més d'un resultat des de la recursió: a més de si l'arbre és equilibrat, retornem la seva alçada. Així cada subarbre es recorre una sola vegada. Com que la funció que volem exposar és balanced(BinTree<int> t) → bool, introduïm una funció d'immersió que retorna una parella (equilibrat, alçada):

pair<bool, int> balanced__(BinTree<int> t) {
    if (t.empty()) {
        return {true, 0};
    } else {
        auto left = balanced__(t.left());
        auto right = balanced__(t.right());
        return {abs(left.second - right.second) <= 1 &&
                    left.first && right.first,
                1 + max(left.second, right.second)};
    }
}

bool balanced(BinTree<int> t) {
    return balanced__(t).first;
}

La funció d'immersió té un nom i una signatura diferents perquè no és compatible amb la interfície desitjada; el pair permet propagar la informació d'equilibri i alçada en una sola passada, evitant els recorreguts repetits.

Mitjana dels valors

Per calcular la mitjana dels valors emmagatzemats en un arbre binari de reals, una primera idea és fer la suma dels nodes, fer el nombre de nodes, i dividir: sum(t) / num_nodes(t). Això implica recórrer l'arbre dues vegades.

Podem evitar-ho retornant en una sola passada tant la suma com el nombre de nodes. De nou, la funció pública pot tenir la signatura que vulguem (per exemple average(BinTree<double> t) → double), i la funció d'immersió retorna un pair<double, int> (suma, mida):

pair<double, int> sum_and_size__(BinTree<double> t) {
    if (t.empty()) {
        return {0.0, 0};
    }
    auto left = sum_and_size__(t.left());
    auto right = sum_and_size__(t.right());

    double sum = t.value() + left.first + right.first;
    int size = 1 + left.second + right.second;
    return {sum, size};
}

double average(BinTree<double> t) {
    auto result = sum_and_size__(t);
    return result.first / result.second;
}

Així només es recorre l'arbre una vegada i es calcula la mitjana a partir del resultat de la funció d'immersió.

Recorregut en amplada

El recorregut en amplada (o per nivells) visita primer l'arrel, després tots els nodes de nivell 1, després tots els de nivell 2, etc. Això no es pot fer amb una recursió simple que vagi "cap avall", perquè hem de processar tots els nodes del mateix nivell abans de baixar. La solució és usar una cua: s'encua l'arrel, i mentre la cua no sigui buida es treu un node, es processa i s'encuen els fills no buits. D'aquesta manera sempre processem els nodes en l'ordre de nivell.

Aquesta funció és iterativa, no recursiva (utilitza queue de <queue> de la biblioteca estàndard):

template<typename T>
void breadth_first(BinTree<T> t) {
    if (t.empty()) {
        return;
    }
    queue<BinTree<T>> Q;
    Q.push(t);
    while (!Q.empty()) {
        BinTree<T> curr = Q.front();
        Q.pop();
        cout << curr.value() << ' ';
        if (!curr.left().empty()) {
            Q.push(curr.left());
        }
        if (!curr.right().empty()) {
            Q.push(curr.right());
        }
    }
}