赤黒木

みんなが作った便利な関数やサンプルを共有するコミュニティです。
[url]http://www.activebasic.com/forum/viewforum.php?f=2]ActiveBasicの「実践コードモジュール」[/url]的な感じでやりましょう。
フォーラム(掲示板)ルール
・投稿するコードはできるだけ一つ、もしくは一つの関数を補助する複数の関数の形式にするか、
それだけをコンパイルして動くソースコード一式の形にしてください。
記事には説明だけを書き、コードは添付ファイルにしてもかまいません。
・使い方などの説明も書いてください。
環境に依存するコードの場合は、対象の環境も書いてください。
・使用条件(ライセンスなど)も書いていただけるとありがたいです。
・C言語、もしくはC++推奨ですが、他の言語でもかまいません。
・コードは正しくcodeタグで囲みましょう。
・一つのスレッドで一つのサンプルが基本です。
関連するサンプルの場合はまとめてもかまいません。
・投稿したサンプルを修正する場合には、スレッドの返信の形で投稿してください。
(新しいスレッドにしないでください。記事の編集でもかまいません)
返信
アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

赤黒木

#1

投稿記事 by みけCAT » 12年前

実装がめんどくさいと言われている[要出典]赤黒木のサンプルです。
プログラミングコンテストや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 バグを修正しました
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

返信

“サンプルを共有するコミュニティ” へ戻る