Arbres de Cerca i Maps

Els contenidors seqüencials són útils per emmagatzemar dades que volem processar en recorreguts, però solen ser una mala idea per cercar elements (amb l'excepció de la cerca dicotòmica).

Si en comptes de voler recórrer els elements d'un contenidor molt sovint, el que fem més és cercar, l'estructura de seqüència no és la millor. Tant map com set són contenidors amb un sol punt for: la cerca. En aquests contenidors afegirem i traurem elements, però en general l'única cosa que farem amb ells és buscar-los per algun criteri.

Part I: Arbres de Cerca (BSTs)

Un Arbre Binari de Cerca (BST per les seves sigles en anglès, Binary Search Tree) és un arbre binari on, per a cada node, es compleix la següent propietat fonamental:

• Tots els valors del subarbre esquerre són estrictament menors que el valor del node.
• Tots els valors del subarbre dret són estrictament majors que el valor del node.

Aquesta propietat d'ordenació permet fer operacions d'exploració i cerca de manera molt eficient, normalment en temps logarítmic $O(log\ n)$, ja que a cada pas podem descartar la meitat de l'arbre, de manera similar a la cerca dicotòmica en un vector ordenat.

Com ja hem vist la implementació i l'ús bàsic de la classe BinTree<T> en el tema anterior, aquí ens centrarem exclusivament en les operacions específiques que aprofiten la propietat de cerca. Totes aquestes operacions les realitzarem de manera funcional: en comptes de modificar l'arbre existent manualment, construirem i retornarem un arbre nou.

El recorregut en inordre visita tots els elements de menor a major

Una de les propietats més interessants d'un BST és que si fem un recorregut en inordre (visitar subarbre esquerre, després l'arrel, i finalment el subarbre dret), obtindrem tots els elements de l'arbre ordenats de menor a major.

void bst_inordre(BinTree<int> bst) {
    if (!bst.empty()) {
        bst_inordre(bst.left());
        cout << bst.value() << " ";
        bst_inordre(bst.right());
    }
}

El valor més petit d'un BST es troba baixant sempre cap a l'esquerra

El valor més petit d'un BST sempre es troba a l'extrem inferior esquerre de l'arbre. Per trobar-lo només cal començar per l'arrel i anar baixant contínuament pel subarbre esquerre fins a trobar un node que ja no tingui fill esquerre. Podem fer-ho fàcilment de manera iterativa:

int bst_minim(BinTree<int> bst) {
    assert(!bst.empty());
    if (bst.left().empty()) {
        return bst.value();
    }
    return bst_minim(bst.left());
}

El valor més gran d'un BST es troba baixant sempre cap a la dreta

Simètricament al mínim, el valor més gran d'un BST es troba a l'extrem inferior dret. En aquest cas podem programar-ho recurrentment per veure una alternativa a la iterativa: anem baixant pel subarbre dret fins a trobar un node sense fill dret.

int bst_maxim(BinTree<int> bst) {
    assert(!bst.empty());
    if (bst.right().empty()) {
        return bst.value();
    }
    return bst_maxim(bst.right());
}

La cerca en un BST descarta ràpidament subarbres sencers per aconseguir temps logarítmic

Gràcies a la propietat d'ordenació de l'arbre, la cerca d'un element és tremendament ràpida. Si estem buscant el valor x, comparem amb l'arrel: si x és menor, busquem "només" al subarbre esquerre; si és major, "només" al dret. En anar descartant branques senceres, el cost que té aquesta cerca és logarítmic, $O(log\ n)$ (si l'arbre està ben equilibrat). Això evita haver de revisar l'arbre complet en temps lineal $O(n)$ com fèiem amb els arbres binaris ordinaris.

bool bst_search(BinTree<int> bst, int x) {
    if (bst.empty()) {
        return false;
    }
    if (bst.value() == x) {
        return true;
    }
    return bst_search(bst.value() < x ? bst.left() : bst.right(), x);
}

La inserció funcional construeix un arbre nou i manté l'ordenació ignorant els repetits

Per inserir un element de forma que es mantingui la propietat de cerca, ens aprofitem de l'estil funcional immutable de la nostra classe BinTree<T>. Quan inserim construïm un arbre nou allà on trobem el lloc adient (quan arribem a un arbre buit). Si el valor ja hi és, retornem l'arbre intacte ignorant la inserció per evitar duplicats.

BinTree<int> bst_insert(BinTree<int> bst, int x) {
    if (bst.empty()) {
        return BinTree<int>(x);
    } else if (x < bst.value()) {
        return BinTree<int>(bst.value(), bst_insert(bst.left(), x), bst.right());
    } else if (x > bst.value()) {
        return BinTree<int>(bst.value(), bst.left(), bst_insert(bst.right(), x));
    }
    return bst;  // Si x == a.value(), retornem el mateix arbre
}

Cal tenir en compte que inserir elements seqüencialment en un BST pot fer que l'arbre quedi desequilibrat (per exemple, si inserim elements ja ordenats, obtindrem una estructura lineal on el cost de cerca passarà de ser logarítmic $O(log\ n)$ a lineal $O(n)$). El disseny i implementació d'arbres que s'equilibren automàticament cauen fora de l'àmbit d'aquesta assignatura i es veuran en assignatures posteriors.

Per poder veure com utilitzar totes aquestes funcions operant conjuntament sobre un mateix arbre, podeu descarregar el fitxer:

Part II: Diccionaris (Maps)

Els diccionaris, realment són contenidors de parelles, per tant, abans de poder-los entendre, cal entendre el tipus pair<A, B> de la STL.

El tipus pair<A, B> agrupa una tupla de dues dades de tipus possiblement diferents

La classe pair<A, B> és una tupla amb dos camps: first i second. Si la declaréssim nosaltres (no cal fer-ho), seria exactament així:

template<typename A, typename B>
struct pair {
    A first;
    B second;
};

Com es veu, és una plantilla, no una tupla, és a dir, cal proporcionar dos tipus A i B per tenir una tupla de veritat. Per exemple, pair<int, int> o pair<string, bool> són tipus de parella concrets.

El pair és útil per agrupar una parella de dades i no haver de declarar una tupla especial (tot i que abusar de pair pot afectar enormement la llegibilitat!).

pair<int, string> p1 = { 25, "twenty-five" };
pair<bool, char> p2 = { true, 'X' };

p1.first = 26;
p2.second = 'Y';

Un map<K, V> és un diccionari o taula associativa implementada internament amb un BST

Els diccionaris, mapes, o taules associatives (són la mateixa cosa), són un contenidor de parelles a on s'emmagatzema una taula que relaciona els elements de l'esquerra de cada parella (que s'anomenen les "claus"), amb els de la dreta (que s'anomenen "valors").

Un diccionari és com una funció parcial: donat el valor d'una clau, només hi haurà un possible valor associat.

• Compacte, ocupa el just espai necessari.
• Inserció: $O(log\ n)$.
• Cerca: $O(log\ n)$.

Un map<K, V> és un contenidor no-sequencial que, internament, utilitza un Arbre Binari de Cerca (BST), molt semblants als que hem vist a la primera part. En el map, però, l'arbre de cerca és molt més sofisticat ja que la inserció inclou operacions addicionals perquè l'arbre es mantingui equilibrat, de tal manera que la cerca en el map tingui la garantia de ser $O(log\ n)$. A més, en l'arbre de cerca intern d'un map, els nodes contenen elements de tipus pair<K, V>, i l'arbre manté ordenada la clau (del tipus K).

Així doncs, cada parella del pair<K,V> té els dos camps first i second i, en el map, els nodes s'organitzen segons la seva clau (first, de tipus K). El valor associat (second, de tipus V) només acompanya la clau dins cada node. L'interès del map és doncs, cercar, i l'utilitzarem sempre que en un programa fem moltes cerques sobre les mateixes dades.

Un map<K, V> està pensat per cercar per la clau, operació que aprofita les propietats del BST intern per ser molt ràpida ($O(log\ n)$), per tot seguit actualitzar o llegir el valor associat. Llavors, utilitzarem map quan necessitem cercar per claus. Si per contra volguéssim buscar elements pel valor associat, ens veuríem obligats a fer un recorregut complet del seu arbre intern, la qual cosa equivaldria a una cerca lineal $O(n)$.

En un map<K,V> no pot haver-hi dues claus iguals. Si s’intenta inserir un element amb la mateixa clau que un altre, l’operació no es realitza. Caldria modificar el valor de la clau existent.

Els mapes es poden inicialitzar indicant directament les parelles clau-valor

map<int, string> M = {
    {1, "one"},
    {10, "ten"},
    {100, "hundred"},
    {1000, "thousand"},
};

La cerca per clau en un diccionari aprofita l'arbre binari per assolir una màxima eficiència

Quan cridem l'operació de cerca, el diccionari guia l'exploració a través del seu BST intern (de forma molt semblant al que fem en la funció bst_search anterior), desestimant branques senceres gràcies a la clau que busquem, aconseguint ser molt eficient.

map<int, string>::iterator it = M.find(10);
if (it != M.end()) {
    cout << "El valor associat a " << (*it).first << " és " << it->second << endl;
} else {
    cout << "No s'ha trobat" << endl;
}

El mètode insert afegeix noves parelles però no substitueix el valor si la clau ja hi és

map<int, string> M;
M.insert({2, "two"});
M.insert({-20, "minus twenty"});

El tipus de retorn d’insert és curiós. És una parella en què el first és un iterator a l’element inserit i el second indica si realment s’ha inserit (perquè les claus no poden repetir-se).

L'operador d'índex per clau insereix un nou element per defecte en cas que no el trobi

map<string, int> M2 = {
    {"hundred", 100},
};
M2["one"] = 1;  // com M2.insert({"one", 1})
M2["ten"] = 10; // com M2.insert({"ten", 10})

// Cerca "hundred", i retorna el seu valor, tot bé.
int a = M2["hundred"];
cout << a << endl; // -> 100

// Cerca "fifty", NO la troba, i **insereix** un pair amb ("fifty", 0),
// el valor per defecte dels enters, i retorna el 0!!
int b = M2["fifty"];
cout << b << endl; // -> 0

Les propietats de l'operador d'índex permeten programar acumuladors molt breument

Comptar paraules:

string word;
map<string, int> word_counts;
while (cin >> word) {
    word_counts[word]++; // <----- Aquí passen moltes coses!!!
}

Paraules amb la mateixa longitud:

string word;
map<int, vector<string>> by_length;
while (cin >> word) {
    by_length[word.size()].push_back(word);
}

El codi anterior fa tot això (!):

• Cerca word.
• Si hi és, retorna una referència al contador d’aquella paraula.
• Si no hi és, crea un pair (word, 0), i retorna una referència al contador.
• Incrementa el contador.

Utilitzarem l'operador índex per acumular, o find si preferim cercar sense alterar el map

1. No volem/podem inserir (per exemple el map és const) -> utilitzar find.
2. La inserció és una acumulació? Utilitzar operator[] és més curt.
3. Si volem controlar la cerca i inserció: find + insert.

Per tant, l’operador [] als map fa una cerca, i si aquesta falla insereix un element. Si no volem això farem servir find.

Els iteradors ens capaciten per a recórrer fàcilment totes les claus de forma ordenada

Quan donem resultats, potser cal recórrer el map (però un cop ja hem utilitzat molt find i insert!).

L’operador ->: it->first és el mateix que (*it).first (i és més fàcil d’escriure). L’operador és el * (indirecció) i el . (accés a camp) a la vegada.

map<int, string> M;
// ... treballar amb M ...
for (auto it = M.begin(); it != M.end(); it++) {
    cout << "Clau: " << it->first
         << ", valor: " << it->second << endl;
}

Exemple 1: Ús d'un map per a comptar la freqüència de múltiples paraules

Llegir una seqüència de paraules i comptar quantes vegades ha sortit cadascuna:

#include <map>
#include <iostream>
using namespace std;

int main() {
    string word;
    map<string, int> word_count;
    while (cin >> word) {
        word_count[word]++;
    }
    // mostrar paraules amb el seu comptador
    for (auto it = word_count.begin(); it != word_count.end(); it++) {
        cout << it->first << ' ' << it->second << endl;
    }
}

Exemple 2: Freqüència de les paraules emmagatzemada i posteriorment reordenada pel comptador

#include <map>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    string word;
    map<string, int> counts;
    while (cin >> word) {
        counts[word]++;
    }
    vector<pair<int, string>> words;
    for (auto it = counts.begin(); it != counts.end(); it++) {
        words.push_back({ it->second, it->first }); // al revés!!
    }
    sort(words.begin(), words.end()); // ordena per `first`, després `second`
    for (auto w : words) {
        // `<paraula> <freqüència>`
        cout << w.second << ' ' << w.first << endl;
    }
}

Els conjunts ignoren els valors associats de les parelles i avaluen principalment la pertinença

Es podria utilitzar un map<K, bool> com a conjunt, però no fem servir el bool per a res; la mera presència d’un element implica que pertany al conjunt.

Com que en un conjunt no hi ha valors associats als elements, cercar un element és només mirar si pertany al conjunt o no.

• No hi ha repetits (perquè map no pot tenir-ne).
• Podem inserir en $O(log\ n)$.
• Podem cercar (determinar la pertinença) en $O(log\ n)$.

La classe set<T> és la implementació estàndard de conjunt a on no s'admeten repetits

• insert no insereix una parella, només la "clau" (l’element).
• find és quasi igual que a map.

set<int> primers = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
primers.insert(31);
primers.insert(37);

auto it = primers.find(15);
if (it == primers.end()) {
    cout << "15 no hi és" << endl;
}

for (int x : primers) {
    cout << x << endl;
}

Exemple: Càlcul de la mida del vocabulari comptant només les paraules diferents

Quantes paraules diferents hi ha hagut en una seqüència de paraules d’entrada?

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<string> S;
    string word;
    while (cin >> word) {
        S.insert(word); // Les repetides no s’insereixen realment
    }
    cout << S.size() << endl;
}

Exemple: Comptar el nombre de vegades que apareixen les paraules repetides en una seqüència

Quantes paraules d’una seqüència ja havien aparegut abans a la mateixa seqüència (repetides però no consecutives).

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<string> vistes;
    string paraula;
    int repetides = 0;
    while (cin >> paraula) {
        auto it = vistes.find(paraula);
        if (it != vistes.end()) {
            repetides++;
        } else {
            vistes.insert(paraula);
        }
    }
    cout << repetides << " paraules repetides" << endl;
}

Codi Font

Per poder veure com utilitzar totes aquestes funcions operant conjuntament, podeu descarregar els fitxers de demostració:

Taula de costos d’operacions en contenidors

$^1$ vector desordenat, afegim amb push_back.

$^2$ vector ordenat, cerca dicotòmica.

$^*$ Amortitzat: normalment és $O(1)$, però de vegades és $O(n)$.