Per què una nova classe?
Realment per moltes raons. La classe Arbre era una porqueria. És la típica que implementes tu, i et posen mala nota. I per moltes raons
Els comentaris
Sí, sembla una raó superficial, però jo sóc el típic que, quan utilitzo una classe, m'agrada saber bé com funciona. I amb aquesta, que a més el PDF era fluixet, doncs m'agradava mirar-me el .hh. I venien ganes de plorar. No pots posar la capçalera de la funció, un comentari al mig, i després el cos de la funció. És com partir la funció entre dos. Una mica com l'AVE de Múrcia.
Deixant de banda que el comentari sembla un embarbussament, oi que talla la funció d'una manera que no és normal?
Noms de les funcions
En general estaven molt mal triats. Una funció per buidar un arbre que es diu a_buit, una per modificar-lo que es diu plantar, una que es diu arrel... Poc abans de l'examen, em van dir una cosa que ho representa bastant bé. "plantar, arrel... Això és programació o jardineria?"
Funcionament de la classe
Així com les dues raons anteriors no tenen gaire importància, aquesta en té, i molta. Com funciona la classe per dins?
Com podem veure si ens mirem el .hh, que suposo que penjaré a algun lloc (encara que si es perd per sempre, tampoc perdrem gaire), declarem una struct que es diu node_arbre, que conté dos node_arbre* i la informació d'aquell node. És a dir, la idea és que la classe té una sèrie de nodes, i cada node conté dos punters pels següents nodes, i un valor. I, com a únic atribut de la classe, un punter que apunta al primer node.
Aleshores, un arbre podem dir que conté un valor i dos fills, dret i esquerre. Què passa si volem accedir a aquests fills? Aquí ve la part divertida
La funció fills
La funció fills rep dos arbres buits i diferents, i el que fa és posar el fill esquerre al primer, i el fill dret al segon. I ja? No! No volien copiar tot el fill, ja que això té un cost massa gran. Podrien haver fet una funció que retorni cada fill per referència, de manera que es pugui consultar sense copiar l'arbre, però això era una bona solució.
Enlloc d'això, fan que per accedir als fills, es modifiqui l'arbre. Quan tu crides la funció fills, l'arbre actual es buida, el seu arbre esquerre se'n va al primer paràmetre, i el dret al segon. Per tant, primer de tot t'estan obligant a passar els arbres per referència normal, no constant, ja que si no els modifiques. I a sobre, t'obliguen a vigilar tu que al final de la funció l'arbre no s'hagi modificat.
Per exemple, imaginem que volíem implementar una funció comptar_nodes_arbre, que rep un arbre i compta quants nodes té. No volem fer cap modificació a l'arbre. Però ens obliguen a modificar-lo per fer la funció. I clar, era una font potencial d'errors
Per exemple, imaginem que volíem implementar una funció comptar_nodes_arbre, que rep un arbre i compta quants nodes té. No volem fer cap modificació a l'arbre. Però ens obliguen a modificar-lo per fer la funció. I clar, era una font potencial d'errors
La classe BinTree
Aquesta classe és una classe ben feta. Molt ben feta, de fet. Només li veig un error, que és utilitzar "using namespace std" a dins d'una capçalera. Com funciona?
Internament, té un punter a un node. Igual que a la classe Arbre, no? No! És un tipus de punter molt especial. És un shared_ptr. Veurem per què serveix això més tard (tot i que de moment no cal saber-ho)
Podem veure també que té quatre constructores.
BinTree (): Construeix un BinTree buit. Sense massa misteri
BinTree (const T& x): Construeix un BinTree que a l'arrel conté x, i no té fills
BinTree (const T& x, const BinTree& left, const BinTree& right): Construeix un BinTree que a l'arrel conté x, i té com a fills aquests dos arbres
BinTree (shared_ptr<Node> p): Serveix per construir un BinTree passant-li un punter. Tampoc cal saber per què cal, és una funció privada
Per altra banda, té una sèrie de funcions per treballar amb el BinTree, amb uns noms bastant ben triats respecte la classe antiga.
bool empty () const: Ens diu si és buit o no. Cost constant
BinTree left () const: Ens retrna el fill esquerre. Cost constant, no lineal com podríem pensar
BinTree right () const: Ídem amb el dret
const T& value () const: Ens retorna el valor. Cost constant també
Sembla bastant fàcil treballar amb ella, no? Ho és. L'únic difícil és entendre la recursivitat que envolta els arbres. Podem veure unes quantes coses que podem fer amb ells
Comptar nodes
int compta_nodes(BinTree<int> b) {
if (b.empty()) return 0;
return 1+compta_nodes(b.left())+compta_nodes(b.right());
}
Mola veritat? Si és buit, té 0 nodes (obvi). Si no, sabem que la quantitat de nodes de l'arbre serà la suma de la quantitat de nodes dels seus subarbres i ell mateix (1).
Incrementa en 1 tots els elements d'un arbre
void incrementa(BinTree<int>& b) {
if (b.empty()) return;
BinTree<int> left=b.left();
BinTree<int> right=b.right();
incrementa(left);
incrementa(right);
b=BinTree<int>(b.value()+1,left,right);
}
Senzill, veritat? Aquí veiem una cosa, i és que copio els subarbres dret i esquerre, i després faig una nova constructora. És perquè les funcions són const, i per tant, no podem modificar-ho. Igualment la constructora té temps constant, no ens hem de preocupar
Per altra banda, malgrat que tendim a fer això, jo penso que no és una opció massa bona. Hi ha una de millor, que seria
BinTree<int> i_incrementa(BinTree<int> b) {
return BinTree<int>(b.value()+1,incrementa(b.left()),incrementa(b.right()));
}
void incrementa(BinTree<int>& b) {
b=i_incrementa(b);
}
Per altra banda, malgrat que tendim a fer això, jo penso que no és una opció massa bona. Hi ha una de millor, que seria
BinTree<int> i_incrementa(BinTree<int> b) {
return BinTree<int>(b.value()+1,incrementa(b.left()),incrementa(b.right()));
}
void incrementa(BinTree<int>& b) {
b=i_incrementa(b);
}
Obté camí més llarg
En aquest cas farem que, per obtenir el camí més llarg, el guardi en una pila. En cas d'empat, agafarem el de l'esquerra. Ho podem fer així
stack<int> cami_llarg(BinTree<int> b) {
if (b.empty()) return stack<int>();
stack<int> left=cami_llarg(b.left());
stack<int> right=cami_llarg(b.right());
if (left.size()<=right.size()) {
left.push(b.value());
return left;
}
right.push(b.value());
return right;
}
Consells per treballar amb arbres
Treballar amb arbres és una cosa que a molta gent se li fa una muntanya. Però realment no és més difícil que la resta. De fet, jo crec que els problemes de llistes són més complicats que els d'arbres
Fonamentalment, per treballar amb arbres cal pensar de manera recursiva. Un exemple
Com llegim un arbre en preordre?
Ens diuen que un arbre en preordre és quan et donen l'arrel, després l'arbre esquerre, i finalment l'arbre dret. Doncs hem de programar exactament això. Llegim l'arrel, llegim dos arbres (utilitzant de manera recursiva la mateixa funció), i ja ho tenim.
Com calculem l'alçada d'un arbre?
Suposem que definim l'alçada d'un arbre com l'alçada del subarbre més alt +1. Així, un arbre buit tindria alçada 0, i a partir d'això, definim l'alçada de qualsevol arbre. Com ho calculem?
Primer de tot, el cas base. Un arbre buit té alçada 0, de manera que si ens demanen l'alçada d'un arbre buit, retornem 0. Si no, retornem 1+max(alçada1,alçada2). I per calcular aquestes dues alçades, cridem a la mateixa funció amb els subarbres esquerre i dret
Com sumem els elements d'un arbre?
En aquest cas faré directament el codi de la funció, perquè m'he cansat de descriure el que han de fer les funcions. Suposo que s'entén el que fa
int suma_nodes(BinTree<int> b) {
if (b.empty()) return 0;
return b.value+suma_nodes(b.left())+suma_nodes(b.right());
}
I un truc
Hi ha vegades que, pel que sigui, no ens funciona el pas per referència. Ens podem estar una bona estona per trobar l'error (perquè sí, serà un error). Però si no us voleu complicar la vida, podeu carregar-vos la referència, ja que la còpia d'un BinTree triga temps constant (que a més, no és gaire temps). Segurament afegir un const us arreglaria el problema, però per què?
