#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "rbTree.h"
#include "bsTree.h"
#include <windows.h>


#define   MaxNumber  300000 
static int randArray[MaxNumber];     


main()
{
	int arrayInt[9] = {8,11,17,15,6,1,22,25,27};
	int i;
	rbTree T1,T2;
	bsTree T3;
	rbTreeNode n1;
	bsTreeNode n2;
	double start,end;
	double time,sum;
	printf("\n\n                   ****  紅黑樹、二叉搜索樹的實(shí)現(xiàn)和性能比較  ****\n\n");
	printf("\n按任意鍵繼續(xù)........");
	getchar();


	printf("\n                                 1. 插入測試：\n\n");
	printf("\n按任意鍵繼續(xù)........");
	getchar();


	printf("\n\n輸入 8，11，17，15，6，1，22，25，27，建立紅黑樹T1:  \n\n");
	T1 = RB_NewTree();
	for (i=0;i<9;i++)
	{
		RB_Insert(T1, arrayInt[i]);
	}
	printf("\n按回車鍵 輸出紅黑樹T1：\n");
	getchar();
	RB_Displiy_Tree(T1, RB_Pre_Disply);
	printf("\n按回車鍵輸出紅黑樹T1的黑高度......");
	getchar();
	printf("   BH(T1) = %d\n",Bh_Tree(T1));
	printf("\n按回車鍵繼續(xù)........");
	getchar();



	printf("\n                                 2. 刪除測試：\n\n");
	printf("\n按任意鍵繼續(xù)........");
	getchar();


	printf("\n\n刪除紅黑樹T1中Key=15的節(jié)點(diǎn):  \n\n");
	RB_Delete(T1, 15);
	printf("\n按回車鍵輸出刪除key = 15 后的紅黑樹T1......");
	getchar();
	RB_Displiy_Tree(T1, RB_Pre_Disply);
	printf("\n按回車鍵輸出刪除key = 15 后的紅黑樹T1的黑高度......");
	getchar();
	printf("   BH(T1) = %d\n",Bh_Tree(T1));
	printf("\n按回車鍵繼續(xù)........");
	getchar();
	RB_Delete_Tree(T1, RB_Post_Visit);

	printf("\n                                 3. 查找測試：\n\n");
	printf("\n按回車鍵繼續(xù)........\n");
	getchar();
	printf("\n隨機(jī)生成1－300,000之間300,000個(gè)不同自然數(shù)的數(shù)組randArray1......\n\n");
	newRandArray(randArray, 1, MaxNumber);
	printf("\n利用隨機(jī)數(shù)組randArray1建立紅黑樹 T2......\n\n");
	T2 = RB_NewTree_Rand(randArray, MaxNumber);
	printf("\n按回車鍵輸出紅黑樹T2的黑高度......");
	getchar();
	printf("\nBH(T1) = %d\n",Bh_Tree(T2));
	printf("\n按回車鍵在紅黑樹T2中查找Key=15000的節(jié)點(diǎn)......\n");
	getchar();
	start = (double)clock();
	start = start/(double)CLOCKS_PER_SEC;
	n1 = RB_SearchInTree(T2, 15000);
	//Sleep(1500);
	end = (double)clock();
	time = end/(double)CLOCKS_PER_SEC - start;
	if ( NULL != n1)
		printf("\n查找成功，輸出查找花費(fèi)時(shí)間time1 = %.20lf：\n\n",time);
	else
		printf("\n查找失敗，輸出查找花費(fèi)時(shí)間time1 = %.20lf：\n\n",time);
	printf("\n按回車鍵刪除釋放紅黑樹T2........");
	getchar();
	RB_Delete_Tree(T2, RB_Post_Visit);
	printf("\n按回車鍵繼續(xù)........\n");
	getchar();

	printf("\n生成1－300,000之間300,000個(gè)不同自然數(shù)的數(shù)組randArray2......\n");
	newRandArray(randArray, 1, MaxNumber);
	printf("\n利用隨機(jī)數(shù)組randArray2建立二叉搜索樹T3......\n");
	T3 = BS_NewTree_Rand(randArray, MaxNumber);
	printf("\n按回車鍵在二叉搜索樹 T3 中查找Key=15000的節(jié)點(diǎn)......\n\n");
	getchar();
	start = (double)clock();
	start = start/(double)CLOCKS_PER_SEC;
	n2 = BS_SearchInTree(T3, 15000);
	//Sleep(1500);
	end = (double)clock();
	time = end/(double)CLOCKS_PER_SEC - start;
	if ( NULL != n2)
		printf("\n查找成功，輸出查找花費(fèi)時(shí)間time2 = %.20lf：\n\n",time);
	else
		printf("\n查找失敗，輸出查找花費(fèi)時(shí)間time2 = %.20lf：\n\n",time);
	printf("\n按回車鍵刪除釋放二叉搜索樹T3........");
	getchar();
	BS_Delete_Tree(T3, BS_Post_Visit);
	printf("\n按回車鍵繼續(xù)........\n");
	getchar();

    printf("\n                                 4. 求平均時(shí)間：\n\n");
    printf("\n按回車鍵繼續(xù)........\n");
	getchar();

	printf("\n\n重復(fù) 5 次 3) 中操作，求在紅黑樹中查找Key=15000的節(jié)點(diǎn)的平均時(shí)間:  \n\n");
	sum = 0;
	for(i=0;i<6;i++)
	{
		newRandArray(randArray, 1, MaxNumber);
		T2 = RB_NewTree_Rand(randArray, MaxNumber);
		start = (double)clock();
	    start = start/(double)CLOCKS_PER_SEC;
		n1 = RB_SearchInTree(T2, 7);
		//printf("%d,\n",n1->rbkey);
		//Sleep(100);
		end = (double)clock();
	    time = end/(double)CLOCKS_PER_SEC - start;
		sum = sum + time;
		//RB_Displiy_Tree(T2, RB_Pre_Disply);
		//getchar();
		RB_Delete_Tree(T2, RB_Post_Visit);
	}
	printf("\n 紅黑樹中查找Key=15000的節(jié)點(diǎn)的平均時(shí)間time = %.20lf：\n\n",sum/(double)6);
	printf("\n 按回車鍵繼續(xù)........");
	getchar();



	printf("\n\n重復(fù) 5 次 3) 中操作，求在二叉搜索樹中查找Key=15000的節(jié)點(diǎn)的平均時(shí)間:  \n\n");
	sum = 0;
	for(i=0;i<6;i++)
	{
		newRandArray(randArray, 1, MaxNumber);
		T3 = BS_NewTree_Rand(randArray, MaxNumber);
		start = (double)clock();
	    start = start/(double)CLOCKS_PER_SEC;
		n2 = BS_SearchInTree(T3, 15000);
		//printf("%d,",n2->bskey);
		//Sleep(100);
		end = (double)clock();
	    time = end/(double)CLOCKS_PER_SEC - start;
		sum = sum + time;
		BS_Delete_Tree(T3, BS_Post_Visit);
	}
	printf("\n二叉搜索樹中查找Key=15000的節(jié)點(diǎn)的平均時(shí)間time = %.20lf：\n\n",sum/(double)6);
	printf("\n按回車鍵繼續(xù)........");
	getchar();


	printf("\n                    5. 修改紅黑樹算法并完成算法 OS_Key_Rank(T,k) ：\n\n");
	printf("\n按回車鍵繼續(xù)........");
	getchar();


	printf("\n\n輸入 1,2,3,4,5,6,7,8，建立紅黑樹T4......  \n\n");
	T1 = RB_NewTree();
	for (i=1;i<9;i++)
	{
		RB_Insert(T1, i);
	}
	printf("\n按回車鍵輸出紅黑樹T4：\n\n");
	getchar();
	RB_Displiy_Tree(T1, RB_Pre_Disply);
	printf("\n按回車鍵輸出紅黑樹T2的黑高度......");
	getchar();
	printf("\nBH(T4) = %d\n",Bh_Tree(T1));
	printf("\n按回車鍵繼續(xù)........");
	getchar();
	printf("\nk=6, 輸出OS_Key_Rank的返回值 OS_Key_Rank(T1, k) = %d\n",OS_Key_Rank(T1, 6));
	printf("\n按回車鍵刪除釋放紅黑樹T4........");
	getchar();
	RB_Delete_Tree(T1, RB_Post_Visit);
    printf("\n按回車鍵結(jié)束演示........");
	getchar();
}