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
//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);
albero.cpp
#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;
}
main.cpp
#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");
}