二分木 (binary tree)
今回はジェネリクスの簡単な例題として「二分木 (binary tree)」を取り上げます。
●二分木の基本
二分木は「木構造 (tree structer)」または「木 (tree)」と呼ばれるデータ構造のひとつです。木は節 (node, ノード) と呼ばれる要素に対して、階層的な関係を表したものです。身近な例では、ディレクトリの階層構造が木にあたります。ディレクトリに「ルートディレクトリ」があるように、木にも「根 (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 の二分木は、プログラムでよく使われるデータ構造です。
図 : 二分木の一例
上図に二分木の例を示します。二分木では、節に一つのデータを格納します。そして、その節の左側の子には小さいデータが、右側の子には大きいデータが配置されるように木を構成します。
この二分木をデータの探索に使うアルゴリズムが「二分探索木」です。二分探索木はデータの探索・挿入を高速に行うことができます。たとえば、上図の木から 19 を探してみましょう。まず root の 18 と比較します。18 < 19 ですから、右側の子をたどり 22 と比較します。今度は 19 < 22 なので左側の子をたどります。次は 20 と比較し 19 < 20 なので左側の子をたどり、ここで 19 を見つけることができます。
二分探索木の探索は「二分探索 (binary search)」と同じ原理です。左右どちらかの子をたどるたびに、探索するデータ数は半分になります。上図の場合でも、探索するデータ数が 15, 7, 3, 1 となり、最後に見つけることができました。
データ数を N とすると、単純な線形探索では平均で N / 2 回の比較が必要になりますが、二分探索木を使うと log 2 N 程度の回数で収まります。たとえば、データが 100個ある場合、線形探索では 50 回データを比較しなければいけないのに、二分探索木では 7 回程度の比較で済むわけです。
ただし、これは左右の部分木のバランスがとれている理想的な状態での話です。バランスが崩れると二分探索木の性能は劣化し、最悪の場合は線形探索と同じになってしまいます。そこで、左右のバランスを一定の範囲に収める「平衡木 (balanced tree)」が考案されています。有名なところでは AVL 木、赤黒木 (red-black tree)、2-3 木、B 木、B* 木などがあります。
Java のライブラリには赤黒木を用いた TreeMap や TreeSet が用意されているので、私達が二分木を作る必要はないのですが、Java のお勉強ということで、単純な二分木を実装することにします。
●節の定義
それではプログラムを作りましょう。まず最初に、二分木と節を表すクラスを定義します。
リスト : 二分木と節の定義
class BinaryTree<E extends Comparable<? super E>> implements Iterable<E> {
// 節
private class Node {
E item;
Node left;
Node right;
Node(E x) {
item = x;
left = nil;
right = nil;
}
// メソッドの定義
・・・省略・・・
}
// 終端
private Node nil = new Node(null);
// ルート
private Node root;
BinaryTree() { root = nil; }
// メソッドの定義
・・・省略・・・
}
二分木を表すクラスを BinaryTree とします。要素の比較が必要になるので、型パラメータ E には Comparable<? super E> を指定します。節を表すクラスは BinaryTree の内部クラスとして定義し、名前を Node としました。連結リストと違い、節を参照する変数が 2 つ必要になります。left が左側の子、right が右側の子を表します。連結リストのように、節を箱で表すと下図のようになります。
図 : 二分木の構造
連結リストと同様に、ルートへの参照を BinaryTree のフィールド変数 root に格納しておけば、この変数を使って二分木にアクセスすることができます。連結リストは終端を null で表しましたが、今回は終端を表す節を用意して、フィールド変数 nil にセットすることにします。節がひとつもない空の木は、変数 root に nil をセットすれば表すことができます。
今回は二分木の操作を Node のメソッドとして定義することにします。それを使って BinaryTree のメソッドを作ることにしましょう。
●データの探索
それでは、データを探索する Node のメソッド search() から作りましょう。次のリストを見てください。
リスト : データの探索
boolean search(E x) {
Node node = this;
while (node != nil) {
int r = x.compareTo(node.item);
if (r == 0) return true;
else if (r < 0)
node = node.left;
else
node = node.right;
}
return false;
}
search() には探索するデータ x を渡します。変数 node は this で初期化して、while ループで二分木をたどります。node に格納されている item と x を compareTo() で比較し、値が等しければ true を返します。x が小さいのであれば左側の子をたどり、そうでなければ右側の子をたどります。たどるべき木がなくなれば node の値は nil になるので、while ループを終了し false を返します。二分探索木の動作をそのままプログラムしているだけなので、難しいところはないと思います。
●データの挿入
次は、データを挿入するメソッド add() を作ります。このメソッドはデータを挿入した新しい木を返します。たとえば、変数 root に木が格納されている場合、データを挿入するときは次のように呼び出します。
root = root.add(x)
この処理は再帰定義を使うと簡単にプログラムできます。次のリストを見てください。
リスト : データの挿入
Node add(E x) {
if (this == nil) {
return new Node(x);
} else {
int r = x.compareTo(item);
if (r < 0)
left = left.add(x);
else if (r > 0)
right = right.add(x);
return this;
}
}
最初に節 this が nil かチェックします。そうであれば木は空なので、新しい節を new Node(x) で生成して返します。たとえば、変数 root が nil の場合、すなわち空の木であれば、新しい節が生成されて root にセットされます。
そうでなければ、x と item を比較します。x と等しいデータが見つかった場合は、新しいデータを挿入する必要はないので、何も行わずに this を返します。x が小さい場合は、左部分木に x を挿入します。ここでメソッド add() を再帰呼び出しします。そして、その返り値を left にセットして this を返します。
たとえば、left が nil の場合、再帰呼び出しの返り値は新しい節なので、それが left にセットされ、木にデータが挿入されたことになります。そして、新しいデータが挿入された木 (this) を返せばいいわけです。x が item よりも大きければ、同様に右部分木にデータを挿入します。
けっきょく、子を格納している節には、同じ子が再度セットされることになります。無駄なように思われるかもしれませんが、その分だけ簡単にプログラムを作ることができます。
●データの削除
次はデータを削除する処理を作りましょう。これは今までと違って少々面倒です。削除するデータが「葉」の場合は、それを削除するだけなので簡単ですが、木の途中のデータを削除する場合は、二分木の構成を崩さないように注意しないといけません。最初に、葉を削除する場合を説明します。下図を見てください。
図 : データの削除（葉の場合）
15 を削除する場合を考えてみましょう。15 は「葉」にあたるので、それを削除するだけで大丈夫です。親の left に nil を代入するだけです。
次に、子が一つある場合を考えてみましょう。
図 : データの削除（子が一つの場合）
16 を削除する場合、その子である 15 と置き換えれば二分探索木の構成は保たれます。これも簡単ですね。問題は、子が二つある節を削除する場合です。
図 : データの削除（子が二つの場合）
この場合、削除するデータの右部分木の中から最小値のデータ [*1] を探し、それと削除するデータと置き換えれば「右部分木 < 節 < 左部分木」の構成を崩さなくてすみます。上図で、14 を削除することを考えてみましょう。右部分木の中で 15 が最小値なので、それと 14 を置き換えます。そして、15 を格納していた節は削除します。節が最小値を格納している場合、その節の左側の子は存在しないので、その節を削除することは簡単です。
まず、木の中から最小値を探すメソッドと、最小値の節を削除するメソッドを作成しましょう。次のリストを見てください。
リスト : 最小値の探索と削除
// 最小値を探す
E searchMin() {
Node node = this;
while (node.left != nil) node = node.left;
return node.item;
}
// 最小値の節を削除
Node removeMin() {
if (left == nil) {
return right;
} else {
left = left.removeMin();
return this;
}
}
最小値は簡単に求めることができます。左側の子を順番にたどっていき、左側の子がない節に行き着いたとき、その節のデータが最小値になります。searchMin() は最小値を求めてそれを返します。最初に、変数 node を this に初期化し、node.left の値をチェックします。nil であれば左側の子がないので、その節のデータが最小値です。while ループを終了して、return で node.item を返します。
removeMin() は最小値を格納している節を削除します。left が nil の節を探すのは searchMin() と同じです。見つけたら、もう一つの子 right を返します。これで、親の左部分木が書き換えられ、最小値を持つ節が削除されます。葉の場合であれば、right は nil なので、単純に削除されることになります。
左側の子があれば removeMin() を再帰呼び出しして、その左部分木の中から最小値を探し出して削除します。そして、その返り値を left にセットして、return で this を返します。
それでは、データを削除するメソッド remove() を作ります。まず削除するデータを探索して、見つけたら子の有無に合わせた削除処理を行います。
リスト : 削除
Node remove(E x) {
if (this != nil) {
int r = x.compareTo(item);
if (r == 0) {
if (left == nil) return right;
if (right == nil) return left;
item = right.searchMin();
right = right.removeMin();
} else if (r < 0) {
left = left.remove(x);
} else {
right = right.remove(x);
}
}
return this;
}
まず、this が nil ならば木は空なので、何もしないで this を返します。削除するデータが見つからない場合や、空の木を与えた場合がこれに相当します。次に、削除するデータ x と item を比較します。等しい場合はその節を削除します。left が nil の場合は right を返し、right が nil の場合は left を返します。
子が 2 つある場合は、右部分木の最小値を searchMin() で求め、item の値を書き換えます。そして、関数 removeMin() で最小値を格納していた節を削除します。これで、削除するデータを最小値で置き換え、不要になった節を二分木から削除することができます。
x と item が等しくない場合は、左右の部分木をたどって削除するデータを探索します。この処理は今までと同じです。最後に this を返します。
[*1] 逆に、左部分木の中から最大値を探し、それと削除するデータを置き換えてもかまいません。
●巡回 (traverse)
最後に、二分木に格納されているすべてのデータにアクセスするメソッドを作りましょう。二分木はデータの大小関係を使って構成されているので、ある順番で節の要素をすべて出力すると、それはソートした結果と同じになります。すべての節を規則的な順序で回ることを「巡回 (traverse)」といいいます。このなかで、次の 3 つの方法が重要です。
- 行きがけ順
まず節のデータを出力、その後左の子、右の子の順番で出力する。 - 帰りがけ順
左の子、右の子と出力してから、節のデータを出力する。 - 通りがけ順
左の子を出力、次に節のデータを出力、最後に右の子を出力する。
名前の由来は、節のデータを出力するタイミングからきています。節に最初に到達したときに出力する方法が「行きがけ」、子を出力してその節に戻ってきたときに出力する方法が「帰りがけ」、子を出力する途中でその節に戻ってきたときに出力する方法が「通りがけ」です。
二分木は「左の子 < 節のデータ < 右の子」という関係が成り立つので、通りがけ順に出力すれば、ソートされた出力結果を得ることができます。この処理も、再帰定義を使えば簡単に実現できます。次のリストを見てください。
リスト : 木の巡回
// 巡回
void forEach(Consumer<? super E> action) {
if (this != nil) {
left.forEach(action);
action.accept(item);
right.forEach(action);
}
}
// 文字列に変換
public String toString() {
String[] s = {""};
forEach(x -> s[0] += x.toString() + " ");
return s[0];
}
メソッド forEach() は通りがけ順で木を巡回し、要素にメソッド action を適用します。this が nil でなければ、再帰呼び出しで左部分木を巡回してから item を action に適用し、そのあとで右部分木を巡回します。メソッド toString() は forEach() を使って簡単に実装することができます。
●BinaryTree クラスの作成
次はクラス BinaryTree のメソッドを作りましょう。作成するメソッドを下表に示します。
| 名前 | 機能 |
|---|---|
| void add(E x) | 二分木に x を挿入する |
| boolean contains(E x) | 二分木から x を探索する |
| void remove(E x) | 二分木から x を削除する |
| void forEach(Consumer<? super E> action) | 二分木を巡回して、要素をメソッド action に渡して呼び出す |
| String toString() | 文字列に変換する |
| Iterator<E> iterator() | イテレータを生成する |
| boolean isEmpty() | 二分木が空ならば真を返す |
プログラムは次のようになります。
リスト : クラス BinaryTree のメソッド
// 探索
public boolean contains(E x) {
return root.search(x);
}
// 挿入
public void add(E x) {
root = root.add(x);
}
// 削除
public void remove(E x) {
root = root.remove(x);
}
// 空か？
public boolean isEmpty() {
return root == nil;
}
// 巡回
public void forEach(Consumer<? super E> action) {
root.forEach(action);
}
// イテレータ
public Iterator<E> iterator() {
// 無名クラス
return new Iterator<E>() {
{
stack = new ArrayList<>();
nextNode(root);
}
private List<Node> stack;
private void nextNode(Node node) {
while (node != nil) {
stack.add(node);
node = node.left;
}
}
public boolean hasNext() { return stack.size() > 0; }
public E next() {
Node node = stack.remove(stack.size() - 1);
nextNode(node.right);
return node.item;
}
public void remove() {
throw new UnsupportedOperationException();
}
};
}
// 文字列に変換
public String toString() {
return "(" + root.toString().trim() + ")";
}
ほとんどのメソッドは該当する Node のメソッドを呼び出すだけなので簡単ですが、イテレータの処理だけが少し複雑になるので、ここで簡単に説明しましょう。イテレータは Node のメソッド forEach() をループに展開することで実現することができます。この場合、自分でスタックを管理する必要があります。
考え方は簡単です。左部分木をたどるとき、その節をスタックに積んでいきます。左部分木が空の場合、節をスタックに積む処理を終了します。このとき、スタックトップの節が、イテレータが指し示す節になります。次の節に移動するとき、スタックから節を取り出して、その節の右部分木を同様にたどればいいわけです。右部分木が空の場合は、一つ前の節に戻ることになります。
フィールド変数 stack が節を格納するスタックです。スタックの実体と初期化は匿名クラスのインスタンス初期化子で行います。節の移動は private なメソッド nextNode() で行います。nextNode() は簡単で、while ループで左部分木をたどり、通ってきた節をスタック stack に積んでいくだけです。
●実行例
それでは実際に実行してみましょう。次に示す簡単なテストを行ってみました。
リスト : 簡単なテスト
public class tree {
public static void main(String[] args) {
var xs = new BinaryTree<Integer>();
int[] a = {5, 3, 8, 1, 4, 7, 9, 2, 6};
for (int x: a) {
xs.add(x);
}
System.out.println(xs);
xs.forEach(x -> System.out.print(x + " "));
System.out.println("");
xs.forEach(System.out::println);
for (int x: xs) System.out.print(x + " ");
System.out.println("");
for (int i = 0; i <= 10; i++) {
System.out.println(xs.contains(i));
}
for (int i = 0; i <= 10; i++) {
xs.remove(i);
System.out.println(xs);
}
}
}
実行結果を示します。
$ javac tree.java $ java tree (1 2 3 4 5 6 7 8 9) 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 false true true true true true true true true true false (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.java : 二分探索木
//
// Copyright (C) 2016-2021 Makoto Hiroi
//
import java.util.Iterator;
import java.util.ArrayList;
import java.util.List;
import java.util.function.Consumer;
class BinaryTree<E extends Comparable<? super E>> implements Iterable<E> {
// 節
// アクセスメソッドは用意しない
private class Node {
E item;
Node left;
Node right;
Node(E x) {
item = x;
left = nil;
right = nil;
}
// 探索
boolean search(E x) {
Node node = this;
while (node != nil) {
int r = x.compareTo(node.item);
if (r == 0) return true;
else if (r < 0)
node = node.left;
else
node = node.right;
}
return false;
}
// 挿入
Node add(E x) {
if (this == nil) {
return new Node(x);
} else {
int r = x.compareTo(item);
if (r < 0)
left = left.add(x);
else if (r > 0)
right = right.add(x);
return this;
}
}
// 最小値を探す
E searchMin() {
Node node = this;
while (node.left != nil) node = node.left;
return node.item;
}
// 最小値の節を削除
Node removeMin() {
if (left == nil) {
return right;
} else {
left = left.removeMin();
return this;
}
}
// 削除
Node remove(E x) {
if (this != nil) {
int r = x.compareTo(item);
if (r == 0) {
if (left == nil) return right;
if (right == nil) return left;
item = right.searchMin();
right = right.removeMin();
} else if (r < 0) {
left = left.remove(x);
} else {
right = right.remove(x);
}
}
return this;
}
// 巡回
void forEach(Consumer<? super E> action) {
if (this != nil) {
left.forEach(action);
action.accept(item);
right.forEach(action);
}
}
// 文字列に変換
public String toString() {
String[] s = {""};
forEach(x -> s[0] += x.toString() + " ");
return s[0];
}
}
// 終端
private Node nil = new Node(null);
// ルート
private Node root;
BinaryTree() { root = nil; }
// メソッド
// 探索
public boolean contains(E x) {
return root.search(x);
}
// 挿入
public void add(E x) {
root = root.add(x);
}
// 削除
public void remove(E x) {
root = root.remove(x);
}
// 空か？
public boolean isEmpty() {
return root == nil;
}
// 巡回
public void forEach(Consumer<? super E> action) {
root.forEach(action);
}
// イテレータ
public Iterator<E> iterator() {
// 無名クラス
return new Iterator<E>() {
{
stack = new ArrayList<>();
nextNode(root);
}
private List<Node> stack;
private void nextNode(Node node) {
while (node != nil) {
stack.add(node);
node = node.left;
}
}
public boolean hasNext() { return stack.size() > 0; }
public E next() {
Node node = stack.remove(stack.size() - 1);
nextNode(node.right);
return node.item;
}
public void remove() {
throw new UnsupportedOperationException();
}
};
}
// 文字列に変換
public String toString() {
return "(" + root.toString().trim() + ")";
}
}
public class tree {
public static void main(String[] args) {
var xs = new BinaryTree<Integer>();
int[] a = {5, 3, 8, 1, 4, 7, 9, 2, 6};
for (int x: a) {
xs.add(x);
}
System.out.println(xs);
xs.forEach(x -> System.out.print(x + " "));
System.out.println("");
xs.forEach(System.out::println);
for (int x: xs) System.out.print(x + " ");
System.out.println("");
for (int i = 0; i <= 10; i++) {
System.out.println(xs.contains(i));
}
for (int i = 0; i <= 10; i++) {
xs.remove(i);
System.out.println(xs);
}
}
}
改訂 2021 年 2 月 21 日