/*
	kreator
	Wed Dec  1 19:48:36 MET 1999
*/

#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <time.h>
#include <sys/timeb.h>

#define MYMAXSIZE 10000
#undef DEBUG

typedef struct node_type
{
	long element;
	struct node_type *left, *right;
} node;

node *create(node *root, long *element)
{
	int direction;
	if (!root)
	{
		root=(node *)malloc(sizeof(node));
		root->element=*element;
		root->left=root->right=0;
	} else if ((direction=*element-root->element)<0)
		root->left=create(root->left, element);
			else if (direction>0) 
				root->right=create(root->right, element);
	return root;
}

void search(node const *root, long *data)
{
	if (root)
	{
		search(root->left, data);
		if (!(root->element-*data))
			/* printf("%ld found at %p address\n", root->element,
				&root->element); */
		search(root->right, data);
	}
}

int main(void)
{

	long a, b, i, iter;

	srandom(time(NULL));

	printf("Molim unijeti donju i gornju granicu\n");
	scanf("%ld %ld", &a, &b);

	printf("Molim unijeti broj iteracija\n");
	scanf("%ld", &iter);
	for(i=0; i<iter; ++i)
	{
		long j, mysize=random()%MYMAXSIZE+1, *polje;
		struct timeb tajmi1, tajmi2;
		node *root;

		printf("Iteracija %ld:\n", i);

		if ((polje=malloc((mysize+1)*sizeof(long)))==NULL)
			continue;
	

		printf("\tPolje je velicine %ld\n", mysize);

#ifdef DEBUG
		printf("\tStvaranje slucajnih brojeva\n");

#endif
		for (j=0; j<mysize; ++j)
			*(polje+j)=random()%(b-a+1)+a;

#ifdef DEBUG
		printf("\tStvaranje binarnog stabla\n");
#endif
		for (j=0; j<mysize; ++j)
			root=create(root, polje+j);

#ifdef DEBUG
		printf("\tMjerenje vremena...\n");
#endif
		ftime(&tajmi1);
                for (j=0; j<mysize; ++j)
                        search(root, polje+j);
		ftime(&tajmi2);
		printf("\tPotrebno vrijeme bilo je %ld sekundi i %hu"
				" milisekundi\n", tajmi2.time-tajmi1.time,
				tajmi2.millitm-tajmi1.millitm);
	
	}
		
	return EXIT_SUCCESS;
}