Binary Search Tree on Array : pseudo-C++/Qt-code (not really so ‘pseudo’)

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;
}

2 thoughts on “Binary Search Tree on Array : pseudo-C++/Qt-code (not really so ‘pseudo’)

  1. Pingback: Balanced binary search tree on array « Can't talk, computing…

  2. Pingback: Alberi binari di ricerca su array « Can't talk, computing…

Lascia un commento

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...