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;
}
Can't talk, computing... 