Binary Search Tree C로 간단 구현

그러나.. 속도 무진장 느림..
Java의 Collections에 있는 binary_search의 1/100 도 안됨..
튜닝 엄청나게 해야 될것 같음..


/*
#include <stdio.h> #include <malloc.h> #include <string.h> #include <time.h> typedef struct _node { int elem; struct _node *left; struct _node *right; } node; node *insert( int key, node *base, int *num ); node *search( int key, node *base ); void initNode( int key, node *rootNode ); int main(void ) { clock_t startTime, endTime; double nProcessExcuteTime; node *rootNode = ( node *)malloc(sizeof(node)); int i, num = 0; initNode( 0, rootNode ); for( i = 0; i < 10000; i++ ) { insert( i, rootNode, &num ); } startTime = clock(); for( i = 0; i < 10000; i++ ) { search( i, rootNode ); } endTime = clock(); nProcessExcuteTime = ( (double)(endTime - startTime) ) / CLOCKS_PER_SEC; printf("Excute time: %f\n", nProcessExcuteTime); return 0; } node *search( int key, node *base ) { node *s; s = base->left; while( key != s->elem && s != NULL ) { if( key < s->elem ) { s = s->left; } else { s = s->right; } } if( s == NULL ) return NULL; else return s; } node *insert( int key, node *base, int *num ) { node *p, *s; p = base; s = base->left; while( s != NULL ) { p = s; if( key < s->elem ) { s = s->left; } else { s = s->right; } } if( (s = ( node *)malloc(sizeof(node))) == NULL ) { return NULL; } initNode( key, s ); if( key < p->elem || p == base ) { p->left = s; } else { p->right = s; } (*num)++; return s; } void initNode( int key, node *rootNode ) { rootNode->elem = key; rootNode->left = NULL; rootNode->right = NULL; }