Range tree, Segment Tree, Windowing and 2D range queries : a Qt/C++ implementation

Works on Windows(tested on 7) and Linux(tested on ubuntu 10.04).
(2012/01: and also Mac Os X Snow Leopard!).

You may want to download Qt sdk (and MinGW if you are on windows, or install g++ on linux)
Download Qt SDK(go LGPL!)
After installing Qt SDK, open the file ‘segmentTree.pro’, you can find it in the source code folder.

This is a good example of how you can find and select objects on a plane, like your desktop server/manager does(think about your  program icons).

More Theory here.

Annunci

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

Balanced binary search tree on array

This is a translation of my last post.

[versione italiana qui]
[pseudo-code here]

A subject treated by many sites, but treated incompletely.
I try to give a taste of how to deal with the implementation on array (vector), usually a sequential data structure, of a non-linear structure as the binary tree, particularly balanced binary search tree.”This method benefits from more compact storage, no pointers needed reducing the amount of space required for the tree, and better locality of reference


[pseudo-code here]

Alberi binari di ricerca su array

Un argomento trattato da molti siti, ma trattato in maniera incompleta.
Tento di dare un assaggio di come si possa affrontare l’implementazione su array (vettore ), struttura solitamente sequenziale, di una struttura non lineare quale l’albero binario, in particolare di ricerca e bilanciato.
Questo metodo permette una memorizzazione più compatta, meno dispendiosa in termini di occupazione( non è necessario l’uso di puntatori) e garantisce una migliore località.