二分探索木

/****************************/
/* 二分探索木               */
/*      coded by Y.Suganuma */
/****************************/
#include <stdio.h>
#include <time.h>
#include <set>
#include "MT.h"

using namespace std;

/********************/
/* クラスListの定義 */
/********************/
class List
{
		int st;
		List *left, *right;

	public :
				// コンストラクタ
		List ()
		{
			st    = -1;
			left  = NULL;
			right = NULL;
		}

		List (int s)
		{
			left  = NULL;
			right = NULL;
			st    = s;
		}

		int add(List *);   // データの追加
		int search(int);   // データの探索
};

/***************************************/
/* データの追加                        */
/*      dt : Listクラスのオブジェクト  */
/*      return : =1 : 追加             */
/*               =0 : 同じデータが存在 */
/***************************************/
int List::add(List *dt)
{
	List *lt = this;
	int sw = -1;
					// トップ
	if (lt->st < 0) {
		lt->st = dt->st;
		sw = 1;
	}
					// トップでない
	else {
		while (sw < 0) {
			int k = dt->st - lt->st;
							// 同じデータがある
			if (k == 0)
				sw = 0;
							// 大きい
			else if (k > 0) {
				if (lt->right == NULL) {
					lt->right = dt;
					sw        = 1;
				}
				else
					lt = lt->right;
			}
							// 小さい
			else {
				if (lt->left == NULL) {
					lt->left = dt;
					sw        = 1;
				}
				else
					lt = lt->left;
			}
		}
	}

	return sw;
}

/***********************************/
/* データの探索                    */
/*      st : 数値                  */
/*      return : =1 : 見つかった   */
/*               =0 : 見つからない */
/***********************************/
int List::search(int st)
{
	List *lt = this;
	int sw = 0;

	if (lt->st >= 0) {
		while (sw == 0 && lt != NULL) {
			int k = st - lt->st;
					// 見つかった
			if (k == 0)
				sw = 1;
					// 次のデータ
			else if (k > 0)
				lt = lt->right;
			else
				lt = lt->left;
		}
	}

	return sw;
}

/****************/
/* main program */
/****************/
int main ()
{
	int n = 0, s[100000];
	List base;
					// データの追加
	printf("二分探索木\n");
	clock_t tm1 = clock();
	for (int i1 = 0; i1 < 5000000; i1++) {
		int k    = genrand_int31();
		List *lt = new List(k);
		int sw   = base.add(lt);
		if (sw > 0) {
			if (i1%50 == 0 && n < 100000) {
				s[n] = k;
				n++;
			}
		}
		else
			i1--;
	}
	clock_t tm2 = clock();
	printf("   保存： %d ms\n", (int)(tm2-tm1));
					// 探索
	for (int i1 = 0; i1 < n; i1++)
		base.search(s[i1]);
	clock_t tm3 = clock();
	printf("   探索： %d ms\n", (int)(tm3-tm2));
					// データの追加（set）
	printf("set\n");
	n = 0;
	set<int> st;
	for (int i1 = 0; i1 < 5000000; i1++) {
		int k = genrand_int31();
		pair<set<int>::iterator, bool> sw = st.insert(k);
		if (sw.second) {
			if (i1%50 == 0 && n < 100000) {
				s[n] = k;
				n++;
			}
		}
		else
			i1--;
	}
	clock_t tm4 = clock();
	printf("   保存(set)： %d ms\n", (int)(tm4-tm3));
					// 探索
	for (int i1 = 0; i1 < n; i1++)
		st.find(s[i1]);
	clock_t tm5 = clock();
	printf("   探索(set)： %d ms\n", (int)(tm5-tm4));

	return 0;
}