今回は簡単な例題として「二分探索木 (binary search tree)」を取り上げます。二分探索木は「木構造 (tree structer)」または「木 (tree)」と呼ばれるデータ構造の一種です。最初に木について簡単に説明します。
木は節 (ノード) と呼ばれる要素に対して、階層的な関係を表したものです。身近な例では、ディレクトリの階層構造が木にあたります。ディレクトリに「ルートディレクトリ」があるように、木にも「根 (ルート)」と呼ばれる節が存在します。下図を見てください。
(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* 木などがあります。
それではプログラムを作りましょう。まず最初に、節を表すクラス Node を定義します。次のリストを見てください。
リスト : 節の定義
package Node;
# 終端
our $None = {};
bless $None, 'Node';
# 終端か
sub null {
my $x = shift;
ref $x eq 'Node' && $x == $None;
}
# 節の生成
sub new {
my ($type, $item, $left, $right) = @_;
my $node = {item => $item, left => $left, right => $right};
bless $node, $type;
$node;
}
連結リストと同様に、終端を表す無名のハッシュを大域変数 $None にセットします。$None は終端だけではなく、「空の木」という意味もあります。メソッド null は節が終端かチェックします。引数 $x が Node のインスタンスであれば、演算子 == で $None と比較します。
連結リストと違い、二分木の節には節を参照する変数が 2 つ必要になります。キー left が左の子、キー right が右の子を表します。子を持たない場合は $None をセットすることにします。データはキー item に格納します。
連結リストのように、節を箱で表すと下図のようになります。
変数 root
┌─┐
│ ┼──┐
└─┘ │
↓
┌─┬─┬─┐
│18│・│・│
└─┴┼┴┼┘
│ │
┌──────┘ └─┐
↓ ↓
┌─┬─┬─┐ ┌─┬─┬─┐
│14│／│／│ │22│／│／│
└─┴─┴─┘ └─┴─┴─┘
┌─┬─┬─┐
節：│Ｄ│Ｌ│Ｒ│
└─┴─┴─┘
Ｄ：data, Ｌ：left, Ｒ：right, ／：$None
図 : 二分木の構造
連結リストと同様に、ルートへの参照を変数 root に格納しておけば、この変数を使って二分木にアクセスすることができます。また、節が一つもない空の木は、変数 root に $None をセットすれば表すことができます。
今回は二分木の操作をクラス Node のメソッドとして定義することにします。それを使って二分木を表すクラス Tree とそのメソッドを作ることにしましょう。
次は節のアクセスメソッドを定義します。
リスト : 節のアクセスメソッド
sub item {
my $node = shift;
$node->{'item'};
}
sub left {
my $node = shift;
$node->{'left'};
}
sub right {
my $node = shift;
$node->{'right'};
}
sub set_item {
my ($node, $x) = @_;
$node->{'item'} = $x;
}
sub set_left {
my ($node, $x) = @_;
$node->{'left'} = $x;
}
sub set_right {
my ($node, $x) = @_;
$node->{'right'} = $x;
}
item, set_item がキー item のアクセスメソッド、left と set_left がキー left のアクセスメソッド、right と set_right がキー right のアクセスメソッドです。プログラムは簡単なので、説明は不要でしょう。
それでは、データを探索するメソッド search_node から作りましょう。次のリストを見てください。
リスト : データの探索
sub search_node {
my ($node, $x) = @_;
while (!$node->null()) {
if ($x == $node->item()) {
return 1;
} elsif ($x < $node->item()) {
$node = $node->left();
} else {
$node = $node->right();
}
}
0;
}
メソッド search_node には節 $node と探索するデータ $x を渡します。$x と $node->item() を比較し、値が等しければ 1 を返します。$x が小さいのであれば左の子をたどり、そうでなければ右の子をたどります。たどるべき木がなくなれば $node の値は $None になるので、while ループを終了し 0 を返します。二分探索木の動作をそのままプログラムしているだけなので、難しいところはないと思います。
次は、データを挿入するメソッド insert_node を作ります。このメソッドは木を引数として受け取り、データを挿入した新しい木を返します。たとえば、変数 root に木が格納されている場合、データを挿入するときは次のように呼び出します。
$root = $root->insert_node($x);
この処理は再帰定義を使うと簡単にプログラムできます。次のリストを見てください。
リスト : データの挿入
sub insert_node {
my ($node, $x) = @_;
if ($node->null()) {
return Node->new($x, $None, $None);
} elsif ($x < $node->item()) {
$node->set_left($node->left()->insert_node($x));
} elsif ($x > $node->item()) {
$node->set_right($node->right()->insert_node($x));
}
$node;
}
最初に節 $node が $None かチェックします。そうであれば木は空なので、新しい節を Node->new() で生成して返します。たとえば、変数 root が $None の場合、すなわち空の木であれば、新しい節が生成されて root にセットされます。
そうでなければ、$x と $node->item() を比較します。$x と等しいデータが見つかった場合は、新しいデータを挿入する必要はないので、何も行わずに $node を返します。$x が小さい場合は、左部分木に $x を挿入します。ここでメソッド insert_node を再帰呼び出しします。そして、set_left で返り値を $node の left にセットして $node を返します。
たとえば、$node の left が $None の場合、再帰呼び出しの返り値は新しい節なので、それが $node の left にセットされ、木にデータが挿入されたことになります。そして、新しいデータが挿入された木 ($node) を返せばいいわけです。$x が $node の item よりも大きければ、同様に右部分木にデータを挿入します。
けっきょく、子を格納している節には、同じ子が再度セットされることになります。無駄なように思われるかもしれませんが、その分だけ簡単にプログラムを作ることができます。
次はデータを削除する処理を作りましょう。これは今までと違って少々面倒です。削除するデータが「葉」の場合は、それを削除するだけなので簡単ですが、木の途中のデータを削除する場合は、二分木の構成を崩さないように注意しないといけません。最初に、葉を削除する場合を説明します。下図を見てください。
14 14
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 => 12 16
／ ＼ ／ ＼ ／ ＼ ／ ＼
11 13 15 17 11 13 $None 17
↑
15 を削除する 削除
図 : データの削除 (葉の場合)
15 を削除する場合を考えてみましょう。15 は「葉」にあたるので、それを削除するだけで大丈夫です。親の left に $None を代入するだけです。
次に、子が一つある場合を考えてみましょう。
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 $None 17
↑
14 を削除する 削除
図 : データの削除 (子が二つの場合)
この場合、削除するデータの右部分木の中から最小値のデータ [*1] を探し、それと削除するデータと置き換えれば「右部分木 < 節 < 左部分木」の構成を崩さなくてすみます。上図で、14 を削除することを考えてみましょう。右部分木の中で 15 が最小値なので、それと 14 を置き換えます。そして、15 を格納していた節は削除します。節が最小値を格納している場合、その節の左側の子は存在しないので、その節を削除することは簡単です。
まず、木の中から最小値を探すメソッドと、最小値の節を削除するメソッドを作りましょう。次のリストを見てください。
リスト : 最小値の探索と削除
# 最小値の探索
sub search_min_node {
my $node = shift;
if ($node->left()->null()) {
$node->item();
} else {
$node->left()->search_min_node();
}
}
# 最小値の削除
sub delete_min_node {
my $node = shift;
if ($node->left()->null()) {
$node->right();
} else {
$node->set_left($node->left()->delete_min_node());
$node;
}
}
最小値は簡単に求めることができます。左の子を順番にたどっていき、左の子がない節に行き着いたとき、その節のデータが最小値になります。メソッド search_min は、最小値を求めてそれを返します。最初に、$node->left() の値をチェックします。もし、$None であれば左の子がないので、その節のデータが最小値です。$node->item() の値を返します。そうでなければ、search_min を再帰呼び出しして左の子をたどります。
メソッド delete_min は最小値を格納している節を削除します。$node->left() が $None の節を探すのは search_min と同じです。見つけたら、もう一つの子 $node->right () を返します。これで、親の左部分木が書き換えられ、最小値を持つ節が削除されます。葉の場合であれば $node->right() は $None なので、単純に削除されることになります。
左の子があれば delete_min を再帰呼び出しして、その左部分木の中から最小値を探し出して削除します。そして、その返り値を $node の left にセットしてから $node を返します。
それでは、データを削除するメソッド delete_node を作ります。削除するデータを探索して、見つけたら子の有無に合わせた削除処理を行います。
リスト : データの削除
sub delete_node {
my ($node, $x) = @_;
return $node if $node->null();
if ($node->item() == $x) {
return $node->right() if $node->left()->null();
return $node->left() if $node->right()->null();
my $item = $node->right()->search_min_node();
$node->set_item($item);
$node->set_right($node->right()->delete_min_node());
} elsif ($node->item > $x) {
$node->set_left($node->left()->delete_node($x));
} else {
$node->set_right($node->right()->delete_node($x));
}
$node;
}
まず、$node が $None ならば木は空なので、何もしないで $node を返します。削除するデータが見つからない場合や空の木を与えた場合がこれに相当します。次に、削除するデータ $x と $node->item() を比較します。等しい場合はその節を削除します。node->left() が $None の場合は $node->right() を返し、$node->right() が $None の場合は $node->left() を返します。
子が 2 つある場合は、右部分木の最小値をメソッド search_min で求め、$node の item にセットします。そして、メソッド delete_min で最小値を格納していた節を削除します。これで、削除するデータを最小値で置き換え、不要になった節を二分木から削除することができます。$x と $node->item() が等しくない場合は、左右の部分木をたどって削除するデータを探索します。この処理は今までと同じです。最後に $node を返します。
最後に、二分木の全データにアクセスするメソッドを作りましょう。二分木はデータの大小関係を使って構成されているので、ある順番で節をすべて出力すると、それはソートした結果と同じになります。「木」のすべての節を規則的な順序で回ることを「巡回 (traverse)」といいいます。このなかで、次の 3 つの方法が重要です。
名前の由来は、節のデータを出力するタイミングからきています。節に最初に到達したときに出力する方法が「行きがけ」、子を出力してその節に戻ってきたときに出力する方法が「帰りがけ」、子を出力する途中でその節に戻ってきたときに出力する方法が「通りがけ」です。
二分木は「左の子 < 節のデータ < 右の子」という関係が成り立つので、通りがけ順に出力すれば、ソートされた出力結果を得ることができます。この処理も、再帰定義を使えば簡単に実現できます。次のリストを見てください。
リスト : 木の巡回
sub each_node {
my ($node, $func) = @_;
if (!$node->null()) {
$node->left()->each_node($func);
$func->($node->item());
$node->right()->each_node($func);
}
}
メソッド each_node は高階関数で、通りがけ順で木を巡回し、データに関数 $func を適用します。$node が $None でなければ、再帰呼び出しで左部分木を巡回してから $func->(node->item()) を実行し、そのあとで右部分木を巡回します。たとえば、次に示すようにデータを出力するメソッドを引数 $func に与えれば、二分木のデータを昇順に表示することができます。
$node->each_node(sub {my $x = shift; print $x, " ";});
最後に、クラス Tree とメソッドを定義します。
リスト : クラス Tree とメソッドの定義
package Tree;
# 二分木の生成
sub new {
my $type = shift;
my $tree = {root => $Node::None};
bless $tree, $type;
$tree;
}
# アクセスメソッド
sub root {
my $tree = shift;
$tree->{'root'};
}
sub set_root {
my ($tree, $node) = @_;
$tree->{'root'} = $node;
}
# 探索
sub search_tree {
my ($tree, $x) = @_;
$tree->root()->search_node($x);
}
# 挿入
sub insert_tree {
my ($tree, $x) = @_;
$tree->set_root($tree->root()->insert_node($x));
}
# 削除
sub delete_tree {
my ($tree, $x) = @_;
$tree->set_root($tree->root()->delete_node($x));
}
# 巡回
sub each {
my ($tree, $func) = @_;
$tree->root()->each_node($func);
}
# 空の木か
sub is_empty {
my $tree = shift;
$tree->root()->null();
}
Tree のフィールド変数は root で、これが二分木の根 (ルート) になります。あとは、Tree のメソッドに対応する Node のメソッドを呼び出すだけです。
それでは簡単なテストを行ってみましょう。
リスト : 簡単なテスト
use strict;
use warnings;
use Tree;
my $a = Tree->new();
foreach my $x (5,6,4,7,3,8,2,9,1,0) {
$a->insert_tree($x);
$a->each(sub { print shift, " " });
print "\n";
}
foreach my $x (0 .. 10) {
print $a->search_tree($x), " ";
}
print "\n";
foreach my $x (0 .. 10) {
$a->delete_tree($x);
$a->each(sub { print shift, " " });
print "\n";
}
実行結果は次のようになります。
$ perl -I. testtree.pl 5 5 6 4 5 6 4 5 6 7 3 4 5 6 7 3 4 5 6 7 8 2 3 4 5 6 7 8 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 0 1 2 3 4 5 6 7 8 9 2 3 4 5 6 7 8 9 3 4 5 6 7 8 9 4 5 6 7 8 9 5 6 7 8 9 6 7 8 9 7 8 9 8 9 9
正常に動作していますね。
#
# Tree.pm : 二分探索木
#
# Copyright (C) 2015 Makoto Hiroi
#
use strict;
use warnings;
package Node;
# 終端
our $None = {};
bless $None, 'Node';
# 終端か
sub null {
my $x = shift;
ref $x eq 'Node' && $x == $None;
}
# 節の生成
sub new {
my ($type, $item, $left, $right) = @_;
my $node = {item => $item, left => $left, right => $right};
bless $node, $type;
$node;
}
# アクセスメソッド
sub item {
my $node = shift;
$node->{'item'};
}
sub left {
my $node = shift;
$node->{'left'};
}
sub right {
my $node = shift;
$node->{'right'};
}
sub set_item {
my ($node, $x) = @_;
$node->{'item'} = $x;
}
sub set_left {
my ($node, $x) = @_;
$node->{'left'} = $x;
}
sub set_right {
my ($node, $x) = @_;
$node->{'right'} = $x;
}
# 探索
sub search_node {
my ($node, $x) = @_;
while (!$node->null()) {
if ($x == $node->item()) {
return 1;
} elsif ($x < $node->item()) {
$node = $node->left();
} else {
$node = $node->right();
}
}
0;
}
# 挿入
sub insert_node {
my ($node, $x) = @_;
if ($node->null()) {
return Node->new($x, $None, $None);
} elsif ($x < $node->item()) {
$node->set_left($node->left()->insert_node($x));
} elsif ($x > $node->item()) {
$node->set_right($node->right()->insert_node($x));
}
$node;
}
# 最小値の探索
sub search_min_node {
my $node = shift;
if ($node->left()->null()) {
$node->item();
} else {
$node->left()->search_min_node();
}
}
# 最小値の削除
sub delete_min_node {
my $node = shift;
if ($node->left()->null()) {
$node->right();
} else {
$node->set_left($node->left()->delete_min_node());
$node;
}
}
# 削除
sub delete_node {
my ($node, $x) = @_;
return $node if $node->null();
if ($node->item() == $x) {
return $node->right() if $node->left()->null();
return $node->left() if $node->right()->null();
my $item = $node->right()->search_min_node();
$node->set_item($item);
$node->set_right($node->right()->delete_min_node());
} elsif ($node->item > $x) {
$node->set_left($node->left()->delete_node($x));
} else {
$node->set_right($node->right()->delete_node($x));
}
$node;
}
# 巡回
sub each_node {
my ($node, $func) = @_;
if (!$node->null()) {
$node->left()->each_node($func);
$func->($node->item());
$node->right()->each_node($func);
}
}
package Tree;
# 二分木の生成
sub new {
my $type = shift;
my $tree = {root => $Node::None};
bless $tree, $type;
$tree;
}
# アクセスメソッド
sub root {
my $tree = shift;
$tree->{'root'};
}
sub set_root {
my ($tree, $node) = @_;
$tree->{'root'} = $node;
}
# 探索
sub search_tree {
my ($tree, $x) = @_;
$tree->root()->search_node($x);
}
# 挿入
sub insert_tree {
my ($tree, $x) = @_;
$tree->set_root($tree->root()->insert_node($x));
}
# 削除
sub delete_tree {
my ($tree, $x) = @_;
$tree->set_root($tree->root()->delete_node($x));
}
# 巡回
sub each {
my ($tree, $func) = @_;
$tree->root()->each_node($func);
}
# 空の木か
sub is_empty {
my $tree = shift;
$tree->root()->null();
}
1;