[AIUTO] alberi binari di ricarca

[P_il_Musicante]

Salve a tutti!!
devo testare la complessità dell'insert search tree_minimum e tree maximum
il mio problema
per imput di dimesione elevata la memoria virtuale viene allocata tutta tipo p per imput di dimensione pari a 9*10^6
lascio il codice:
albero.h

<CODE>

//Predichiarazione della struct
struct nodo;
struct albero;


//Dichiarazione del tipo puntatore a nodo
typedef struct nodo* tree;
//Dichiarazione del tipo puntatore ad albero
typedef struct albero* ABR;


//Dichiarazione del tipo strutturato nodo
struct nodo {
int key;
tree genitore;
tree sinistro;
tree destro;

};
//Dichiarazine del tipo strutturato albero
struct albero{
tree root;
};


//PROTOTIPI delle funzioni utilizzate

void inizializza_nodo(tree n);
void inizializza_root(ABR T);
void set_ABR_root(ABR T, tree n);

void Inorder(tree x);
void Preorder(tree x);
void Postorder(tree x);
tree Tree_successor(tree x);



tree RicercaBin(tree x,int x);
tree RicercaIterativaBin(tree x,int k);
tree RicercaMin(tree x);
tree RicercaMax(tree x);
void Inserimento(ABR T,tree z);
tree Tree_delete(ABR T, tree z);


</CODE>





albero.cpp

<CODE>


#include "albero.h"
#include <stdlib.h>
#include <iostream>

using namespace std;


void inizializza_nodo(tree n){
n->key=0;
n->genitore=NULL;
n->sinistro=NULL;
n->destro=NULL;
}
void inizializza_root(ABR T){
T->root=NULL;

}



void Inorder(tree x)
// Funzione di visita di un'albero
{
if (x!=NULL) {
Inorder(x->sinistro);
cout<<x->key<<" ";
Inorder(x->destro);
}
}

void Preorder(tree x)
// Funzione di visita di un'albero
{
if (x!=NULL) {
cout<<x->key<<" ";
Preorder(x->sinistro);
Preorder(x->destro);
}
}

void Postorder(tree x)
// Funzione di visita di un'albero
{
if (x!=NULL) {
Postorder(x->sinistro);
Postorder(x->destro);
cout<<x->key<<" ";
}
}

/*
trova {succ,prede}cessore del nodo x
output: puntatore {succ,prede}cessore
*/
tree Tree_successor(tree x){
if(x->destro!=NULL)
return RicercaMin(x->destro);

tree y=x->genitore;
while( y!=NULL && x==y->sinistro){
x=y;
y=y->genitore;
}
return y;
}

tree Tree_predecessor(tree x){
if(x->sinistro!=NULL)
return RicercaMax(x->sinistro);

tree y=x->genitore;
while( y!=NULL && x==y->destro){
x=y;
y=y->genitore;
}
return y;
}


tree RicercaBin(tree x,int k)
// Ricerca per alberi binari di ricerca
{
if ((x==NULL)||(k==x->key))
return x;
else {
if (k < x->key)
return RicercaBin(x->sinistro,k) ;
else
return RicercaBin(x->destro,k) ;
}
}

tree RicercaIterativaBin(tree x,int k)
// Ricerca iterativa per alberi binari di ricerca
{
while ((x!=NULL)&&(k!=x->key))
{
if (k < x->key)
x=x->sinistro;
else
x=x->destro;
}
return x;
}

tree RicercaMin(tree x)
// Ricerca del minimo per alberi binari di ricerca
{
while (x->sinistro!=NULL)
{
x=x->sinistro;
return x;
}
}

tree RicercaMax(tree x)
// Ricerca del massimo per alberi binari di ricerca
{
while (x->destro!=NULL)
{
x=x->destro;
return x;
}
}

void Inserimento(ABR T,tree z)
// Costruisce un albero binario di ricerca
{
//Puntatore al padre
tree Y=NULL;

tree X=T->root;
//tree X=T;
while (X!=NULL)
{
Y=X;
if ( z->key < X->key)
X=X->sinistro;
else
X=X->destro;
}
z->genitore=Y;

if (Y==NULL)
T->root=z;

else
if (z->key < Y->key)
Y->sinistro=z;
else
Y->destro=z;
z->sinistro=NULL;
z->destro=NULL;


}


/*
cancella un nodo dall'albero

*/
tree Tree_delete(ABR T, tree z){
tree x=NULL;
tree y=NULL;



if( z->sinistro==NULL || z->destro==NULL){
y=z;
}else{
y=Tree_successor(z);
}

if(y->sinistro!=NULL){
x=y->sinistro;
}else{
x=y->destro;
}

if(x!=NULL)
x->genitore=y->genitore;

if(y->genitore ==NULL){
T->root=x;
}else{
if( y==(y->genitore)->sinistro){
(y->genitore)->sinistro=x;
}else{
(y->genitore)->destro=x;
}
}

if (y!=z){
z->key=y->key;
z->genitore=y->genitore;
z->sinistro=y->sinistro;
z->destro=y->destro;
}


return y;
}




</CODE>






main.cpp


<CODE>

#include "albero.h"
#include <iostream>
#include <stdlib.h>
#include <ctime>
#include <cstdlib>



using namespace std;


int main()
{

ABR T=new albero;
inizializza_root(T);
tree x=NULL;
tree found=NULL;
time_t t1,t2;
double media=0;
int dim;
int scelta;


do{
cout<<"\n SCEGLI LA FUNZIONE DI CUI VUOI TESTARE LA COMPLESSITA'";
cout<<"\n digita 1 per INSERT";
cout<<"\n digita 2 per SEARCH (ricorsiva)";
cout<<"\n digita 3 per SEARCH (iterativa)";
cout<<"\n digita 4 per uscire dal programma";
cout<<"\n ->";
cin>>scelta;
switch(scelta){
case 1:
cout<<"\n TEST INSERT";
cout<<"\n test di complessita' ";
cout<<"\n inserisci la dimensione dell'input ->";
cin>>dim;

media=0;
cout<<"\n";
for(int h=0;h<10;h++){
//Crea l'albero di dim elementi
for (int i=0;i<dim;i++){

x=new nodo;
inizializza_nodo(x);

x->key=rand();

if(i==0)
t1=time(NULL);
Inserimento(T,x);

//Inorder(x);
}
t2=time(NULL);
cout<<"tempo della "<<h+1<<" prova: ";
cout<<difftime(t2,t1);
cout<<"\n";
// devo inserire una funzione per liberare la memoria
cout<<"tempo per deallocare la memoria...\n\n";

media=media+difftime(t2,t1);
}

cout<<"\n media dei tempi -> "<<media/10<<"\n\n";
cout<<"\n\n";

break;


case 2:
cout<<"\n TEST SEARCH";
cout<<"\n test di complessita' ";
cout<<"\n inserisci la dimensione dell'input ->";
cin>>dim;



cout<<"\n --------caso ricorsivo---------> \n";
//Crea l'albero di dim elementi
for (int i=0;i<dim;i++){

x=new nodo;
inizializza_nodo(x);

x->key=rand();

Inserimento(T,x);

}
//Inserisce l'elemento 1234567890
x=new nodo;
inizializza_nodo(x);
x->key=1234567890;
Inserimento(T,x);

media=0;
for(int h=0;h<10;h++){
t1=time(NULL);
found=RicercaBin(x,1234567890);
t2=time(NULL);
cout<<"tempo della "<<h+1<<" prova: ";
cout<<(long double)difftime(t2,t1);
cout<<"\n";
media=difftime(t2,t1)+media;
}
cout<<"\n media dei tempi -> "<<media/10<<"\n\n";

cout<<"\n\n";
break;


case 3:
cout<<"\n TEST SEARCH";
cout<<"\n test di complessita'";
cout<<"\n inserisci la dimensione dell'input ->";
cin>>dim;


cout<<"\n --------caso iterativo----------> \n";
x=new nodo;
inizializza_nodo(x);
x->key=1234567890;

Inserimento(T,x);
//Crea l'albero di dim elementi
for (int i=0;i<dim;i++){

x=new nodo;
inizializza_nodo(x);
x->key=rand();
Inserimento(T,x);
}
media=0;
for(int h=0;h<10;h++){
t1=time(NULL);
found=RicercaIterativaBin(x,1234567890);
t2=time(NULL);
cout<<"tempo della "<<h+1<<" prova: ";
cout<<(long double)difftime(t2,t1);
cout<<"\n";
media=difftime(t2,t1)+media;
}
cout<<"\n media dei tempi -> "<<media/10<<"\n\n";

cout<<"\n\n";
break;


case 4:

exit(0);
break;

}
}while((scelta>0)&&(scelta<5));

cout<<"\n Errore di digitazione \n";

cout<<"\n\n\n\n\n";





system("PAUSE");


}


</CODE>

ho utilizzato il C++
se è possibile utilizzare altri comandi per allocare la struttura tipo malloc (ke io nn so utilizzare) e free
aiutatemi please!!!!!
potreste consigliarmi come fare
GRAzie

[Furla]

non capisco quale sia il problema...