今回は簡単な例題として「二分探索木 (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 木、2 色木 (赤黒木)、2-3 木、B 木、B* 木などがあります。
それではプログラムを作りましょう。まず最初に、節を表す構造体を定義します。
リスト : 節の定義
// 格納するデータのインターフェース
type Item interface {
Eq(Item) bool
Less(Item) bool
}
// 節
type Node struct {
item Item
left, right *Node
}
// 節の生成
func newNode(x Item) *Node {
p := new(Node)
p.item = x
return p
}
連結リストと違い、節を参照する変数が 2 つ必要になります。left が左の子、right が右の子を表します。子を持たない場合は、連結リストと同様に nil をセットすることにします。二分木に格納するデータの型はインターフェース Item で表します。メソッド x.Eq(y) は x と y が等しい場合は true を返します。x.Less(y) は x < y ならば true を返します。この場合、ポリモーフィズムと型アサーションが働くので、実行時間は遅くなると思います。これはあとで試してみましょう。
連結リストのように、節を箱で表すと下図のようになります。
変数 root
┌─┐
│ ┼──┐
└─┘ │
↓
┌─┬─┬─┐
│18│・│・│
└─┴┼┴┼┘
│ │
┌──────┘ └─┐
↓ ↓
┌─┬─┬─┐ ┌─┬─┬─┐
│14│／│／│ │22│／│／│
└─┴─┴─┘ └─┴─┴─┘
┌─┬─┬─┐
節：│Ｄ│Ｌ│Ｒ│
└─┴─┴─┘
Ｄ：data, Ｌ：left, Ｒ：right, ／：nil
図 : 二分木の構造
連結リストと同様に、ルートへの参照を変数 root に格納しておけば、この変数を使って二分木にアクセスすることができます。また、節が一つもない空の木は、変数 root に nil をセットすれば表すことができます。なお、nil のかわりに終端を表す節を用意する方法もあります。
今回は二分木の操作を関数として定義することにします。それを使って二分木を表す構造体 Tree とメソッドを作ることにしましょう。
それでは、データを探索する関数 searchNode から作りましょう。次のリストを見てください。
リスト : データの探索
func searchNode(node *Node, x Item) bool {
for node != nil {
switch {
case x.Eq(node.item): return true
case x.Less(node.item): node = node.left
default: node = node.right
}
}
return false
}
関数 searchNode には節 node と探索するデータ x を渡します。x と node.item を比較し、値が等しければ true を返します。x が小さいのであれば左の子をたどり、そうでなければ右の子をたどります。たどるべき木がなくなれば node の値は nil になるので、for ループを終了し false を返します。二分探索木の動作をそのままプログラムしているだけなので、難しいところはないと思います。
次は、データを挿入する関数 insertNode を作ります。この関数は木を引数として受け取り、データを挿入した新しい木を返します。たとえば、変数 root に木が格納されている場合、データを挿入するときは次のように呼び出します。
root = insertNode(root, x)
この処理は再帰定義を使うと簡単にプログラムできます。次のリストを見てください。
リスト : データの挿入
func insertNode(node *Node, x Item) *Node {
switch {
case node == nil: return newNode(x)
case x.Eq(node.item): return node
case x.Less(node.item):
node.left = insertNode(node.left, x)
default:
node.right = insertNode(node.right, x)
}
return node
}
最初に節 node が nil かチェックします。そうであれば木は空なので、新しい節を newNode(x) で生成して返します。たとえば、変数 root が nil の場合、すなわち空の木であれば、新しい節が生成されて root にセットされます。
そうでなければ、x と node.item を比較します。x と等しいデータが見つかった場合は、新しいデータを挿入する必要はないので、何も行わずに node を返します。x が小さい場合は、左部分木に x を挿入します。ここで関数 insertNode を再帰呼び出しします。そして、返り値を node.left にセットして node を返します。
たとえば、node.left が nil の場合、再帰呼び出しの返り値は新しい節なので、それが node.left にセットされ、木にデータが挿入されたことになります。そして、新しいデータが挿入された木 (node) を返せばいいわけです。x が item よりも大きければ、同様に右部分木にデータを挿入します。
けっきょく、子を格納している節には、同じ子が再度セットされることになります。無駄なように思われるかもしれませんが、その分だけ簡単にプログラムを作ることができます。
次はデータを削除する処理を作りましょう。これは今までと違って少々面倒です。削除するデータが「葉」の場合は、それを削除するだけなので簡単ですが、木の途中のデータを削除する場合は、二分木の構成を崩さないように注意しないといけません。最初に、葉を削除する場合を説明します。下図を見てください。
14 14
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 => 12 16
／ ＼ ／ ＼ ／ ＼ ／ ＼
11 13 15 17 11 13 nil 17
↑
15 を削除する 削除
図 : データの削除（葉の場合）
15 を削除する場合を考えてみましょう。15 は「葉」にあたるので、それを削除するだけで大丈夫です。親の left に nil を代入するだけです。
次に、子が一つある場合を考えてみましょう。
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 nil 17
↑
14 を削除する 削除
図 : データの削除（子が二つの場合）
この場合、削除するデータの右部分木の中から最小値のデータ [*1] を探し、それと削除するデータと置き換えれば「右部分木 < 節 < 左部分木」の構成を崩さなくてすみます。上図で、14 を削除することを考えてみましょう。右部分木の中で 15 が最小値なので、それと 14 を置き換えます。そして、15 を格納していた節は削除します。節が最小値を格納している場合、その節の左側の子は存在しないので、その節を削除することは簡単です。
まず、木の中から最小値を探す関数と、最小値の節を削除する関数を作りましょう。次のリストを見てください。
リスト : 最小値の探索と削除
// 最小値を求める
func searchMin(node *Node) Item {
if node.left == nil {
return node.item
}
return searchMin(node.left)
}
// 最小値を削除する
func deleteMin(node *Node) *Node {
if node.left == nil {
return node.right
}
node.left = deleteMin(node.left)
return node
}
最小値は簡単に求めることができます。左の子を順番にたどっていき、左の子がない節に行き着いたとき、その節のデータが最小値になります。関数 searchMin は、最小値を求めてそれを返します。最初に、node.left の値をチェックします。もし、nil であれば左の子がないので、その節のデータが最小値です。return で node.item を返します。そうでなければ、searchMin を再帰呼び出しして左の子をたどります。
関数 deleteMin は最小値を格納している節を削除します。node.left が nil の節を探すのは searchMin と同じです。見つけたら、もう一つの子 node.right を返します。これで、親の左部分木が書き換えられ、最小値を持つ節が削除されます。葉の場合であれば node.right は nil なので、単純に削除されることになります。
左の子があれば deleteMin を再帰呼び出しして、その左部分木の中から最小値を探し出して削除します。そして、その返り値を node.left にセットして、return で node を返します。
それでは、データを削除する関数 delete を作ります。まず削除するデータを探索して、見つけたら子の有無に合わせた削除処理を行います。
リスト : データの削除
func deleteNode(node *Node, x Item) *Node {
if node != nil {
if x.Eq(node.item) {
if node.left == nil {
return node.right
} else if node.right == nil {
return node.left
} else {
node.item = searchMin(node.right)
node.right = deleteMin(node.right)
}
} else if x.Less(node.item) {
node.left = deleteNode(node.left, x)
} else {
node.right = deleteNode(node.right, x)
}
}
return node
}
まず、node が nil ならば木は空なので、何もしないで node を返します。削除するデータが見つからない場合や空の木を与えた場合がこれに相当します。次に、削除するデータ x と node.item を比較します。等しい場合はその節を削除します。node.left が nil の場合は node.right を返し、node.right が nil の場合は node.left を返します。
子が 2 つある場合は、右部分木の最小値を関数 searchMin で求め、node.item の値を書き換えます。そして、関数 deleteMin で最小値を格納していた節を削除します。これで、削除するデータを最小値で置き換え、不要になった節を二分木から削除することができます。
x と item が等しくない場合は、左右の部分木をたどって削除するデータを探索します。この処理は今までと同じです。最後に node を返します。
最後に、二分木の全データにアクセスする関数を作りましょう。二分木はデータの大小関係を使って構成されているので、ある順番で節をすべて出力すると、それはソートした結果と同じになります。「木」のすべての節を規則的な順序で回ることを「巡回 (traverse) 」といいいます。このなかで、次の 3 つの方法が重要です。
名前の由来は、節のデータを出力するタイミングからきています。節に最初に到達したときに出力する方法が「行きがけ」、子を出力してその節に戻ってきたときに出力する方法が「帰りがけ」、子を出力する途中でその節に戻ってきたときに出力する方法が「通りがけ」です。
二分木は「左の子 < 節のデータ < 右の子」という関係が成り立つので、通りがけ順に出力すれば、ソートされた出力結果を得ることができます。この処理も、再帰定義を使えば簡単に実現できます。次のリストを見てください。
リスト : 木の巡回
func foreachNode(f func(Item), node *Node) {
if node != nil {
foreachNode(f, node.left)
f(node.item)
foreachNode(f, node.right)
}
}
関数 traverseNode は高階関数で、通りがけ順で木を巡回し、データに関数 f を適用します。node が nil でなければ、再帰呼び出しで左部分木を巡回してから f(nod.item) を実行し、そのあとで右部分木を巡回します。たとえば、次に示すようにデータを出力する関数を引数 f に与えれば、二分木のデータを昇順に表示することができます。
func(x int) { fmt.Print(x, " ") }
最後に、構造体 Tree とメソッドを定義します。
リスト : 構造体 Tree とメソッドの定義
// 二分木
type Tree struct {
root *Node
}
// 二分木の生成
func newTree() *Tree {
return new(Tree)
}
// データの探索
func (t *Tree) searchTree(x Item) bool {
return searchNode(t.root, x)
}
// データの挿入
func (t *Tree) insertTree(x Item) {
t.root = insertNode(t.root, x)
}
// データの削除
func (t *Tree) deleteTree(x Item) {
t.root = deleteNode(t.root, x)
}
// 二分木の巡回
func (t *Tree) foreachTree(f func(Item)) {
foreachNode(f, t.root)
}
Tree のフィールド変数は root で、これが二分木の根 (ルート) になります。あとは、メソッドの処理に対応する関数を呼び出すだけです。
それでは実際に実行してみましょう。次に示す簡単なテストを行ってみました。
リスト : 簡単なテスト
// 表示
func (t *Tree) printTree() {
t.foreachTree(func(x Item) { fmt.Print(x, " ") })
fmt.Println("")
}
// インターフェースの実装
type Int int
func (n Int) Eq(m Item) bool {
return n == m.(Int)
}
func (n Int) Less(m Item) bool {
return n < m.(Int)
}
// 簡単なテスト
func main() {
a := newTree()
for _, v := range []int{5,6,4,7,3,8,2,9,1,0} {
a.insertTree(Int(v))
}
a.printTree()
for i := 0; i < 10; i++ {
fmt.Println(a.searchTree(Int(i)))
}
for i := 0; i < 10; i++ {
a.deleteTree(Int(i))
a.printTree()
}
}
実行結果を示します。
C<go run tree.go 0 1 2 3 4 5 6 7 8 9 true true true true true true true true true true 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
正常に動作していますね。
最後に、格納するデータの型が Item と int で実行時間にどれくらい違いがあるか試してみましょう。int 専用の二分探索木は、Item を int に、Eq を演算子 == に、Less を演算子 < に変更するだけです。詳細は プログラムリスト２ をお読みください。
乱数で 100 万個の整数を生成し、挿入、探索、削除の実行時間を計測します。テストプログラムは次のようになります。
リスト : 実行時間の計測
func main() {
a := newTree()
var b [1000000]int
for i := 0; i < len(b); i++ {
b[i] = rand.Int()
}
s := time.Now()
for _, x := range b {
a.insertTree(Int(x))
}
e := time.Now().Sub(s)
fmt.Println(e)
s = time.Now()
for _, x := range b {
a.searchTree(Int(x))
}
e = time.Now().Sub(s)
fmt.Println(e)
s = time.Now()
for _, x := range b {
a.deleteTree(Int(x))
}
e = time.Now().Sub(s)
fmt.Println(e)
}
実行結果を示します。
表 : 実行結果 (単位 : 秒)
| 挿入 | 探索 | 削除
-----+------+------+------
int | 0.67 | 0.36 | 0.47
Item | 1.46 | 1.19 | 1.23
実行環境 : Windows 7, Core i7-2670QM 2.20GHz
データの型が Item の場合、ポリモーフィズムと型アサーションが働くので、int に比べて実行時間が数倍遅くなるのはしかたがないところです。それでも、100 万個のデータを 1 秒ちょっとで処理できるのですから、Go 言語はやっぱり速いなあと改めて思いました。
//
// tree.go : 二分探索木
//
// Copyright (C) 2014 Makoto Hiroi
//
package main
import "fmt"
// 比較関数
type Item interface {
Eq(Item) bool
Less(Item) bool
}
// 節
type Node struct {
item Item
left, right *Node
}
// 節の生成
func newNode(x Item) *Node {
p := new(Node)
p.item = x
return p
}
// 二分木
type Tree struct {
root *Node
}
// 二分木の生成
func newTree() *Tree {
return new(Tree)
}
// データの探索
func searchNode(node *Node, x Item) bool {
for node != nil {
switch {
case x.Eq(node.item): return true
case x.Less(node.item): node = node.left
default: node = node.right
}
}
return false
}
func (t *Tree) searchTree(x Item) bool {
return searchNode(t.root, x)
}
// データの挿入
func insertNode(node *Node, x Item) *Node {
switch {
case node == nil: return newNode(x)
case x.Eq(node.item): return node
case x.Less(node.item):
node.left = insertNode(node.left, x)
default:
node.right = insertNode(node.right, x)
}
return node
}
func (t *Tree) insertTree(x Item) {
t.root = insertNode(t.root, x)
}
// 最小値を求める
func searchMin(node *Node) Item {
if node.left == nil {
return node.item
}
return searchMin(node.left)
}
// 最小値を削除する
func deleteMin(node *Node) *Node {
if node.left == nil {
return node.right
}
node.left = deleteMin(node.left)
return node
}
// 削除
func deleteNode(node *Node, x Item) *Node {
if node != nil {
if x.Eq(node.item) {
if node.left == nil {
return node.right
} else if node.right == nil {
return node.left
} else {
node.item = searchMin(node.right)
node.right = deleteMin(node.right)
}
} else if x.Less(node.item) {
node.left = deleteNode(node.left, x)
} else {
node.right = deleteNode(node.right, x)
}
}
return node
}
func (t *Tree) deleteTree(x Item) {
t.root = deleteNode(t.root, x)
}
// 巡回
func foreachNode(f func(Item), node *Node) {
if node != nil {
foreachNode(f, node.left)
f(node.item)
foreachNode(f, node.right)
}
}
func (t *Tree) foreachTree(f func(Item)) {
foreachNode(f, t.root)
}
// 表示
func (t *Tree) printTree() {
t.foreachTree(func(x Item) { fmt.Print(x, " ") })
fmt.Println("")
}
// インターフェースの実装
type Int int
func (n Int) Eq(m Item) bool {
return n == m.(Int)
}
func (n Int) Less(m Item) bool {
return n < m.(Int)
}
// 簡単なテスト
func main() {
a := newTree()
for _, v := range []int{5,6,4,7,3,8,2,9,1,0} {
a.insertTree(Int(v))
}
a.printTree()
for i := 0; i < 10; i++ {
fmt.Println(a.searchTree(Int(i)))
}
for i := 0; i < 10; i++ {
a.deleteTree(Int(i))
a.printTree()
}
}
//
// tree1.go : 二分探索木 (int 専用)
//
// Copyright (C) 2014 Makoto Hiroi
//
package main
import (
"fmt"
"math/rand"
"time"
)
// 節
type Node struct {
item int
left, right *Node
}
// 節の生成
func newNode(x int) *Node {
p := new(Node)
p.item = x
return p
}
// 二分木
type Tree struct {
root *Node
}
// 二分木の生成
func newTree() *Tree {
return new(Tree)
}
// データの探索
func searchNode(node *Node, x int) bool {
for node != nil {
switch {
case x == node.item: return true
case x < node.item: node = node.left
default: node = node.right
}
}
return false
}
func (t *Tree) searchTree(x int) bool {
return searchNode(t.root, x)
}
// データの挿入
func insertNode(node *Node, x int) *Node {
switch {
case node == nil: return newNode(x)
case x == node.item: return node
case x < node.item:
node.left = insertNode(node.left, x)
default:
node.right = insertNode(node.right, x)
}
return node
}
func (t *Tree) insertTree(x int) {
t.root = insertNode(t.root, x)
}
// 最小値を求める
func searchMin(node *Node) int {
if node.left == nil {
return node.item
}
return searchMin(node.left)
}
// 最小値を削除する
func deleteMin(node *Node) *Node {
if node.left == nil {
return node.right
}
node.left = deleteMin(node.left)
return node
}
// 削除
func deleteNode(node *Node, x int) *Node {
if node != nil {
if x == node.item {
if node.left == nil {
return node.right
} else if node.right == nil {
return node.left
} else {
node.item = searchMin(node.right)
node.right = deleteMin(node.right)
}
} else if x < node.item {
node.left = deleteNode(node.left, x)
} else {
node.right = deleteNode(node.right, x)
}
}
return node
}
func (t *Tree) deleteTree(x int) {
t.root = deleteNode(t.root, x)
}
// 巡回
func foreachNode(f func(int), node *Node) {
if node != nil {
foreachNode(f, node.left)
f(node.item)
foreachNode(f, node.right)
}
}
func (t *Tree) foreachTree(f func(int)) {
foreachNode(f, t.root)
}
// 表示
func (t *Tree) printTree() {
t.foreachTree(func(x int) { fmt.Print(x, " ") })
fmt.Println("")
}
// 簡単なテスト
func main() {
a := newTree()
var b [1000000]int
for i := 0; i < len(b); i++ {
b[i] = rand.Int()
}
s := time.Now()
for _, x := range b {
a.insertTree(x)
}
e := time.Now().Sub(s)
fmt.Println(e)
s = time.Now()
for _, x := range b {
a.searchTree(x)
}
e = time.Now().Sub(s)
fmt.Println(e)
s = time.Now()
for _, x := range b {
a.deleteTree(x)
}
e = time.Now().Sub(s)
fmt.Println(e)
}