プログラミングコンテストやAIZU ONLINE JUDGE向けです。
最初に一定量のメモリを確保し、それを超えたら挿入しない仕組みです。
とりあえず整数のキー、データの検索と挿入(と初期化)のみできます。
関数の説明
void rbt_init(void)
赤黒木を初期化します。
int rbt_search(int searchfor)
赤黒木からキーがsearchforである要素を探し、その要素のデータを返します。
見つからなかったら-1を返します。
int rbt_insert(int key,int data)
赤黒木にキーがkey、データがdataである要素を挿入します。
キーがkeyである要素がすでに存在する場合、その要素のデータをdataで上書きします。
void rbt_print(int youso,int kaisou)
赤黒木の構造を表示します。デバッグ・テスト用です。
根から表示する場合は、rbt_brint(0,-1)として呼び出します。
ソースコード(C言語)
#include <stdio.h>
#include <string.h>
/*構造を、挿入するたびに表示するなら真にする*/
#define DO_REALTIME_DISPLAY 1
/*赤黒木メインコードここから*/
#define TREE_MAX 10000
typedef struct {
int key;
int data;
int isred;
int parent;
int left;
int right;
} rbt_node_t;
int rbt_node_used;
rbt_node_t rbt_node[TREE_MAX+1];
void rbt_init(void) {
rbt_node_used=1;
memset(rbt_node,0,sizeof(rbt_node));
rbt_node[0].key=-0x7fffffff;
}
int rbt_search(int searchfor) {
int pos=rbt_node[0].right;
while(pos>0) {
if(rbt_node[pos].key==searchfor) {
return rbt_node[pos].data;
} else if(rbt_node[pos].key<searchfor) {
pos=rbt_node[pos].right;
} else {
pos=rbt_node[pos].left;
}
}
return -1;
}
int rbt_insert(int key,int data) {
int pos=0;
int parent,p_parent,p_left,p_right;
int pp_parent,pp_left,pp_right;
while(1) {
if(rbt_node[pos].key==key) {
rbt_node[pos].data=data;
return 1;
} else if(rbt_node[pos].key<key) {
if(rbt_node[pos].right==0)break;
pos=rbt_node[pos].right;
} else {
if(rbt_node[pos].left==0)break;
pos=rbt_node[pos].left;
}
}
if(rbt_node_used>TREE_MAX)return 0;
rbt_node[rbt_node_used].key=key;
rbt_node[rbt_node_used].data=data;
rbt_node[rbt_node_used].isred=1;
rbt_node[rbt_node_used].parent=pos;
rbt_node[rbt_node_used].left=0;
rbt_node[rbt_node_used].right=0;
if(rbt_node[pos].key<key) {
rbt_node[pos].right=rbt_node_used;
} else {
rbt_node[pos].left=rbt_node_used;
}
pos=rbt_node_used;
rbt_node_used++;
while(pos>0) {
if(rbt_node[pos].parent==0) {
rbt_node[pos].isred=0;
break;
}
parent=rbt_node[pos].parent;
p_parent=rbt_node[parent].parent;
p_left=rbt_node[parent].left;
p_right=rbt_node[parent].right;
if(!rbt_node[parent].isred) {
break;
}
pp_parent=rbt_node[p_parent].parent;
pp_left=rbt_node[p_parent].left;
pp_right=rbt_node[p_parent].right;
if(rbt_node[pp_left].isred && rbt_node[pp_right].isred) {
rbt_node[pp_left].isred=0;
rbt_node[pp_right].isred=0;
rbt_node[p_parent].isred=1;
pos=p_parent;
} else {
if(pos==p_right && parent==pp_left) {
if(rbt_node[pos].left>0) {
rbt_node[rbt_node[pos].left].parent=parent;
}
rbt_node[parent].right=rbt_node[pos].left;
rbt_node[parent].parent=pos;
rbt_node[pos].left=parent;
rbt_node[pos].parent=p_parent;
rbt_node[p_parent].left=pos;
pos=parent;
} else if(pos==p_left && parent==pp_right) {
if(rbt_node[pos].right>0) {
rbt_node[rbt_node[pos].right].parent=parent;
}
rbt_node[parent].left=rbt_node[pos].right;
rbt_node[parent].parent=pos;
rbt_node[pos].right=parent;
rbt_node[pos].parent=p_parent;
rbt_node[p_parent].right=pos;
pos=parent;
} else if(pos==p_left && parent==pp_left) {
if(rbt_node[pp_parent].left==p_parent) {
rbt_node[pp_parent].left=parent;
} else if(rbt_node[pp_parent].right==p_parent) {
rbt_node[pp_parent].right=parent;
} else {
/* error! bug! */
return 0;
}
if(rbt_node[parent].right>0) {
rbt_node[rbt_node[parent].right].parent=p_parent;
}
rbt_node[p_parent].left=rbt_node[parent].right;
rbt_node[p_parent].parent=parent;
rbt_node[parent].right=p_parent;
rbt_node[parent].parent=pp_parent;
rbt_node[p_parent].isred=1;
rbt_node[parent].isred=0;
break;
} else if(pos==p_right && parent==pp_right) {
if(rbt_node[pp_parent].left==p_parent) {
rbt_node[pp_parent].left=parent;
} else if(rbt_node[pp_parent].right==p_parent) {
rbt_node[pp_parent].right=parent;
} else {
/* error! bug! */
return 0;
}
if(rbt_node[parent].left>0) {
rbt_node[rbt_node[parent].left].parent=p_parent;
}
rbt_node[p_parent].right=rbt_node[parent].left;
rbt_node[p_parent].parent=parent;
rbt_node[parent].left=p_parent;
rbt_node[parent].parent=pp_parent;
rbt_node[p_parent].isred=1;
rbt_node[parent].isred=0;
break;
} else {
/* error! bug! */
return 0;
}
}
}
rbt_node[0].parent=0;
rbt_node[0].left=0;
rbt_node[0].isred=0;
return 1;
}
/*赤黒木メインコードここまで*/
/*デバッグ用関数*/
void rbt_print(int youso,int kaisou) {
int i;
if(youso<=0) {
if(kaisou<0)rbt_print(rbt_node[0].right,0);
else puts("(空)");
return;
} else if(youso<=TREE_MAX) {
printf("%d->%d %s (%d <- %d -> %d %d)\n",
rbt_node[youso].key,rbt_node[youso].data,
rbt_node[youso].isred?"赤":"黒",rbt_node[youso].parent,
youso,rbt_node[youso].left,rbt_node[youso].right);
for(i=0;i<=kaisou;i++)printf(" ");
printf("左: ");rbt_print(rbt_node[youso].left,kaisou+1);
for(i=0;i<=kaisou;i++)printf(" ");
printf("右: ");rbt_print(rbt_node[youso].right,kaisou+1);
}
}
/*テストコード*/
#if DO_REALTIME_DISPLAY
#define CHOICE_TEXT "1:挿入 2:検索 3:リセット 4:終了"
#define RESET_CODE 3
#define EXIT_CODE 4
#else
#define CHOICE_TEXT "1:挿入 2:検索 3:構造の表示 4:リセット 5:終了"
#define RESET_CODE 4
#define EXIT_CODE 5
#endif
int main(void) {
int sousa=0;
int key,data;
rbt_init();
while(sousa!=EXIT_CODE) {
puts("操作を選んでください");
puts(CHOICE_TEXT);
putchar('>');
scanf("%d",&sousa);
switch(sousa) {
case 1:
printf(" キー>");
scanf("%d",&key);
printf("データ>");
scanf("%d",&data);
if(rbt_insert(key,data)) {
puts("挿入しました。");
} else {
puts("エラーが発生しました。");
}
#if DO_REALTIME_DISPLAY
rbt_print(0,-1);
#endif
break;
case 2:
printf("キー>");
scanf("%d",&key);
data=rbt_search(key);
if(data==-1) {
puts("見つからないかデータが-1です。");
} else {
printf("データは%dです。\n",data);
}
break;
#if !DO_REALTIME_DISPLAY
case 3:
puts("現在の構造");
rbt_print(0,-1);
break;
#endif
case RESET_CODE:
rbt_init();
puts("リセットしました。");
break;
case EXIT_CODE:
break;
default:
puts("ふざけるな!");
break;
}
}
return 0;
}
このままの形での転載はおやめください。
これを利用したコードの掲示は構いません。
この場合、私のコードを使用したことを紹介してくれると嬉しいです。(それが適切な場所の場合)
※2012/4/28 バグを修正しました