Codice su pastebin: http://pastebin.com/wq65fpZv
Download del codice: http://pastebin.com/download.php?i=wq65fpZv
QVector<myStruct> buildBSTOnArray(QVector<myStruct> vettoreInput){ //fase di costruzione dell'albero binario di ricerca bilanciato su vettore //prelevo il numero di endpoint memorizzati int dimensione=vettoreInput.size(); //calcolo il livello dell'albero che incomincia a contenere le foglie dell'albero bilanciato int livello_i=(int)floor(log2((double)dimensione)); //calcolo poi quanti elementi usualmente stanno in un albero pieno di quel livello int elementiLivello_i=(int)pow(2.0,livello_i); //scopro quanti nodi del livello i 'passano' da foglie a padri per delle foglie del livello i+1 int nodiLivello_i= dimensione-elementiLivello_i; //Calcolo quanti elementi devo spostare in coda al vettore per ottenere la rappresentazione corretta dell'albero int foglieLivello_ip1= nodiLivello_i*2; //...e quindi effettuo, se necessario, gli spostamenti int i; //vettore risultato contenente il BST QVector<myStruct> vettoreBST; myStruct nodo; //////////fase di valorizzazione delle foglie if(foglieLivello_ip1>0){ //se il numero di foglie non è una potenza di 2, allora devo spostare i primi 'foglieLivello_ip1' elementi in fondo al vettore //oppure portare in testa gli elementi dopo i primi 'foglieLivello_ip1' elementi for(i= foglieLivello_ip1;i<=dimensione-1;i++){ nodo.key=vettoreInput[i].getKey(); nodo.isLeaf=true; //Aggiungo il nodo vettoreBST.push_back(nodo); } //ora aggiungo i primi elementi for(i=0;i<=foglieLivello_ip1-1;i++){ nodo.key=vettoreInput[i].getKey(); nodo.isLeaf=true; //Aggiungo il nodo vettoreBST.push_back(nodo); } }else{ //ho un numero di foglie pari ad una potenza di 2 e non devo spostare nulla, li copio semplicemente in fondo al vettore for(i=0;i<=dimensione-1;i++){ nodo.key=vettoreInput[i].getKey(); nodo.isLeaf=true; //Aggiungo il nodo vettoreBST.push_back(nodo); } } //////////fase di valorizzazione dei nodi interni //Si effettua la costruzione 'bottom-up' dell'albero valorizzando tutti i nodi padre delle foglie precedentemente inserite //'Puntatori' a figli sinistro e destro per un particolare nodo genitore int leftC,rightC; //Inizializzazione dei puntatori ai figli sinistro e destro: inizialmente corrispondono agli ultimi due elementi del vettore finora riempito con delle 'foglie' leftC=dimensione-2; rightC=dimensione-1; //costruzione 'bottom-up' for(i=dimensione-1;i>0;i--){ //indico che non è una foglia del bst nodo.isLeaf=false; //aggiungo il nodo padre vettoreBST.push_front(nodo); //decremento i 'puntatori' ai figli per provedere con la costruzione 'bottom-up' leftC--; rightC--; }//fine for padri //valorizzazione dei campi key dei nodi padre(interni), che permettono la ricerca all'interno dell'albero binario bilanciato for(i=0;i<=dimensione-2;i++){ //valorizzo per ogni nodo padre il valore key che mi permette di condurre la ricerca //la chiave per i nodi padre sarà il valore chiave dell'ultima foglia del suo sottoalbero sinistro int indice=i; indice=indice*2+1;//vado al figlio sinistro //mi sposto nei sotto alberi destri while(!(vettoreBST[indice].isLeaf)){ indice=indice*2+2; } //ora ho la chiave da memorizzare nel nodo padre per condurre la ricerca vettoreBST[i].key=vettoreBST[indice].key; } //restituisco il vettore contenente il BST return vettoreBST; }
