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);
}
}