BST(二叉サーチツリー)

5905 ワード

BST(Binary Search Tree)目的は、検索の性能を向上させるために、平均と最悪の場合は両方ともlognレベルで、二分割検索に近い検索を行うことです.
各ノードの値は、その任意の左側のサブノードの値よりも大きく、その任意の右ノードの値よりも小さいことが特徴である.
三つの基本的な操作を紹介します.
予備操作:
typedef struct node{
	int value;
	char key;
	int Index;
	struct node *left;
	struct node *right;
}BSTNode,*PBSTNode;

1、

//       
PBSTNode  Get(PBSTNode root,char Key)
{
	if(!root)
		return NULL;
	if(Key == root->key)
		return root;
	else if(Key < root->key)
		return Get(root->left,Key);
	else
		return Get(root->right,Key);
}
2、ノードを して する.
//    
//------1.BSTree  -------------------------
//------2.BSTree     ,       
//------3.    ---------------------------
void BSTInsert(PBSTNode *root,char Key,int Value)
{
	//      
	if(!(*root))
	{
		(*root) = (PBSTNode)malloc(sizeof(BSTNode));
		(*root)->Index = 0;
		(*root)->key = Key;
		(*root)->value = Value;
		(*root)->left = (*root)->right = NULL;
		return;
	}
	PBSTNode Temp = (PBSTNode)malloc(sizeof(BSTNode));
	PBSTNode des = Get((*root),Key);
	//        
	if(des != NULL)
	{
		des->value = Value;
		return;
	}
	//      :
	PBSTNode Go = (*root);
	while(Go)
	{
		if(Go->key > Key)
		{
			if(!Go->left)
			{
				Temp->key = Key;
				Temp->value = Value;
				Temp->left = Temp->right = NULL;
				Go->left = Temp;
                //        。
				return;
			}
			else
				Go = Go->left;
		}//end of > situation
		else
		{
			if(!Go->right)
			{
				Temp->key = Key;
				Temp->value = Value;
				Temp->left = Temp->right = NULL;
				Go->right = Temp;
				return;
			}
			else
				Go = Go->right;
		}
	}
}
ノードという を してBSTツリーの ができます.
//         BSTree
PBSTNode CreateBSTree(char *data,int n)
{
	PBSTNode Root = NULL;
	if(n == 0)
		Root =  NULL;
	else
	{
		for(int i = 0;i < n;i++)
			BSTInsert(&Root,data[i],i);
	}
	return Root;
}
3、
//    :
//-------1、    ----------------------------------------------------------------------
//-------2、            ,      ,                   
//-------3、          ,      
//-------4、           ,          :
//-------------------------------------------------------1)                 
//-------------------------------------------------------2)                 
//   -1      。1    。
int Delete(PBSTNode * Root,char key)
{
	//     
	if((*Root)->key == key)
	{
		if(!(*Root)->left && (*Root)->right)
		{
			(*Root) = (*Root)->right;
			free((*Root));
			return 1;
		}
		else if((*Root)->left && !(*Root)->right)
		{
			(*Root) = (*Root)->left;
			free((*Root));
			return 1;
		}
		PBSTNode Min = (PBSTNode)malloc(sizeof(BSTNode));
		Min = (*Root)->right;
		PBSTNode ParentMin = (PBSTNode)malloc(sizeof(BSTNode));
		ParentMin = (*Root);
		while(Min->left)
		{
			ParentMin = Min;
			Min = Min->left;
		}
		ParentMin->left = Min->right;
		Min->left = (*Root)->left;
		Min->right = (*Root)->right;
		(*Root) = Min;
		return 1;
	}
	//              ,      Get  
	PBSTNode Parent = (*Root);
	PBSTNode Go = (*Root);
	while(Go)
	{
		if(Go->key == key)
			break;
		else if(Go->key > key)
		{
			Parent = Go;
			Go = Go->left;
		}
		else
		{
			Parent = Go;
			Go = Go->right;
		}
	}
	//Situation 1
	if(!Go)
		return -1;
	//Situation 2
	if(!Go->left && Go->right)
	{
		if(Parent->left == Go)
			Parent->left = Go->right;
		else
			Parent->right = Go->right;
		free(Go);
		return 1;
	}
	else if(Go->left && !Go->right)
	{
		if(Parent->left == Go)
			Parent->left = Go->left;
		else
			Parent->right = Go->left;
		free(Go);
		return 1;
	}
    //Situation 3
	else if(!Go->left && !Go->right)
	{
		if(Parent->left == Go)
			Parent->left = NULL;
		else
			Parent->right = NULL;
		free(Go);
		return 1;
	}
	//Situation 4
	//Choose Solution 1: Min right son
	else
	{
		PBSTNode Min = (PBSTNode)malloc(sizeof(BSTNode));
		Min = Go->right;
		PBSTNode ParentMin = (PBSTNode)malloc(sizeof(BSTNode));
		ParentMin = Go;
		while(Min->left)
		{
			ParentMin = Min;
			Min = Min->left;
		}
		if(Parent->left == Go)
		{
			Parent->left = Min;
			ParentMin->left = Min->right;
			Min->left = Go->left;
			Min->right = Go->right;
		}
		else
		{
			Parent->right = Min;
			ParentMin->left = Min->right;
			Min->left = Go->left;
			Min->right = Go->right;
		}
	}//end of else
	return 1;
}
は が いので です.
4、 り のすべてのデータ
//    ,            ,        
void  GetDatasFromField(PBSTNode Root,char LowKey,char MaxKey,PBSTNode *Result,int *count)
{
	if(!Root)
		return;
	if(Root->key > LowKey && Root->key < MaxKey)
	{
		Result[(*count)] = (PBSTNode)malloc(sizeof(BSTNode));
		Result[(*count)]->key = Root->key;
		Result[(*count)]->value = Root->value;  
		(*count)++;
		//                   
		GetDatasFromField(Root->left,LowKey,MaxKey,Result,count);
		GetDatasFromField(Root->right,LowKey,MaxKey,Result,count);
	}
	else if(Root->key < LowKey)
	{
		if(Root->key == LowKey)
		{
			Result[(*count)] = (PBSTNode)malloc(sizeof(BSTNode));
			Result[(*count)]->key = Root->key;
			Result[(*count)]->value = Root->value;
			(*count)++;
		}
		//       
		GetDatasFromField(Root->right,LowKey,MaxKey,Result,count);
	}
	else
	{
		if(Root->key == MaxKey)
		{
			Result[(*count)] = (PBSTNode)malloc(sizeof(BSTNode));
			Result[(*count)]->key = Root->key;
			Result[(*count)]->value = Root->value;
			(*count)++;
		}
		//       
		GetDatasFromField(Root->left,LowKey,MaxKey,Result,count);
	}
}