赤黒木の検証

[みけCAT]

gcc4.7.0をDev-C++4.9.9.2で使っています。
主に以下の2サイトを参考に、赤黒木を実装しています。
http://www.geocities.jp/h2fujimura/mutt ... -tree.html
http://www.ece.uc.edu/~franco/C321/html ... black.html
一応うまくいっていそうなのですが、
１．このコードは本当に正しいでしょうか？
２．どうやって検証するのがいいでしょうか？
よろしくお願いします。

► スポイラーを表示

rbt.h

コード:

#include <cstdio>

#ifndef RBT_H_GUARD
#define RBT_H_GUARD

struct RedBlackTreeNode {
	int key;
	bool isRed;
	RedBlackTreeNode* left;
	RedBlackTreeNode* right;

	RedBlackTreeNode() {
		key=0;isRed=true;left=right=NULL;
	}
	RedBlackTreeNode(int initKey) {
		key=initKey;isRed=true;left=right=NULL;
	}
	~RedBlackTreeNode() {
		if(left)delete left;
		if(right)delete right;
	}
};

class RedBlackTree {
	private:
		RedBlackTreeNode* root;
		bool enableBalance;

		void rotate(RedBlackTreeNode** target,bool isLeft);
		int insertInternal(RedBlackTreeNode** now,int key);
		bool searchInternal(const RedBlackTreeNode* now,int key) const;
		RedBlackTreeNode* searchPtr(RedBlackTreeNode* now,int key);
		RedBlackTreeNode* searchMinNode(RedBlackTreeNode* now);
		int removeInternal(RedBlackTreeNode** now,RedBlackTreeNode* target);
		int calcuateDepthInternal(const RedBlackTreeNode* now) const;
		int countElementsInternal(const RedBlackTreeNode* now) const;
	public:
		RedBlackTree() {
			root=NULL;
			enableBalance=true;
		}
		~RedBlackTree() {
			if(root)delete root;
		}

		void clear();
		void insert(int key);
		bool search(int key) const;
		bool remove(int key);
		int calcuateDepth() const;
		int countElements() const;
		const RedBlackTreeNode* getRoot() const {
			return root;
		}
		void setEnableBalance(bool eb) {
			enableBalance=eb;
		}
		bool getEnableBalance() const {
			return enableBalance;
		}
};

#endif

rbt.cpp

コード:

#include "rbt.h"

/*
全体の解説 
http://www.geocities.jp/h2fujimura/mutter/tree/red-black-tree.html
デモと細かいこと 
http://www.ece.uc.edu/~franco/C321/html/RedBlack/redblack.html
*/

const int RBT_REQUEST_NONE			= 0;
const int RBT_REQUEST_INIT			= 1;
const int RBT_REQUEST_NEXTOFLEFT	= 2;
const int RBT_REQUEST_NEXTOFRIGHT	= 3;
const int RBT_REQUEST_ROTATE_LEFT	= 0x100;
const int RBT_REQUEST_ROTATE_RIGHT	= 0x200;

const int RBT_REQUEST_DEL_INIT		= 1;

void RedBlackTree::clear() {
	if(root)delete root;
	root=NULL;
}

void RedBlackTree::rotate(RedBlackTreeNode** target,bool isLeft) {
	if(isLeft && (*target)->right!=NULL) {
		RedBlackTreeNode* top=*target;
		RedBlackTreeNode* topRight=(*target)->right;
		RedBlackTreeNode* topRightLeft=(*target)->right->left;
		(*target)->right->left=top;
		(*target)->right=topRightLeft;
		*target=topRight;
	} else if((*target)->left!=NULL) {
		RedBlackTreeNode* top=*target;
		RedBlackTreeNode* topLeft=(*target)->left;
		RedBlackTreeNode* topLeftRight=(*target)->left->right;
		(*target)->left->right=top;
		(*target)->left=topLeftRight;
		*target=topLeft;
	}
}

int RedBlackTree::insertInternal(RedBlackTreeNode** now,int key) {
	int ret=RBT_REQUEST_NONE;
	bool isLeft;
	if(*now==NULL) {
		*now=new RedBlackTreeNode(key);
		if(enableBalance) {
			return RBT_REQUEST_INIT;
		} else {
			(*now)->isRed=false;
			return RBT_REQUEST_NONE;
		}
	} else if((*now)->key==key) {
		return RBT_REQUEST_NONE;
	} else if((*now)->key<key) {
		ret=insertInternal(&((*now)->right),key);
		isLeft=false;
	} else { // key<(*now)->key
		ret=insertInternal(&((*now)->left),key);
		isLeft=true;
	}

	if(ret==RBT_REQUEST_INIT) {
		//ケース1 
		if((*now)->isRed) {
			ret=isLeft?RBT_REQUEST_NEXTOFLEFT:RBT_REQUEST_NEXTOFRIGHT;
		} else {
			ret=RBT_REQUEST_NONE;
		}
	} else if(ret==RBT_REQUEST_NEXTOFLEFT) {
		if(isLeft) {
			if((*now)->right==NULL || !(*now)->right->isRed) {
				//ケース4
				(*now)->isRed=true;
				(*now)->left->isRed=false;
				rotate(now,false);
				ret=RBT_REQUEST_NONE;
			} else {
				//ケース2
				(*now)->left->isRed=false;
				if((*now)->right)(*now)->right->isRed=false;
				(*now)->isRed=true;
				ret=RBT_REQUEST_INIT;
			}
		} else {
			if((*now)->left==NULL || !(*now)->left->isRed) {
				//ケース3
				rotate(&((*now)->right),false);
				//ケース4
				(*now)->isRed=true;
				(*now)->right->isRed=false;
				rotate(now,true);
				ret=RBT_REQUEST_NONE;
			} else {
				//ケース2
				(*now)->right->isRed=false;
				if((*now)->left)(*now)->left->isRed=false;
				(*now)->isRed=true;
				ret=RBT_REQUEST_INIT;
			}
		}
	} else if(ret==RBT_REQUEST_NEXTOFRIGHT) {
		if(isLeft) {
			if((*now)->right==NULL || !(*now)->right->isRed) {
				//ケース3
				rotate(&((*now)->left),true);
				//ケース4
				(*now)->isRed=true;
				(*now)->left->isRed=false;
				rotate(now,false);
				ret=RBT_REQUEST_NONE;
			} else {
				//ケース2
				(*now)->left->isRed=false;
				if((*now)->right)(*now)->right->isRed=false;
				(*now)->isRed=true;
				ret=RBT_REQUEST_INIT;
			}
		} else {
			if((*now)->left==NULL || !(*now)->left->isRed) {
				//ケース4
				(*now)->isRed=true;
				(*now)->right->isRed=false;
				rotate(now,true);
				ret=RBT_REQUEST_NONE;
			} else {
				//ケース2
				(*now)->right->isRed=false;
				if((*now)->left)(*now)->left->isRed=false;
				(*now)->isRed=true;
				ret=RBT_REQUEST_INIT;
			}
		}
	}
	return ret;
}

void RedBlackTree::insert(int key) {
	insertInternal(&root,key);
	root->isRed=false;
}

bool RedBlackTree::searchInternal(const RedBlackTreeNode* now,int key) const {
	if(now==NULL)return false;
	if(now->key==key)return true;
	return now->key<key?
		searchInternal(now->right,key):
		searchInternal(now->left,key);
}

bool RedBlackTree::search(int key) const {
	return searchInternal(root,key);
}

RedBlackTreeNode* RedBlackTree::searchPtr(RedBlackTreeNode* now,int key) {
	if(now==NULL)return NULL;
	if(now->key==key)return now;
	return searchPtr(now->key<key?now->right:now->left,key);
}

RedBlackTreeNode* RedBlackTree::searchMinNode(RedBlackTreeNode* now) {
	if(now->left==NULL)return now;
	return searchMinNode(now->left);
}

int RedBlackTree::removeInternal(RedBlackTreeNode** now,RedBlackTreeNode* target) {
	int ret=RBT_REQUEST_NONE;
	bool isLeft=false;
	if(*now==NULL)return RBT_REQUEST_NONE;
	if(*now==target) {
		RedBlackTreeNode* delNode=*now;
		bool delNodeIsRed=delNode->isRed;
		*now=(*now)->left?(*now)->left:(*now)->right;
		delNode->left=delNode->right=NULL;
		delete delNode;
		//ケース0 
		if(delNodeIsRed) {
			return RBT_REQUEST_NONE;
		} else if(*now && (*now)->isRed) {
			(*now)->isRed=false;
			return RBT_REQUEST_NONE;
		}
		return enableBalance?RBT_REQUEST_DEL_INIT:RBT_REQUEST_NONE;
	} else if((*now)->key<=target->key) {
		ret=removeInternal(&((*now)->right),target);
		isLeft=false;
	} else {
		ret=removeInternal(&((*now)->left),target);
		isLeft=true;
	}
	if(ret==RBT_REQUEST_DEL_INIT) {
		if(isLeft) {
			if((*now)->right!=NULL && (*now)->right->isRed) {
				//ケース2 
				(*now)->isRed=!(*now)->isRed;
				(*now)->right->isRed=!(*now)->right->isRed;
				rotate(now,true);
				now=&((*now)->left);
			}
			ret=RBT_REQUEST_NONE;
			if((*now)->right!=NULL) {
				if(((*now)->right->left==NULL ||
						!((*now)->right->left->isRed)) &&
						((*now)->right->right==NULL ||
						!((*now)->right->right->isRed))) {
					if((*now)->isRed) {
						//ケース4 
						(*now)->isRed=false;
						(*now)->right->isRed=true;
					} else {
						//ケース3 
						(*now)->right->isRed=true;
						ret=RBT_REQUEST_INIT;
					}
				} else if((*now)->right->right!=NULL &&
						(*now)->right->right->isRed) {
					//ケース6
					bool colorTemp=(*now)->isRed;
					(*now)->isRed=(*now)->right->isRed;
					(*now)->right->isRed=colorTemp;
					(*now)->right->right->isRed=false;
					rotate(now,true); 
				} else {
					//ケース5
					(*now)->right->isRed=true; 
					(*now)->right->left->isRed=false;
					rotate(&((*now)->right),false);
					//ケース6 
					bool colorTemp=(*now)->isRed;
					(*now)->isRed=(*now)->right->isRed;
					(*now)->right->isRed=colorTemp;
					(*now)->right->right->isRed=false;
					rotate(now,true); 
				}
			}
		} else {
			if((*now)->left!=NULL && (*now)->left->isRed) {
				//ケース2 
				(*now)->isRed=!(*now)->isRed;
				(*now)->left->isRed=!(*now)->left->isRed;
				rotate(now,false);
				now=&((*now)->right);
			}
			ret=RBT_REQUEST_NONE;
			if((*now)->left!=NULL) {
				if(((*now)->left->left==NULL ||
						!((*now)->left->left->isRed)) &&
						((*now)->left->right==NULL ||
						!((*now)->left->right->isRed))) {
					if((*now)->isRed) {
						//ケース4 
						(*now)->isRed=false;
						(*now)->left->isRed=true;
					} else {
						//ケース3 
						(*now)->left->isRed=true;
						ret=RBT_REQUEST_INIT;
					}
				} else if((*now)->left->left!=NULL &&
						(*now)->left->left->isRed) {
					//ケース6
					bool colorTemp=(*now)->isRed;
					(*now)->isRed=(*now)->left->isRed;
					(*now)->left->isRed=colorTemp;
					(*now)->left->left->isRed=false;
					rotate(now,false);
				} else {
					//ケース5
					(*now)->left->isRed=true; 
					(*now)->left->right->isRed=false;
					rotate(&((*now)->left),true);
					//ケース6 
					bool colorTemp=(*now)->isRed;
					(*now)->isRed=(*now)->left->isRed;
					(*now)->left->isRed=colorTemp;
					(*now)->left->left->isRed=false;
					rotate(now,false); 
				}
			}
		}
	}
	return ret;
}

bool RedBlackTree::remove(int key) {
	RedBlackTreeNode* target;
	target=searchPtr(root,key);
	if(target==NULL)return false;
	if(target->left!=NULL && target->right!=NULL) {
		RedBlackTreeNode* minNode;
		minNode=searchMinNode(target->right);
		target->key=minNode->key;
		target=minNode;
	}
	removeInternal(&root,target);
	return true;
}

int RedBlackTree::calcuateDepthInternal(const RedBlackTreeNode* now) const {
	int depth1,depth2;
	if(now==NULL)return 0;
	depth1=calcuateDepthInternal(now->left);
	depth2=calcuateDepthInternal(now->right);
	return ((depth1>depth2)?depth1:depth2)+1;
}

int RedBlackTree::calcuateDepth() const {
	return calcuateDepthInternal(root);
}

int RedBlackTree::countElementsInternal(const RedBlackTreeNode* now) const {
	if(now==NULL)return 0;
	return countElementsInternal(now->left)+countElementsInternal(now->right)+1;
}

int RedBlackTree::countElements() const {
	return countElementsInternal(root);
}

[みけCAT]

身勝手ですいません。
AVL木についても同様の質問をさせてください。

► スポイラーを表示

avlt.h

コード:

#include <cstdio>

#ifndef AVLT_H_GUARD
#define AVLT_H_GUARD

const int AVLTREE_FLAG_L = 0;
const int AVLTREE_FLAG_E = 1;
const int AVLTREE_FLAG_R = 2;

struct AVLTreeNode {
	int key;
	int flag;
	AVLTreeNode* left;
	AVLTreeNode* right;

	AVLTreeNode() {
		key=0;flag=AVLTREE_FLAG_E;left=right=NULL;
	}
	AVLTreeNode(int initKey) {
		key=initKey;flag=AVLTREE_FLAG_E;left=right=NULL;
	}
	~AVLTreeNode() {
		if(left)delete left;
		if(right)delete right;
	}
};

class AVLTree {
	private:
		AVLTreeNode* root;
		bool enableBalance;

		void rotate(AVLTreeNode** target,bool isLeft);
		bool insertInternal(AVLTreeNode** now,int key);
		bool searchInternal(const AVLTreeNode* now,int key) const;
		AVLTreeNode* searchPtr(AVLTreeNode* now,int key);
		AVLTreeNode* searchMaxNode(AVLTreeNode* now);
		bool removeInternal(AVLTreeNode** now,AVLTreeNode* target);
		int calcuateDepthInternal(const AVLTreeNode* now) const;
		int countElementsInternal(const AVLTreeNode* now) const;
	public:
		AVLTree() {
			root=NULL;
			enableBalance=true;
		}
		~AVLTree() {
			if(root)delete root;
		}

		void clear();
		void insert(int key);
		bool search(int key) const;
		bool remove(int key);
		int calcuateDepth() const;
		int countElements() const;
		const AVLTreeNode* getRoot() const {
			return root;
		}
		void setEnableBalance(bool eb) {
			enableBalance=eb;
		}
		bool getEnableBalance() const {
			return enableBalance;
		}
};

#endif

avlt.cpp

コード:

#include "avlt.h"

/*
参考
http://www.jaist.ac.jp/~okamotoy/lect/2005/DSA/avl.pdf
*/ 

void AVLTree::clear() {
	if(root)delete root;
	root=NULL;
}

void AVLTree::rotate(AVLTreeNode** target,bool isLeft) {
	if(isLeft && (*target)->right!=NULL) {
		AVLTreeNode* top=*target;
		AVLTreeNode* topRight=(*target)->right;
		AVLTreeNode* topRightLeft=(*target)->right->left;
		(*target)->right->left=top;
		(*target)->right=topRightLeft;
		*target=topRight;
	} else if((*target)->left!=NULL) {
		AVLTreeNode* top=*target;
		AVLTreeNode* topLeft=(*target)->left;
		AVLTreeNode* topLeftRight=(*target)->left->right;
		(*target)->left->right=top;
		(*target)->left=topLeftRight;
		*target=topLeft;
	}
}

bool AVLTree::insertInternal(AVLTreeNode** now,int key) {
	bool isLeft;
	bool ret=false;
	if(*now==NULL) {
		*now=new AVLTreeNode(key);
		return enableBalance;
	} else if((*now)->key==key) {
		return false;
	} else if((*now)->key<key) {
		ret=insertInternal(&((*now)->right),key);
		isLeft=false;
	} else { // key<(*now)->key
		ret=insertInternal(&((*now)->left),key);
		isLeft=true;
	}
	if(!ret)return false;
	ret=false;

	if(isLeft) { //左から来た
		if((*now)->flag==AVLTREE_FLAG_R) {
			(*now)->flag=AVLTREE_FLAG_E;
		} else if((*now)->flag==AVLTREE_FLAG_E) {
			(*now)->flag=AVLTREE_FLAG_L;
			ret=true;
		} else {
			if((*now)->left->flag==AVLTREE_FLAG_L) {
				(*now)->left->flag=AVLTREE_FLAG_E;
				(*now)->flag=AVLTREE_FLAG_E;
				rotate(now,false);
			} else if((*now)->left->flag==AVLTREE_FLAG_R) {
				if((*now)->left->right) {
					if((*now)->left->right->flag==AVLTREE_FLAG_L) {
						(*now)->flag=AVLTREE_FLAG_R;
						(*now)->left->flag=AVLTREE_FLAG_E;
					} else if((*now)->left->right->flag==AVLTREE_FLAG_R) {
						(*now)->flag=AVLTREE_FLAG_E;
						(*now)->left->flag=AVLTREE_FLAG_L;
					} else if((*now)->left->right->flag==AVLTREE_FLAG_E) {
						(*now)->flag=AVLTREE_FLAG_E;
						(*now)->left->flag=AVLTREE_FLAG_E;
					}
					(*now)->left->right->flag=AVLTREE_FLAG_E;
					rotate(&((*now)->left),true);
					rotate(now,false);
				}
			}
		}
	} else { //右から来た
		if((*now)->flag==AVLTREE_FLAG_L) {
			(*now)->flag=AVLTREE_FLAG_E;
		} else if((*now)->flag==AVLTREE_FLAG_E) {
			(*now)->flag=AVLTREE_FLAG_R;
			ret=true;
		} else {
			if((*now)->right->flag==AVLTREE_FLAG_R) {
				(*now)->right->flag=AVLTREE_FLAG_E;
				(*now)->flag=AVLTREE_FLAG_E;
				rotate(now,true);
			} else if((*now)->right->flag==AVLTREE_FLAG_L) {
				if((*now)->right->left) {
					if((*now)->right->left->flag==AVLTREE_FLAG_R) {
						(*now)->flag=AVLTREE_FLAG_L;
						(*now)->right->flag=AVLTREE_FLAG_E;
					} else if((*now)->right->left->flag==AVLTREE_FLAG_L) {
						(*now)->flag=AVLTREE_FLAG_E;
						(*now)->right->flag=AVLTREE_FLAG_R;
					} else if((*now)->right->left->flag==AVLTREE_FLAG_E) {
						(*now)->flag=AVLTREE_FLAG_E;
						(*now)->right->flag=AVLTREE_FLAG_E;
					}
					(*now)->right->left->flag=AVLTREE_FLAG_E;
					rotate(&((*now)->right),false);
					rotate(now,true);
				}
			}
		}
	}

	return ret;
}

void AVLTree::insert(int key) {
	insertInternal(&root,key);
}

bool AVLTree::searchInternal(const AVLTreeNode* now,int key) const {
	if(now==NULL)return false;
	if(now->key==key)return true;
	return now->key<key?
		searchInternal(now->right,key):
		searchInternal(now->left,key);
}

bool AVLTree::search(int key) const {
	return searchInternal(root,key);
}

AVLTreeNode* AVLTree::searchPtr(AVLTreeNode* now,int key) {
	if(now==NULL)return NULL;
	if(now->key==key)return now;
	return searchPtr(now->key<key?now->right:now->left,key);
}

AVLTreeNode* AVLTree::searchMaxNode(AVLTreeNode* now) {
	if(now->right==NULL)return now;
	return searchMaxNode(now->right);
}

bool AVLTree::removeInternal(AVLTreeNode** now,AVLTreeNode* target) {
	bool isLeft=false;
	bool ret=false;
	if(*now==NULL)return false;
	if(*now==target) {
		AVLTreeNode* delNode=*now;
		*now=(*now)->left?(*now)->left:(*now)->right;
		delNode->left=delNode->right=NULL;
		delete delNode;
		return enableBalance;
	} else if((*now)->key<target->key) {
		ret=removeInternal(&((*now)->right),target);
		isLeft=false;
	} else {
		ret=removeInternal(&((*now)->left),target);
		isLeft=true;
	}
	if(!ret)return false;
	ret=false;

	if(isLeft) { //左から来た
		if((*now)->flag==AVLTREE_FLAG_L) {
			(*now)->flag=AVLTREE_FLAG_E;
			ret=true;
		} else if((*now)->flag==AVLTREE_FLAG_E) {
			(*now)->flag=AVLTREE_FLAG_R;
		} else {
			if((*now)->right->flag==AVLTREE_FLAG_E) {
				(*now)->right->flag=AVLTREE_FLAG_L;
				rotate(now,true);
			} else if((*now)->right->flag==AVLTREE_FLAG_R) {
				(*now)->flag=AVLTREE_FLAG_E;
				(*now)->right->flag=AVLTREE_FLAG_E;
				rotate(now,true);
				ret=true;
			} else {
				if((*now)->right->left) {
					if((*now)->right->left->flag==AVLTREE_FLAG_L) {
						(*now)->flag=AVLTREE_FLAG_E;
						(*now)->right->flag=AVLTREE_FLAG_R;
					} else if((*now)->right->left->flag==AVLTREE_FLAG_E) {
						(*now)->flag=AVLTREE_FLAG_E;
						(*now)->right->flag=AVLTREE_FLAG_E;
					} else if((*now)->right->left->flag==AVLTREE_FLAG_R) {
						(*now)->flag=AVLTREE_FLAG_L;
						(*now)->right->flag=AVLTREE_FLAG_E;
					}
					(*now)->right->left->flag=AVLTREE_FLAG_E;
					rotate(&((*now)->right),false);
					rotate(now,true);
				}
				ret=true;
			}
		}
	} else { //右から来た
		if((*now)->flag==AVLTREE_FLAG_R) {
			(*now)->flag=AVLTREE_FLAG_E;
			ret=true;
		} else if((*now)->flag==AVLTREE_FLAG_E) {
			(*now)->flag=AVLTREE_FLAG_L;
		} else {
			if((*now)->left->flag==AVLTREE_FLAG_E) {
				(*now)->left->flag=AVLTREE_FLAG_R;
				rotate(now,false);
			} else if((*now)->left->flag==AVLTREE_FLAG_L) {
				(*now)->flag=AVLTREE_FLAG_E;
				(*now)->left->flag=AVLTREE_FLAG_E;
				rotate(now,false);
				ret=true;
			} else {
				if((*now)->left->right) {
					if((*now)->left->right->flag==AVLTREE_FLAG_L) {
						(*now)->flag=AVLTREE_FLAG_R;
						(*now)->left->flag=AVLTREE_FLAG_E;
					} else if((*now)->left->right->flag==AVLTREE_FLAG_E) {
						(*now)->flag=AVLTREE_FLAG_E;
						(*now)->left->flag=AVLTREE_FLAG_E;
					} else if((*now)->left->right->flag==AVLTREE_FLAG_R) {
						(*now)->flag=AVLTREE_FLAG_E;
						(*now)->left->flag=AVLTREE_FLAG_L;
					}
					(*now)->left->right->flag=AVLTREE_FLAG_E;
					rotate(&((*now)->left),true);
					rotate(now,false);
				}
				ret=true;
			}
		}
	} 

	return ret;
}

bool AVLTree::remove(int key) {
	AVLTreeNode* target;
	target=searchPtr(root,key);
	if(target==NULL)return false;
	if(target->left!=NULL && target->right!=NULL) {
		AVLTreeNode* maxNode;
		maxNode=searchMaxNode(target->left);
		target->key=maxNode->key;
		target=maxNode;
	}
	removeInternal(&root,target);
	return true;
}

int AVLTree::calcuateDepthInternal(const AVLTreeNode* now) const {
	int depth1,depth2;
	if(now==NULL)return 0;
	depth1=calcuateDepthInternal(now->left);
	depth2=calcuateDepthInternal(now->right);
	return ((depth1>depth2)?depth1:depth2)+1;
}

int AVLTree::calcuateDepth() const {
	return calcuateDepthInternal(root);
}

int AVLTree::countElementsInternal(const AVLTreeNode* now) const {
	if(now==NULL)return 0;
	return countElementsInternal(now->left)+countElementsInternal(now->right)+1;
}

int AVLTree::countElements() const {
	return countElementsInternal(root);
}

[たいちう]

どこまで真面目に検証するかにもよりますが、
手始めにツリー構造を表示できるようにしてはどうでしょうか。
DxLibでもWinAPIでも構わないので、正しいかどうかを一目で判断できるようにします。
私ならばきっとCUIで作ります。
適当な乱数列で赤黒木が構成されていく様子をステップ毎に確認できれば十分かと。

もっと真面目にやるならば、CppUnitなどの単体テストを作り、
カバレッジ100%を目指しましょう。
私が作るとしたら最初からテスト駆動式に開発します。
CUIでの表示は、表示メソッドのテストが作りやすいというメリットもあります。


繰り返しになりますし、実装済みかもしれませんが、
視覚化が開発・検証の最優先事項です。

[みけCAT]

回答ありがとうございます。

どこまで真面目に検証するかにもよりますが、
手始めにツリー構造を表示できるようにしてはどうでしょうか。
DxLibでもWinAPIでも構わないので、正しいかどうかを一目で判断できるようにします。
私ならばきっとCUIで作ります。
適当な乱数列で赤黒木が構成されていく様子をステップ毎に確認できれば十分かと。

ごめんなさい。表示ソフトは既に作ってあります。
添付しました。
UIは共通で、F1で操作説明を表示します。あとはそれを見てください。
0～999の整数をキーとして挿入できます。

もっと真面目にやるならば、CppUnitなどの単体テストを作り、
カバレッジ100%を目指しましょう。
私が作るとしたら最初からテスト駆動式に開発します。
CUIでの表示は、表示メソッドのテストが作りやすいというメリットもあります。

もう少し詳しくお願いします。

[たいちう]

> もう少し詳しくお願いします。

キーワードでググったりした後という前提で少し回答します。

カバレッジはC0です。
フリーで見つけることができたツールが、C0まででしたので。
最近探してないですので、今はもっと良いツールが見つかるかも。

設計の悪いプログラムにxUnit用のテストを書こうとしても、
不可能に近い場合が多く、テストを書くためには先にリファクタリングが必要、
安全にリファクタリングをするためには先にテストが必要、というジレンマに陥ります。
これには何度も苦労させられているので、趣味である程度以上の規模のプログラムを作る時は、
殆ど必ずテスト駆動で作ります。カバレッジを測ることは少ないですが。


判らない点があれば、もう少しピンポイントで尋ねてくれた方が答えやすいです。

[みけCAT]

CppUnitを使用しようとしたのですが、よくわかりませんでした。
まずhttp://www.ogis-ri.co.jp/otc/hiroba/technical/CppUnit/
を参考にしようとしましたが、古そうなので、
http://sourceforge.net/apps/mediawiki/c ... =Main_Page
からCppUnit 1.12.1をダウンロードし、MSYSで./configureしてからmakeしました。
exsamples/simpleを参考に、
Dev-C++のプロジェクトの形でコンパイルできたら便利なので試してみたのですが、

コード:

4 F:\C\cppUnitTest\TestTest.cpp invalid declarator before 'autoRegisterRegistry__4' 

というエラーが出てしまいました。
何か足りないのでしょうか？それともプロジェクトを使用することはできないのでしょうか？
よろしくお願いします。
使用したプロジェクトを添付します。

[たいちう]

ogis-riのCppUnitは同名の別のソフトです。
同じ目的のプログラムですが、マクロの定義が違っていたり、
使い方は結構違っていたと思います。

私が使っているのはsourceforgeのcppunit-1.12.1です。
ただ、これも相当古いみたいで、VC++6.0用のプロジェクトだったと思います。
もっと使いやすい物が出ていないんでしょうかね？

MSYSの事は判りませんが、freeのVisual Studio 2008 Express Editionからの
使い方ならば、ある程度は説明できます。多分2010でも大差ないでしょう。

example.dswは古いファイルですので、2008から開こうとすると、
プロジェクトの変換が行われると思います。
その後、ソリューションをビルドしようとしても、全てはビルドできません。
GUIの部分はMFCを使っているため、freeのExpress Editionではビルドできないのです。

それでもCUIの部分は十分使えますので、
simple.exeを参考にテストを書くことができます。

別のアプローチとして、『テスト駆動開発入門』
という本に、xUnitの作り方、というのが載っています。
本に書かれているのはpythonの例ですが、それを参考にC++で作ることも可能です。
何年か前に作ったことがあるので、このアプローチで行き詰ったら聞いてください。


# 前世紀の話ですが、プロになりかけの頃リファクタリングとxUnitの存在を知り、
# これは素晴らしいものだ、と思いながらも設定が難しく使えなかったのも良い思い出です。
# 今ならば当時ほどは難しくないし、素晴らしいという評価も変わりません。
# つまり、お勧めなので、この機会に是非一度使ってみて下さい。

[みけCAT]

ogis-riのCppUnitは同名の別のソフトです。
同じ目的のプログラムですが、マクロの定義が違っていたり、
使い方は結構違っていたと思います。

私が使っているのはsourceforgeのcppunit-1.12.1です。

CppUnit 1.12.1をダウンロードしたって言いましたよね？

MSYSの事は判りませんが、freeのVisual Studio 2008 Express Editionからの
使い方ならば、ある程度は説明できます。多分2010でも大差ないでしょう。

できればMSYSではなくDev-C++でお願いします。
バージョンアップして5.2.0.3になりました。

[みけCAT]

エラーの原因は、TestTest.hのクラス定義の最後にセミコロンを忘れたことでした。
お騒がせしました。

[たいちう]

> CppUnit 1.12.1をダウンロードしたって言いましたよね？

誤解させてしまったようですが、みけCATさんがDLした
バージョンは昨夜も把握していましたよ。
それが数年前に私のDLしたものと同じだと書いたのです。


> できればMSYSではなくDev-C++でお願いします。
> バージョンアップして5.2.0.3になりました。

これについては私はお手伝いできません。
幸い解決したみたいですが。

[みけCAT]

すいません。
しばらく放置してしまったので解決にし、
気がむいたらまた考えることにします。