今回は簡単なコンテナクラスの例題として「二分探索木 (binary search tree)」を取り上げます。二分探索木は「木構造 (tree structer)」や「木 (tree)」と呼ばれるデータ構造の一種です。
Ｃ++の標準ライブラリ (STL) には、二分木 (平衡木) を使って実装されたクラス <map> や <set> などが用意されています。私たちが二分探索木を実装する必要はありませんが、Ｃ++とデータ構造のお勉強ということで、あえてプログラムを作ってみましょう。まず最初に木について簡単に説明します。
木は「節 (ノード)」と呼ばれる要素に対して、階層的な関係を表したものです。身近な例では、ディレクトリの階層構造が木にあたります。ディレクトリに「ルートディレクトリ」があるように、木にも「根 (ルート)」と呼ばれる節が存在します。下図を見てください。
(root)
Ａ ──────── レベル０
／｜＼ ↑
／ ｜ ＼
Ｂ Ｃ Ｄ 木 レベル１
／｜＼ ｜＼ の
／ ｜ ＼ ｜ ＼ 高
Ｅ Ｆ Ｇ Ｈ Ｉ さ レベル２
／ ＼
／ ＼ ↓
Ｊ Ｋ ───── レベル３
図 : 一般的な木構造の一例
木を図示する場合、階層関係がはっきりわかるように、根を上にして、同じ階層にある節を並べて書きます。根からレベル 0、レベル 1 と階層を数えていき、最下層の節までの階層数を「木の高さ」といいます。木は、ある節から下の部分を切り出したものも、木としての性質を持っています。これを「部分木」といいます。
木は、ある節からほかの節に至る「経路」を考えることができます。たとえば、A から J には、A - B - G - J という経路がありますね。これは、ディレクトリやファイルを指定するときのパスと同じです。
ある節から根の方向にさかのぼるとき、途中で通っていく節を「先祖」といい、直接繋がっている節を「親」といます。これは、逆から見ると「子孫」と「子」という関係になります。子を持たない節をとくに「葉」と呼ぶことがあります。上図でいうと、G は J, K の親で、J は G の子になります。J は子を持っていないので葉となります。
子は、「左 < 右」の順番で節に格納するのが一般的です。これを「順序木」といいます。また、順番がない木を「無順序木」と呼びます。節が持っている子の数を「次数」といいます。上図の場合、A は 3 つの子 B, C, D を持っているので、A の次数は 3 となります。すべての節の次数を n に揃えた順序木を「 n 分木」と呼びます。特に、次数が 2 の二分木は、プログラムでよく使われるデータ構造です。
(root)
18
／ ＼
／ ＼
／ ＼
／ ＼
／ ＼
14 22
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 20 24
／ ＼ ／ ＼ ／ ＼ ／ ＼
11 13 15 17 19 21 23 25
図 : 二分木の一例
上図に二分木の例を示します。二分木では、節に一つのデータを格納します。そして、その節の左側の子には小さいデータが、右側の子には大きいデータが配置されるように木を構成します。
この二分木をデータの探索に使うアルゴリズムが「二分探索木」です。二分探索木はデータの探索・挿入を高速に行うことができます。たとえば、上図の木から 19 を探してみましょう。まず root の 18 と比較します。18 < 19 ですから、右側の子をたどり 22 と比較します。今度は 19 < 22 なので左側の子をたどります。次は 20 と比較し 19 < 20 なので左側の子をたどり、ここで 19 を見つけることができます。
二分探索木の探索は「二分探索」と同じ原理です。左右どちらかの子をたどるたびに、探索するデータ数は半分になります。上図の場合でも、探索するデータ数が 15, 7, 3, 1 となり、最後に見つけることができました。
データ数を N とすると、単純な線形探索では平均で N / 2 回の比較が必要になりますが、二分探索木を使うと log2 N 程度の回数で収まります。たとえば、データが 100個ある場合、線形探索では 50 回データを比較しなければいけないのに、二分探索木では 7 回程度の比較で済むわけです。
ただし、これは左右の部分木のバランスがとれている理想的な状態での話です。バランスが崩れると二分探索木の性能は劣化し、最悪の場合は線形探索と同じになってしまいます。そこで、左右のバランスを一定の範囲に収める「平衡木 (balanced tree)」が考案されています。有名なところでは AVL 木、赤黒木、AA 木、2-3 木、B 木、B* 木などがあります。
それではプログラムを作りましょう。平衡木を作るのはちょっと難しいので、単純な二分探索木を作ることにします。また、プログラムを簡単にするため、格納するデータは整数 (int) に限定します。まず最初に、節を表すクラス Node を定義します。
リスト : 節の定義
class Node {
int item;
Node* left;
Node* right;
public:
explicit Node(int x) : item(x), left(0), right(0) { }
int get_item() const { return item; }
Node* get_left() const { return left; }
Node* get_right() const { return right; }
void put_item(int x) { item = x; }
void put_left(Node* l) { left = l; }
void put_right(Node* r) { right = r; }
};
メンバ変数 item に整数値を格納します。連結リストと違い、節へのポインタが 2 つ必要になります。メンバ変数 left が左の子、right が右の子を表します。子を持たない場合は、連結リストと同様に 0 をセットすることにします。あとはコンストラクタとアクセス関数を定義します。
連結リストのように、節を箱で表すと下図のようになります。
変数 root
┌─┐
│ ┼──┐
└─┘ │
↓
┌─┬─┬─┐
│18│・│・│
└─┴┼┴┼┘
│ │
┌──────┘ └─┐
↓ ↓
┌─┬─┬─┐ ┌─┬─┬─┐
│14│／│／│ │22│／│／│
└─┴─┴─┘ └─┴─┴─┘
┌─┬─┬─┐
節：│Ｄ│Ｌ│Ｒ│
└─┴─┴─┘
Ｄ：data, Ｌ：left, Ｒ：right, ／：０
図 : 二分木の構造
連結リストと同様に、ルートへの参照を変数 root に格納しておけば、この変数を使って二分木にアクセスすることができます。また、節が一つもない空の木は、変数 root に 0 をセットすれば表すことができます。なお、0 のかわりに終端を表す節を用意する方法もあります。
今回は節 (Node) のほかに、root を格納するクラス IntTree を定義することにします。そして、節を操作する作業用の関数を定義し、IntTree のメンバ関数から呼び出します。
それでは、データを探索する関数 search_node から作りましょう。次のリストを見てください。
リスト : データの探索
bool search_node(int x, Node* node)
{
while (node) {
int y = node->get_item();
if (x == y)
return true;
else if (x < y)
node = node->get_left();
else
node = node->get_right();
}
return false;
}
関数 search_node には節 node と探索するデータ x を渡します。x と node の item を比較し、値が等しければ true を返します。x が小さいのであれば左の子をたどり、そうでなければ右の子をたどります。たどるべき木がなくなれば node の値は 0 になるので、while ループを終了し false を返します。二分探索木の動作をそのままプログラムしているだけなので、難しいところはないと思います。
次は、データを挿入する関数 insert_node を作ります。この関数は木を引数として受け取り、データを挿入した新しい木を返します。たとえば、変数 root に木が格納されている場合、データを挿入するときは次のように呼び出します。
root = insert_node(x, root);
この処理は再帰定義を使うと簡単にプログラムできます。次のリストを見てください。
リスト : データの挿入
Node* insert_node(int x, Node* node)
{
if (!node) return new Node(x);
int y = node->get_item();
if (x < y)
node->put_left(insert_node(x, node->get_left()));
else if (x > y)
node->put_right(insert_node(x, node->get_right()));
return node;
}
最初に節 node が終端 (0) かチェックします。そうであれば木は空なので、新しい節を new Node(x) で生成して返します。たとえば、変数 root が 0 の場合、すなわち空の木であれば、新しい節が生成されて root にセットされます。
そうでなければ、x と node の item を比較します。x と等しいデータが見つかった場合は、新しいデータを挿入する必要はないので、何も行わずに node を返します。x が小さい場合、左部分木に x を挿入します。ここで関数 insert_node を再帰呼び出しします。そして、返り値を node の left にセットして node を返します。
たとえば、node の left が 0 の場合、再帰呼び出しの返り値は新しい節なので、それが node の left にセットされ、木にデータが挿入されたことになります。そして、新しいデータが挿入された木 (node) を返せばいいわけです。x が item よりも大きければ、同様に右部分木にデータを挿入します。
けっきょく、子を格納している節には、同じ子が再度セットされることになります。無駄なように思われるかもしれませんが、その分だけ簡単にプログラムを作ることができます。
次はデータを削除する処理を作りましょう。これは今までと違って少々面倒です。削除するデータが「葉」の場合は、それを削除するだけなので簡単ですが、木の途中のデータを削除する場合は、二分木の構成を崩さないように注意しないといけません。最初に、葉を削除する場合を説明します。下図を見てください。
14 14
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 => 12 16
／ ＼ ／ ＼ ／ ＼ ／ ＼
11 13 15 17 11 13 空 17
↑
15 を削除する 削除
図 : データの削除 (葉の場合)
15 を削除する場合を考えてみましょう。15 は「葉」にあたるので、それを削除するだけで大丈夫です。親の left に 0 を代入するだけです。
次に、子が一つある場合を考えてみましょう。
14 14
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 => 12 15
／ ＼ ／ ／ ＼
11 13 15 11 13
16 を削除する
図 : データの削除 (子が一つの場合)
16 を削除する場合、その子である 15 と置き換えれば二分探索木の構成は保たれます。これも簡単ですね。問題は、子が二つある節を削除する場合です。
14 15 <- 最小値と置き換え
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 => 12 16
／ ＼ ／ ＼ ／ ＼ ／ ＼
11 13 15 17 11 13 空 17
↑
14 を削除する 削除
図 : データの削除 (子が二つの場合)
この場合、削除するデータの右部分木の中から最小値のデータ [*1] を探し、それと削除するデータと置き換えれば「右部分木 < 節 < 左部分木」の構成を崩さなくてすみます。上図で、14 を削除することを考えてみましょう。右部分木の中で 15 が最小値なので、それと 14 を置き換えます。そして、15 を格納していた節は削除します。節が最小値を格納している場合、その節の左側の子は存在しないので、その節を削除することは簡単です。
まず、木の中から最小値を探す関数と、最小値の節を削除する関数を作りましょう。次のリストを見てください。
リスト : 最小値の探索と削除
// 最小値を探す
int search_min(Node* node)
{
while (node->get_left()) node = node->get_left();
return node->get_item();
}
// 最小値の節を削除
Node* delete_min(Node* node)
{
if (!node->get_left()) {
Node* x = node->get_right();
delete node;
return x;
}
node->put_left(delete_min(node->get_left()));
return node;
}
最小値は簡単に求めることができます。左の子を順番にたどっていき、左の子がない節に行き着いたとき、その節のデータが最小値になります。関数 search_min は while ループで左の子をたどっていきます。左の子がなければ while ループを終了し、return で node の item を返します。
関数 delete_min は最小値を格納している節を削除します。左の子がない節を探すのは search_min と同じです。見つけた場合、変数 x に右の子をセットします。それから、削除する node を delete で解放して、return で x を返します。これで、親の左部分木が書き換えられ、最小値を持つ節が削除されます。葉の場合であれば右の子は 0 なので、単純に削除されることになります。
左の子があれば delete_min を再帰呼び出しして、その左部分木の中から最小値を探し出して削除します。そして、その返り値を node の left にセットして、return で node を返します。
それでは、データを削除する関数 delete_node を作ります。まず削除するデータを探索して、見つけたら子の有無に合わせた削除処理を行います。
リスト : データの削除
Node* delete_node(int x, Node* node)
{
if (!node) return node;
int y = node->get_item();
if (x == y) {
if (!node->get_left()) {
Node* x = node->get_right();
delete node;
return x;
}
if (!node->get_right()) {
Node* x = node->get_left();
delete node;
return x;
}
node->put_item(search_min(node->get_right()));
node->put_right(delete_min(node->get_right()));
} else if (x < y)
node->put_left(delete_node(x, node->get_left()));
else
node->put_right(delete_node(x, node->get_right()));
return node;
}
まず、node が 0 ならば木は空なので、何もしないで 0 を返します。削除するデータが見つからない場合や空の木を与えた場合がこれに相当します。次に、削除するデータ x と node の item を比較します。等しい場合はその節を削除します。node の left が 0 の場合は右の子を返し、node の right が 0 の場合は左の子を返します。
子が 2 つある場合は、右部分木の最小値を関数 search_min で求め、node の item の値を書き換えます。そして、関数 delete_min で最小値を格納していた節を削除します。これで、削除するデータを最小値で置き換え、不要になった節を二分木から削除することができます。x と item が等しくない場合は、左右の部分木をたどって削除するデータを探索します。最後に node を返します。
次は、二分木のすべての要素にアクセスする関数を作りましょう。二分木はデータの大小関係を使って構成されているので、ある順番で節をすべて出力すると、それはソートした結果と同じになります。「木」のすべての節を規則的な順序で回ることを「巡回 (traverse)」といいいます。このなかで、次の 3 つの方法が重要です。
名前の由来は、節のデータを出力するタイミングからきています。節に最初に到達したときに出力する方法が「行きがけ」、子を出力してその節に戻ってきたときに出力する方法が「帰りがけ」、子を出力する途中でその節に戻ってきたときに出力する方法が「通りがけ」です。
二分木は「左の子 < 節のデータ < 右の子」という関係が成り立つので、通りがけ順に出力すれば、ソートされた出力結果を得ることができます。この処理も、再帰定義を使えば簡単に実現できます。次のリストを見てください。
リスト : 木の巡回
void for_each_node(void (*func)(int), Node *node)
{
if (node) {
for_each_node(func, node->get_left());
func(node->get_item());
for_each_node(func, node->get_right());
}
}
関数 for_each_node は高階関数で、通りがけ順で木を巡回します。node が 0 でなければ、再帰呼び出しで左部分木を巡回してから関数 func(node->get_item()) を実行し、そのあとで右部分木を巡回します。
次は節をコピーする関数 copy_node と廃棄する関数 destroy_node を作ります。
リスト : 節のコピーと廃棄
// コピー
Node* copy_node(Node* node)
{
if (!node) return 0;
Node* new_node = new Node(node->get_item());
new_node->put_left(copy_node(node->get_left()));
new_node->put_right(copy_node(node->get_right()));
return new_node;
}
// 廃棄
void destroy_node(Node* node)
{
if (node) {
destroy_node(node->get_left());
destroy_node(node->get_right());
delete node;
}
}
どちらの関数も再帰定義を使うと簡単です。copy_node は引数 node が 0 ならば 0 を返します。これが再帰呼び出しの停止条件になります。そうでなければ、new Node() で新しい節を生成して変数 new_node にセットします。そして、左右の子に対して copy_node を再帰呼び出しして部分木をコピーし、その返り値を new_node の left と right にセットします。最後に new_node を返します。
destory_node も簡単です。引数 node が 0 でなければ、左部分木と右部分木を destory_node で廃棄してから、node 本体を delete で解放します。
それでは、クラス IntTree とメンバ関数を作りましょう。IntTree のメンバ関数を下表に示します。
| 関数名 | 機能 |
|---|---|
| bool search(int x) | 二分木から x を探索する |
| int min() | 二分木の最小値を求める |
| int max() | 二分木の最大値を求める |
| void insert(int x) | 二分木に x を挿入する |
| void remove(int x) | 二分木から x を削除する |
| void remove_min() | 二分木の最小値を削除する |
| void remove_max() | 二分木の最大値を削除する |
| void for_each(void (*func)(int)) | 二分木を巡回して、要素を関数 func に渡して呼び出す |
| bool empty() | 二分木が空ならば真を返す |
| Iterator begin() | 先頭要素を指し示すイテレータを生成する |
| Iterator end() | 末尾要素の次 (終端) を指し示すイテレータを生成する |
| Generator make_gen() | ジェネレータを生成する |
IntTree の定義は次のようになります。
リスト : クラス IntTree の定義
// 二分探索木
class IntTree {
Node* root;
public:
IntTree() : root(0) { }
~IntTree();
// コピーコンストラクタ
IntTree(const IntTree&);
// 代入演算子
IntTree& operator=(const IntTree& tree);
// メンバ関数
bool empty() const;
bool search(int) const;
int min() const;
int max() const;
void insert(int);
void remove(int);
void remove_min();
void remove_max();
void for_each(void (*func)(int));
// イテレータとジェネレータの定義
//
// ・・・省略・・・
//
};
IntTree のメンバ変数は root で、これが二分木の根 (ルート) になります。コンストラクタは root を 0 に初期化します。
次はメンバ関数を定義します。
リスト : メンバ関数の定義
bool IntTree::empty() const { return !root; }
bool IntTree::search(int x) const { return search_node(x, root); }
int IntTree::min() const {
if (!root) throw std::runtime_error("IntTree::min empty tree");
return search_min(root);
}
int IntTree::max() const {
if (!root) throw std::runtime_error("IntTree::max empty tree");
return search_max(root);
}
void IntTree::insert(int x) { root = insert_node(x, root); }
void IntTree::remove(int x) { root = delete_node(x, root); }
void IntTree::remove_min() {
if (!root) throw std::runtime_error("IntTree::remove_min empty tree");
root = delete_min(root);
}
void IntTree::remove_max() {
if (!root) throw std::runtime_error("IntTree::remove_max empty tree");
root = delete_max(root);
}
void IntTree::for_each(void (*func)(int)) { for_each_node(func, root); }
デストラクタは destory_node で root に格納された節のメモリを解放します。コピーコンストラクタは copy_node で引数 tree の root をコピーして自分自身の root にセットします。代入演算子は destroy_node を呼び出して root の節を削除してから、copy_node で引数 tree の root をコピーします。あとは、処理に対応する操作関数を呼び出すだけです。
次はイテレータを作りましょう。イテレータの処理は for_each_node をループに展開することで実現することができます。この場合、自分でスタックを管理しなければならないので、プログラムはちょっと複雑になります。
考え方は簡単です。左部分木をたどるとき、その節をスタックに積んでいきます。左部分木が空の場合、節をスタックに積む処理を終了します。このとき、スタックトップの節が、イテレータが指し示す節になります。次の節に移動するとき、スタックから節を取り出して、その節の右部分木を同様にたどればいいわけです。右部分木が空の場合は、一つ前の節に戻ることになります。
プログラムは次のようになります。
リスト : イテレータの定義
class IntVec {
//
// ・・・省略・・・
//
class Iterator {
Node** stack;
int sp;
static const int S_SIZE = 32;
// 次の node へ進める
void next_node(Node* node) {
while (node) {
if (sp >= S_SIZE)
throw std::runtime_error("IntTree::Iterator stack over flow");
stack[sp++] = node;
node = node->get_left();
}
}
public:
Iterator(IntTree* tree, bool end) : sp(0), stack(0) {
if (!end) {
stack = new Node* [S_SIZE];
next_node(tree->root);
}
}
~Iterator() { delete[] stack; }
//
// ・・・省略・・・
//
};
メンバ変数 stack は節を格納するスタックで、sp がスタックポインタを表します。スタックの実体はコンストラクタで確保します。引数 end が true のときは終端を表すイテレータを生成します。このとき、sp と stack は 0 のままです。スタックの大きさは S_SIZE (32) とし、オーバーフローしたら例外を送出することにします。
デストラクタは delete[] で確保した stack を解放します。節の移動は private なメンバ関数 next_node で行います。next_node は簡単で、while ループで左部分木をたどり、通ってきた節をスタック stack に積んでいくだけです。
次はイテレータを操作するメンバ関数を定義します。
リスト : Iterator のメンバ関数
class Iterator {
//
// ・・・省略・・・
//
// 前置きの ++ 演算子
Iterator& operator++() {
if (sp > 0) {
Node* node = stack[--sp];
next_node(node->get_right());
}
return *this;
}
// 間接参照 (代入は禁止)
int operator*() {
if (sp == 0) throw std::runtime_error("IntTree::Iterator out of range");
return stack[sp - 1]->get_item();
}
// 比較演算子
bool operator==(const Iterator& iter) {
return sp == iter.sp &&
(sp == 0 || stack[sp - 1] == iter.stack[sp - 1]);
}
bool operator!=(const Iterator& iter) {
return sp != iter.sp ||
(sp > 0 && stack[sp - 1] != iter.stack[sp - 1]);
}
};
++ 演算子はスタックから節を取り出し、その右の子の左部分木を next_node でたどります。間接演算子はスタックトップにある節の値を返します。節の値を書き換えると、二分木の条件を満たさなくなる場合があるので、参照を返さずに値 (int) を返しています。等値演算子は sp の値とスタックトップに格納されている節のアドレスを比較するだけです。
このほかに、コピーコンストラクタと代入演算子を定義します。処理は簡単なので説明は割愛します。詳細はプログラムリストをお読みください。
最後にジェネレータを作ります。次のリストを見てください。
リスト : ジェネレータ
class Generator {
Iterator iter;
Iterator end;
public:
Generator(IntTree* tree) :
iter(Iterator(tree, false)),
end(Iterator(tree, true))
{}
bool operator()(int& x) {
if (iter == end) return false;
x = *iter;
++iter;
return true;
}
};
ジェネレータはイテレータを使って実装します。メンバ変数 iter がイテレータで、end が終端を表すイテレータです。iter と end はコンストラクタで初期化します。あとは、演算子 () を多重定義します。iter が end と等しくなければ、引数 x に *iter をセットして、++iter でイテレータを一つ進めます。
あとのプログラムは簡単なので説明は割愛します。詳細はプログラムリストをお読みください。
それでは実際に実行してみましょう。次に示す簡単なテストを行ってみました。
リスト : 簡単なテスト
int main()
{
int a[10] = {5,6,4,7,3,8,2,9,1,0};
IntTree tree;
for (int x : a) tree.insert(x);
tree.for_each(print);
cout << endl;
IntTree tree1 = tree;
tree1.for_each(print);
cout << endl;
for (int i = -1; i <= 10; i++) cout << tree.search(i) << endl;
cout << tree.min() << endl;
cout << tree.max() << endl;
tree.remove_min();
tree.for_each(print);
cout << endl;
tree.remove_max();
tree.for_each(print);
cout << endl;
for (int x : a) {
cout << "remove " << x << endl;
tree.remove(x);
tree.for_each(print);
cout << endl;
}
cout << tree.empty() << endl;
for (auto iter = tree1.begin(); iter != tree1.end(); ++iter)
cout << *iter << " ";
cout << endl;
IntTree tree2;
tree2.insert(10);
tree2 = tree1;
for (auto iter = tree1.begin(); iter != tree1.end(); ++iter)
cout << *iter << " ";
cout << endl;
auto gen = tree1.make_gen();
int x;
while (gen(x)) cout << x << " ";
cout << endl;
}
実行結果を示します。
$ clang++ test_inttree.cpp inttree.cpp $ ./a.out 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1 1 1 1 1 1 1 1 1 0 0 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 remove 5 1 2 3 4 6 7 8 remove 6 1 2 3 4 7 8 remove 4 1 2 3 7 8 remove 7 1 2 3 8 remove 3 1 2 8 remove 8 1 2 remove 2 1 remove 9 1 remove 1 remove 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
正常に動作していますね。
//
// inttree.h : 二分探索木
//
// Copyright (C) 2015-2023 Makoto Hiroi
//
#ifndef _INTTREE_H_
#define _INTTREE_H_
#include <iostream>
#include <stdexcept>
// 節
class Node {
int item;
Node* left;
Node* right;
public:
explicit Node(int x) : item(x), left(0), right(0) { }
int get_item() const { return item; }
Node* get_left() const { return left; }
Node* get_right() const { return right; }
void put_item(int x) { item = x; }
void put_left(Node* l) { left = l; }
void put_right(Node* r) { right = r; }
};
// 二分探索木
class IntTree {
Node* root;
public:
IntTree() : root(0) { }
~IntTree();
// コピーコンストラクタ
IntTree(const IntTree&);
// 代入演算子
IntTree& operator=(const IntTree& tree);
// メンバ関数
bool empty() const;
bool search(int) const;
int min() const;
int max() const;
void insert(int);
void remove(int);
void remove_min();
void remove_max();
void for_each(void (*func)(int));
// イテレータ
class Iterator {
Node** stack;
int sp;
static const int S_SIZE = 32;
// 次の node へ進める
void next_node(Node* node) {
while (node) {
if (sp >= S_SIZE)
throw std::runtime_error("IntTree::Iterator stack over flow");
stack[sp++] = node;
node = node->get_left();
}
}
public:
Iterator(IntTree* tree, bool end) : sp(0), stack(0) {
if (!end) {
stack = new Node* [S_SIZE];
next_node(tree->root);
}
}
~Iterator() { delete[] stack; }
// コピーコンストラクタ
Iterator(const Iterator& iter) {
if (iter.stack != 0) {
stack = new Node* [S_SIZE];
for (int i = 0; i < S_SIZE; i++)
stack[i] = iter.stack[i];
}
sp = iter.sp;
}
// 代入演算子
Iterator& operator=(const Iterator& iter) {
delete[] stack;
if (iter.stack != 0) {
stack = new Node* [S_SIZE];
for (int i = 0; i < S_SIZE; i++)
stack[i] = iter.stack[i];
} else {
stack = 0;
}
sp = iter.sp;
return *this;
}
// 前置きの ++ 演算子
Iterator& operator++() {
if (sp > 0) {
Node* node = stack[--sp];
next_node(node->get_right());
}
return *this;
}
// 間接参照 (代入は禁止)
int operator*() {
if (sp == 0) throw std::runtime_error("IntTree::Iterator out of range");
return stack[sp - 1]->get_item();
}
// 比較演算子
bool operator==(const Iterator& iter) {
return sp == iter.sp &&
(sp == 0 || stack[sp - 1] == iter.stack[sp - 1]);
}
bool operator!=(const Iterator& iter) {
return sp != iter.sp ||
(sp > 0 && stack[sp - 1] != iter.stack[sp - 1]);
}
};
Iterator begin() { return Iterator(this, false); }
Iterator end() { return Iterator(this, true); }
// ジェネレータ
class Generator {
Iterator iter;
Iterator end;
public:
Generator(IntTree* tree) :
iter(Iterator(tree, false)),
end(Iterator(tree, true))
{}
bool operator()(int& x) {
if (iter == end) return false;
x = *iter;
++iter;
return true;
}
};
Generator make_gen() { return Generator(this); }
};
#endif
//
// inttree.cpp : 二分探索木
//
// Copyright (C) 2015-2023 Makoto Hiroi
//
#include "inttree.h"
// 探索
bool search_node(int x, Node* node)
{
while (node) {
int y = node->get_item();
if (x == y) return true;
else if (x < y)
node = node->get_left();
else
node = node->get_right();
}
return false;
}
// 挿入
Node* insert_node(int x, Node* node)
{
if (!node) return new Node(x);
int y = node->get_item();
if (x < y)
node->put_left(insert_node(x, node->get_left()));
else if (x > y)
node->put_right(insert_node(x, node->get_right()));
return node;
}
// 最小値を探す
int search_min(Node* node)
{
while (node->get_left()) node = node->get_left();
return node->get_item();
}
// 最小値の節を削除
Node* delete_min(Node* node)
{
if (!node->get_left()) {
Node* x = node->get_right();
delete node;
return x;
}
node->put_left(delete_min(node->get_left()));
return node;
}
// 最大値を探す
int search_max(Node* node)
{
while (node->get_right()) node = node->get_right();
return node->get_item();
}
// 最大値の節を削除
Node* delete_max(Node* node)
{
if (!node->get_right()) {
Node* x = node->get_left();
delete node;
return x;
}
node->put_right(delete_max(node->get_right()));
return node;
}
// 削除
Node* delete_node(int x, Node* node)
{
if (!node) return node;
int y = node->get_item();
if (x == y) {
if (!node->get_left()) {
Node* x = node->get_right();
delete node;
return x;
}
if (!node->get_right()) {
Node* x = node->get_left();
delete node;
return x;
}
node->put_item(search_min(node->get_right()));
node->put_right(delete_min(node->get_right()));
} else if (x < y)
node->put_left(delete_node(x, node->get_left()));
else
node->put_right(delete_node(x, node->get_right()));
return node;
}
// 巡回
void for_each_node(void (*func)(int), Node *node)
{
if (node) {
for_each_node(func, node->get_left());
func(node->get_item());
for_each_node(func, node->get_right());
}
}
// コピー
Node* copy_node(Node* node)
{
if (!node) return 0;
Node* new_node = new Node(node->get_item());
new_node->put_left(copy_node(node->get_left()));
new_node->put_right(copy_node(node->get_right()));
return new_node;
}
// 廃棄
void destroy_node(Node* node)
{
if (node) {
destroy_node(node->get_left());
destroy_node(node->get_right());
delete node;
}
}
// デストラクタ
IntTree:: ~IntTree() { destroy_node(root); }
// コピーコンストラクタ
IntTree:: IntTree(const IntTree& tree) {
root = copy_node(tree.root);
}
// 代入演算子
IntTree& IntTree::operator=(const IntTree& tree) {
destroy_node(root);
root = copy_node(tree.root);
return *this;
}
// メンバ関数
bool IntTree::empty() const { return !root; }
bool IntTree::search(int x) const { return search_node(x, root); }
int IntTree::min() const {
if (!root) throw std::runtime_error("IntTree::min empty tree");
return search_min(root);
}
int IntTree::max() const {
if (!root) throw std::runtime_error("IntTree::max empty tree");
return search_max(root);
}
void IntTree::insert(int x) { root = insert_node(x, root); }
void IntTree::remove(int x) { root = delete_node(x, root); }
void IntTree::remove_min() {
if (!root) throw std::runtime_error("IntTree::remove_min empty tree");
root = delete_min(root);
}
void IntTree::remove_max() {
if (!root) throw std::runtime_error("IntTree::remove_max empty tree");
root = delete_max(root);
}
void IntTree::for_each(void (*func)(int)) { for_each_node(func, root); }
//
// test_inttree.cpp : 二分探索木のテスト
//
// Copyright (C) 2015-2023 Makoto Hiroi
//
#include "inttree.h"
using namespace std;
void print(int x) { cout << x << " "; }
int main()
{
int a[10] = {5,6,4,7,3,8,2,9,1,0};
IntTree tree;
for (int x : a) tree.insert(x);
tree.for_each(print);
cout << endl;
IntTree tree1 = tree;
tree1.for_each(print);
cout << endl;
for (int i = -1; i <= 10; i++) cout << tree.search(i) << endl;
cout << tree.min() << endl;
cout << tree.max() << endl;
tree.remove_min();
tree.for_each(print);
cout << endl;
tree.remove_max();
tree.for_each(print);
cout << endl;
for (int x : a) {
cout << "remove " << x << endl;
tree.remove(x);
tree.for_each(print);
cout << endl;
}
cout << tree.empty() << endl;
for (auto iter = tree1.begin(); iter != tree1.end(); ++iter)
cout << *iter << " ";
cout << endl;
IntTree tree2;
tree2.insert(10);
tree2 = tree1;
for (auto iter = tree1.begin(); iter != tree1.end(); ++iter)
cout << *iter << " ";
cout << endl;
auto gen = tree1.make_gen();
int x;
while (gen(x)) cout << x << " ";
cout << endl;
}