C++ バイナリツリー 書いて覚えるための初心者自己中記事

前回やったデータ構造　ツリーの性能制限版

バイナリツリー

子ノードを最大で２つに制限したツリー

これを利用したデータ構造で代表的なのが

バイナリサーチツリー（二分探索木）

子ノードを追加して値を入れるときにそのノードより小さい場合は左へ、大きい場合は右へを繰り返していくとすべて左から小さい順になる。

このツリーから特定の値を探すときは同じ方法で今いるノードと比較しながら進んでいく。

この数値と対になった文字列をノードに持たせる。

ということはノードの持ち物は

キーとなる値

対になる文字列

子ノード２つ

ということか。

さて、まだドバっとコード来たからひとつづつ理解していこう。

template <typename KEY, typename VALUE>
class Assoc {
public:
	struct Node {
		KEY key;//検索に使用するキー
		VALUE value;//ノードに関連付けられた値
		Node* left;
		Node* right;
		Node(const KEY& key) :key(key), value(), left(NULL), right(NULL) {}
	};

private:
	Node* m_root; //ルートノード
 
};

まず、template ではKEY と VALUEそれぞれ型を用意する。

構造体Nodeのメンバはさっき予想した通りでちょっとほっとした。

Nodeのコンストラクタではvalue以外を初期化している。

というかvalueは書かないのとなにか違いがあるのだろうか？

テンプレートクラスAssocのメンバ変数m_root はルートノード役。

次、

Assoc() :m_root(NULL) {}

テンプレートクラスAssocのコンストラクタではルートノードm_rootをNULLで初期化している。

次、

	//全削除
	void Clear() {
		Clear(m_root);
		m_root = NULL;
	}
 
private:
	void Clear(Node* node) {
		//NULLなら何もしない
		if (node == NULL) { return; }
 
		//子ノードをすべて破壊
		Clear(node->left);
		Clear(node->right);
 
		//ノードを破壊
		delete node;
	}

Clear関係。

引数ありのClearから、引数で貰ったノードがNULLなら何もしない。

ノードが使われていたら、再帰関数でそれぞれleftとrightの子ノードに行かせる。

それぞれ終端でdeleteしてそのノードを削除。

引数なしのClearは引数付きClearにルートノードを渡している。

全部のノードを指定しているのと同じ意味だ。

この場合ルートノードもdeleteされると思うんだけど、

ルートノードm_rootはメンバ変数であって、子ノードと違ってnewで作られたものじゃないわけでしょ？

調べたら

new で割り当てられたのではないオブジェクトへのポインターに対して delete を使用すると、予期しない結果になります。

ダメっぽいけど。

俺が何か勘違いしているのかな。

でも前回やったクラステンプレートTree の時はルートノードだけはdeleteしないようにしてたしな。

何が違うんだろう。ダメな気がする。

つぎ、

virtual ~Assoc() { Clear(); }//ツリーを破壊

デストラクタ。

これはさっきのメンバ関数Clearを使うだけ。

次、

private:
	//指定したキーを持つノードへの参照を取得
	PNode& FindNode(const KEY& key) {
		return const_cast<PNode&>(FindNode_(key));
	}
	const PNode FindNode(const KEY& key)const {
		return FindNode_(key);
	}
	const PNode& FindNode_(const KEY& key)const {
		return FindNode_(m_root, key);
	}
	const PNode& FindNode_(const PNode& node, const KEY& key)const {
		if (node == NULL) { return node; }
 
		if (key < node->key) {
			return FindNode_(node->left, key);
		}
		else if (node->key < key) {
			return FindNode_(node->right, key);
		}
		else {
			return node;
		}
	}

PNodeってのはtypedefした Node* だから

Node* で参照。であってるかな。

クラステンプレートAssocのメンバ関数FindNodeはconst 非const の二つの受付があって、どちらも３番目のm_rootを引数に追加する二次受付的なのに行ってそこからようやく本体に行く。

再帰関数で

渡ってきたノードがNULLなら終了

指定したkeyと比べてnode->key が大きかったら node->left

小さかったら node->right へ再帰呼び出し

NULLでもなく大きくもなく小さくもなかったら == とみなして終了。

Node* 参照で返す。

//指定したキーを持つノードを探し、無ければノードを作成する
//対応する値へのノードを返す
VALUE& operator[](const KEY& key) {
	PNode& node = FindNode(key);
	if (node == NULL) {
		node = new Node(key);
	}
	return node->value;
}

演算子オーバーロードで指定したkeyに対応するvalueの参照を返す。

先ほどのFindNode関数を使用している。

一致するkey が無かったらあるべき場所のNode*参照が、それがNULLかどうかで判断する。NULLならそのkeyで初期化したNodeをnewしてそのあるべき場所に入れる。

nodeがNULLでなければ一致したことになるのでそのままnode->value を返す。newで作ったほうもこれはやる。

参照なのでこの戻り値に代入が出来る。はず。

つぎ、

//指定したキーを持つノードを探し、無ければ例外を投げる
//対応する値への参照を返す
const VALUE& operator[](const KEY& key)const {
	const Node* node = FindNode(key);
	if (node == NULL) {
		throw out_of_range("見つかりませんでした");
	}
	return node->value;
}

ほとんど同じ。見つからなかった場合に例外を投げる。

こっちは戻り値にconstがかかっているし。見る専用なのかな。

クラステンプレートAssocはここまで。

次に使用例。

bool Input(int& n) {
	cout << "値を入力してください > " << flush;
	n = 0;
	cin >> n;
	return n > 0;
}

Inputあります。

typedef Assoc<int, string> AssocIS;

void Check(const AssocIS& assoc, int n) {
	try {
		cout << assoc[n] << endl;
	}
	catch (const out_of_range& e) {
		cerr << e.what() << endl;
	}
}

型を指定したクラステンプレートAssocをtypedefでAssocISと命名。

クラステンプレートのオブジェクト参照と数値(key)を引数にしたCheck関数。

演算子オーバーロードしているからvalueの参照が返ってくる、例外はcatchする。

って、あれ？

無かったらノードを作成するほうの [ ] との使い分け方って、引数の

const AssocIS& assoc　がconstってことで成立するのか？

そうだな。

で最後にmain関数内で

int main() {
 
	AssocIS assoc;
 
	assoc[42] = "Hoge";
	assoc[25] = "Foo";
	assoc[89] = "Bar";
	assoc[11] = "Baz";
 
	int n;
	while (Input(n)) {
		Check(assoc, n);
	}
 
	system("pause");
}
//output
値を入力してください > 42
Hoge
値を入力してください > 25
Foo
値を入力してください > 89
Bar
値を入力してください > 11
Baz
値を入力してください > 4
見つかりませんでした
値を入力してください >

こうなると。

 keyがまるで配列のインデックスのようになっている。だたし飛び飛び。

連想配列ということがある。

さらにkeyがint 型だったが

Assoc<string , string> も可能。

keyがint型の場合は大小でleft right へ振り分けていたが、

stringクラスはなんと >  <  がオーバーロードされていて文字コード順で比較が可能になっている。すごい。

なので変更なく使える。

typedef Assoc<string, string> AssocSS;
bool Input(string& str) {
	cout << "文字列を入力してください > " << flush;
	str = "";
	getline(cin, str);
	return ! str.empty();
}
 
void Check(const AssocSS& assoc, string str) {
	try {
		cout << assoc[str] << endl;
	}
	catch (const out_of_range& e) {
		cerr << e.what << endl;
	}
}

AssocSS assocss;
 
assocss["Type"] = "Rectangle";
assocss["Size"] = "1024×768";
assocss["Color"] = "Green";
 
string str;
while (Input(str)) {
	Check(assocss, str);
}

これら二分探索木は標準でクラステンプレートにある。

キーと値が同一なら set

キーと値が異なるなら map

この同一とか異なるっていうのは型の事かな？

また、キーに対して複数の値をもたせた

multiset

multimap

がある。それぞれset map ヘッダファイルで定義されている。

map関係のクラステンプレートメンバ関数を慣れるために使ってみた。

int main() {
#define Cout(n) cout << n << endl
#define Coutf(n) cout << n << flush
#define Coute cout << endl
	typedef map<int,string> MapIS;
	typedef MapIS::iterator Iterator;
 
	MapIS mapis;
	mapis[5] = "go";//operator[] キーが見つからなければノード追加
	mapis[7] = "nana";
	mapis[2] = "ni";
	mapis[3] = "san";
	mapis[1] = "ichi";
	
	Coutf("size :");
	Cout(mapis.size());//要素数を返す
	Coutf("empty :");
	Cout(mapis.empty());//ツリーの要素数が０かどうか
 
	Coute;
 
	Iterator f = mapis.begin();//先頭要素のイテレータを返す
	Coutf("begin()->first :");
	Cout(f->first);//Nodeメンバfirst がキー
	Coutf("begin()->second :");
	Cout(f->second );//Nodeメンバsecond が値
	//先頭要素って最小キーなのか。
 
	Coute;
 
	Iterator e = mapis.end();//終端を表すイテレータを返す
	--e;//終端を表すイテレータは何もないらしい
	Coutf("end()->first :");
	Cout(e->first);//Nodeメンバfirst がキー
	Coutf("end()->second :");
	Cout(e->second);//Nodeメンバsecond が値
	//最後の要素って最大キーなのか。
 
	MapIS mapis2;
	mapis2[4] = "yon";
	mapis2[8] = "hachi";
	mapis2[2] = "ni2";
 
	mapis.insert(mapis2.begin(), mapis2.end());//イテレータの範囲をツリーに追加する
 
 
	/*
	こんな戻り値がある
	pair<iterator,bool>
	追加位置を表すイテレータ pair::first
	値が新規に追加されたかどうか pair::scond
	*/
	Coute;
 
	mapis.insert(make_pair(10,"juu"));//make_pair ペアクラスのオブジェクトを構築する
 
	Coutf("find(8)->second :");
	Cout(mapis.find(8)->second);//キーを探してイテレータを返す
	Coute;
 
	 pair<Iterator,Iterator> pa = mapis.equal_range(5);
	 Iterator ipa = pa.first;
	 Cout("mapis.equal_range(5)");
	 Cout("Iterator ipa = pa.first;");
	 Coutf("ipa->first : ");
	 Cout(ipa->first);
	 Coutf("ipa->second : ");
	 Cout(ipa->second);
	 Coute;
	 Cout("Iterator ipa = pa.second;");
	 ipa = pa.second;
	 Coutf("ipa->first : ");
	 Cout(ipa->first);
	 Coutf("ipa->second : ");
	 Cout(ipa->second);
 
	 Coute;
 
	 pa = mapis.equal_range(6);
	 ipa = pa.first;
	 Cout("mapis.equal_range(6)");
	 Cout("Iterator ipa = pa.first;");
	 Coutf("ipa->first : ");
	 Cout(ipa->first);
	 Coutf("ipa->second : ");
	 Cout(ipa->second);
	 Coute;
	 Cout("Iterator ipa = pa.second;");
	 ipa = pa.second;
	 Coutf("ipa->first : ");
	 Cout(ipa->first);
	 Coutf("ipa->second : ");
	 Cout(ipa->second);
	 //equal_range 等しい範囲？いまいち。
	 Coute;
 
	 Cout("erase 戻り値は削除した数");
	 Cout(mapis.erase(8));//キーに一致したノードを削除
	 Coute;
 
	 //ツリーの先頭・終端ってよくわからないな。
	for (Iterator it = mapis.begin(); it != mapis.end(); ++it) {
		Coutf(it->first);
		Coutf(" : ");
		Coutf(it->second);
		cout << endl;
	}
	
	mapis.clear();//ツリーを全て削除
	system("pause");
}

知らない部分があったけど調べたらとりあえず使えた。

イテレータに

++

--

使えた。set . map . miltiset . multimap 

全て双方向イテレータらしい。

あ、やっぱり。

ノード追加するときに例えば常に大きい値をキーとして入れていくと右方向にだけ伸びたツリーが出来る。

バランスが悪くなる。

バランスをとれるようにしたものを平衡二分探索木というらしい。

これは初心者テキストだと範囲外らしい。

ここまで。