今回はプログラムでよく用いられる「二分木 (binary tree)」というデータ構造を取り上げます。二分木は「木構造 (tree structer)」または「木 (tree)」と呼ばれるデータ構造の一種です。最初に木について簡単に説明します。
木は「節 (ノード, node)」と呼ばれる要素に対して、階層的な関係を表したものです。身近な例では、ディレクトリの階層構造が木にあたります。ディレクトリに「ルートディレクトリ」があるように、木にも「根 (ルート, root)」と呼ばれる節が存在します。下図を見てください。
(root)
Ａ ──────── レベル０
／｜＼ ↑
／ ｜ ＼
Ｂ Ｃ Ｄ 木 レベル１
／｜＼ ｜＼ の
／ ｜ ＼ ｜ ＼ 高
Ｅ Ｆ Ｇ Ｈ Ｉ さ レベル２
／ ＼
／ ＼ ↓
Ｊ Ｋ ───── レベル３
図 : 一般的な木構造の一例
木を図示する場合、階層関係がはっきりわかるように、根を上にして同じ階層にある節を並べて書きます。根からレベル 0、レベル 1 と階層を数えていき、最下層の節までの階層数を「木の高さ」といいます。木は、ある節から下の部分を切り出したものも、木としての性質を持っています。これを「部分木」といいます。
木は、ある節からほかの節に至る「経路」を考えることができます。たとえば、A から J には、A - B - G - J という経路がありますね。これは、ディレクトリやファイルを指定するときのパスと同じです。
ある節から根の方向にさかのぼるとき、途中で通っていく節を「先祖」といい、直接つながっている節を「親」といいます。これは、逆から見ると「子孫」と「子」という関係になります。子を持たない節をとくに「葉 (leaf)」と呼びます。上図でいうと、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 を見つけることができます。
二分木の探索は「Scheme プログラミング中級編 [1]」で説明した二分探索と同じ原理です。左右どちらかの子をたどるたびに、探索するデータ数は半分になります。上図の場合でも、探索するデータ数が 15, 7, 3, 1 となり、最後に見つけることができました。
データ数を N とすると、単純な線形探索では平均で N / 2 回の比較が必要になりますが、二分木を使うと log2 N 程度の回数で収まります。たとえばデータが 100個ある場合、線形探索では 50 回データを比較しなければいけないのに、二分探索木では 7 回程度の比較で済むわけです。また、データの挿入や削除も、log2 N 程度の比較回数で行うことができます。
ただし、これは左右の部分木のバランスがとれている理想的な状態での話です。バランスが崩れると二分木の性能は劣化し、最悪の場合は線形探索と同じになってしまいます。そこで、左右のバランスを一定の範囲に収める「平衡木 (balanced tree)」が考案されています。有名なところでは AVL 木、赤黒木、2-3 木、B 木、B* 木などがあります。なお、Gauche には平衡木を使った「ツリーマップ (tree-map)」というライブラリがあり、内部の実装には赤黒木が用いられています。
二分木のようなデータ構造を作る場合、R7RS-small の「レコード型 (record type)」を使うと便利です。レコード型は、ユーザーが既存のデータ型を組み合わせて、新しいデータ型を定義する機能です。Ｃ言語や Common Lisp にも「構造体」という同じような機能があります。
Ｃ言語の構造体はデータ型を定義するだけですが、Common Lisp の構造体や Scheme のレコード型はそれだけではなく、データを生成する関数 (コンストラクタ) やアクセス関数を自動的に生成します。
レコード型はシンタックス形式 define-record-type で定義します。
(define-record-type record-name
(constructor field_1 ... field_n)
pridecate
(field_1 reader_1 [writer_1])
・・・
(field_n reader_n [writer_n]))
図 : レコード型の定義
define-record-type の後ろにレコード名 record-name を指定します。次の節で、レコードを生成するコンストラクタ constructor とフィールド field_x を指定します。フィールドはレコード内にある変数のことで、Common Lisp の構造体ではスロット (slot)、Ｃ言語ではメンバ変数といいます。
次の節で、データ型を判定する述語の名前 predicate を指定します。それ以降の節で、フィールド field_x にアクセスする関数の名前 (リーダー reader_x とライター writer_x) を指定します。ライターは省略すると、そのフィールドは更新不可 (immutable) になります。なお、R7RS-small ではリーダーのことを「アクセサ (accessor)」、ライターのことを「モデファイア (modifier)」と記述しています。
レコードの生成はコンストラクタで行います。コンストラクタに渡す引数が各フィールドの初期値になります。リーダーはレコードを引数に受け取り、そのフィールドの値を返します。ライターはレコードとデータを引数に受け取り、そのフィールドの値をデータに書き換えます。
簡単な例を示しましょう。2 つの値を格納するレコード Pair を作ります。
gosh[r7rs.user]> (define-record-type Pair (make-pair fst snd) pair? (fst fst set-fst!) (snd snd set-snd!)) set-snd!
レコード Pair にはフィールド fst と snd があり、そこにデータを格納します。型述語は pair? で、fst のアクセス関数は fst, set-fst!、snd のアクセス関数は snd, set-snd! です。Scheme のレコード型は、フィールドとアクセス関数が同じ名前でもエラーにはならないようです。それでは実際に Pair を生成してみましょう。
gosh[r7rs.user]> (define a (make-pair 1 2)) a gosh[r7rs.user]> a #<Pair 0x7fb6782886c0> gosh[r7rs.user]> (pair? a) #t gosh[r7rs.user]> (pair? 1) #f gosh[r7rs.user]> (fst a) 1 gosh[r7rs.user]> (snd a) 2 gosh[r7rs.user]> (set-fst! a 10) #<undef> gosh[r7rs.user]> (fst a) 10 gosh[r7rs.user]> (set-snd! a 20) #<undef> gosh[r7rs.user]> (snd a) 20
fst, snd を car, cdr と考えれば、Pair の動作はコンスセルと同じになります。
それではプログラムを作りましょう。最初に節を定義します。次のリストを見てください。
リスト : 節の定義 (define-record-type Node (make-node item left right) node? (data data set-data!) (left left set-left!) (right right set-right!))
レコード名は Node としました。フィールド data にデータを、フィールド left に左部分木を、フィールド right に右部分木を格納します。子を持たない場合は、空リストをセットすることにします。節を箱で表すと下図のようになります。
ルートへの参照を変数 root に格納しておけば、この変数を使って二分木にアクセスすることができます。また、節が一つもない空の木は、変数 root に空リストをセットすれば表すことができます。なお、空リストのかわりに終端を表す節を用意する方法もあります。
変数 root
┌─┐
│ ┼──┐
└─┘ │
↓
┌─┬─┬─┐
│18│・│・│
└─┴┼┴┼┘
│ │
┌──────┘ └─┐
↓ ↓
┌─┬─┬─┐ ┌─┬─┬─┐
│14│／│／│ │22│／│／│
└─┴─┴─┘ └─┴─┴─┘
┌─┬─┬─┐
節：│Ｄ│Ｌ│Ｒ│
└─┴─┴─┘
Ｄ：data, Ｌ：left, Ｒ：right, ／：空リスト
図 : 二分木の構造
今回は二分木を表すレコード型 Tree を定義し、そこにルートを格納するフィールド root と、比較関数を格納するフィールド comp を用意します。(comp x y) は x < y ならば負の値、x = y ならば 0、x > y ならば正の値を返すものとします。二分木 (Tree) の操作は、節 (Node) を操作する関数を呼び出すことで行います。このとき、root と comp を節の操作関数に渡します。
それでは節の操作関数からプログラムしていきましょう。最初はデータを探索する関数 search-node を作ります。次のリストを見てください。
リスト : データの探索
(define (search-node node x comp)
(if (null? node)
#f
(let ((r (comp x (data node))))
(cond
((zero? r)
(data node))
((negative? r)
(search-node (left node) x comp))
(else
(search-node (right node) x comp))))))
関数 search-node には節 node、探索するデータ x、比較関数 comp を渡します。x と node に格納されているデータ (data node) を比較し、値が等しければ (data node) を返します。x が小さいのであれば左の子をたどり、そうでなければ右の子をたどります。たどるべき子がなくなれば node の値は空リストになるので #f を返します。二分探索木の動作をそのままプログラムしているだけなので、難しいところはないと思います。
次は、データを挿入する関数 insert-node! を作ります。この関数は木を引数として受け取り、データを挿入した新しい木を返します。フィールド変数 root の値を insert-node! の返り値で書き換えることで、二分木にデータを挿入することができます。この処理は再帰定義を使うと簡単にプログラムできます。次のリストを見てください。
リスト : データの挿入
(define (insert-node! node x comp)
(if (null? node)
(make-node x '() '())
(let ((r (comp x (data node))))
(cond
((zero? r) node)
((negative? r)
(set-left! node (insert-node! (left node) x comp))
node)
(else
(set-right! node (insert-node! (right node) x comp))
node)))))
最初に節 node が空リストかチェックします。そうであれば木は空なので、関数 make-node で新しい節を生成して返します。たとえば、フィールド変数 root が空リストの場合、すなわち空の木であれば、新しい節が生成されて root にセットされます。
そうでなければ、x と (data node) を比較します。x と等しいデータが見つかった場合は x を挿入する必要はないので、何も行わずに node を返します。x が小さい場合は、左部分木に x を挿入します。ここで関数 insert-node! を再帰呼び出しします。そして、その返り値を set-left! で左の子にセットして node を返します。
たとえば、左部分木が空リストの場合、再帰呼び出しの返り値は新しい節なので、それが左部分木にセットされ、木にデータが挿入されたことになります。そして、新しいデータが挿入された木 (node) を返せばいいわけです。x が (data node) よりも大きければ、同様に右部分木にデータを挿入します。
けっきょく、子を格納している節には、同じ子が再度セットされることになります。無駄なように思われるかもしれませんが、その分だけ簡単にプログラムを作ることができます。
次はデータを削除する処理を作りましょう。これは今までと違って少々面倒です。削除するデータが葉の場合は、それを削除するだけなので簡単です。ところが、木の途中のデータを削除する場合は、二分木の構成を崩さないように注意しないといけません。
最初に、葉を削除する場合を説明します。下図を見てください。
14 14
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 => 12 16
／ ＼ ／ ＼ ／ ＼ ／ ＼
11 13 15 17 11 13 () 17
↑
15 を削除する 削除
図 : データの削除 (葉の場合)
15 を削除する場合を考えてみましょう。15 は「葉」にあたるので、それを削除するだけで大丈夫です。親の左の子に空リストを代入するだけです。次に、子が一つある場合を考えてみましょう。
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 を格納していた節は削除します。節が最小値を格納している場合、その節の左側の子は存在しないので、その節を削除することは簡単です。
まず、木の中から最小値を探す関数と、最小値の節を削除する関数を作りましょう。次のリストを見てください。
リスト : 最小値の探索と削除
;;; 最小値の探索
(define (search-min-node node)
(if (null? (left node))
(data node)
(search-min-node (left node))))
;;; 最小値の削除
(define (delete-min-node! node)
(cond
((null? (left node))
(right node))
(else
(set-left! node (delete-min-node! (left node)))
node)))
二分木の場合、最小値は簡単に求めることができます。左の子を順番にたどっていき、左の子がない節に行き着いたとき、その節のデータが最小値になります。関数 search-min-node は、最初に (left node) の値をチェックします。もし、空リストであれば左の子がないので、その節のデータが最小値です。(data node) を返します。そうでなければ、search-min-node を再帰呼び出しして左の子をたどります。
関数 delete-min-node は最小値を格納している節を削除します。(left node) が空リストの節を探すのは search-min-node と同じです。見つけたら、もう一つの子 (right node) を返します。これで、親の左の子が書き換えられて、最小値を持つ節が削除されます。葉の場合であれば (right node) も空リストなので、単純に削除されることになります。
左の子があれば delete-min-node を再帰呼び出しして、その左部分木の中から最小値を探し出して削除します。そして、その返り値を左の子にセットして node を返します。
それでは、データを削除する関数 delete-node を作ります。削除するデータを探索して、見つけたら子の有無に合わせた削除処理を行います。
リスト : データの削除
(define (delete-node! node x comp)
(if (null? node)
node
(let ((r (comp x (data node))))
(cond
((zero? r)
(cond
((null? (left node)) (right node))
((null? (right node)) (left node))
(else
(set-data! node (search-min-node (right node)))
(set-right! node (delete-min-node! (right node)))
node)))
((negative? r)
(set-left! node (delete-node! (left node) x comp))
node)
(else
(set-right! node (delete-node! (right node) x comp))
node)))))
まず、node が空リストならば木は空なので、何もしないで node を返します。削除するデータが見つからない場合がこれに相当します。次に、削除するデータ x と (data node) を比較します。等しい場合はその節を削除します。(left node) が空リストの場合は (right node) を返し、(right node) が空リストの場合は (left node) を返します。
子が 2 つある場合は、右部分木の最小値を関数 search-min-node で求め、set-data! で値を書き換えます。そして、関数 delete-min-node で最小値を格納していた節を削除します。これで、削除するデータを最小値で置き換えて、不要になった節を二分木から削除することができます。
x と (data node) が等しくない場合は、左右の部分木をたどって削除するデータを探索します。この処理は関数 insert-node! と同じです。最後に node を返します。
最後に、二分木の全データにアクセスする関数を作りましょう。二分木はデータの大小関係を使って構成されているので、ある順番で節をすべて出力すると、それはソートした結果と同じになります。「木」のすべての節を規則的な順序で回ることを「巡回 (traverse)」といいいます。このなかで、次の 3 つの方法が重要です。
名前の由来は、節のデータを出力するタイミングからきています。節に最初に到達したときに出力する方法が「行きがけ」、子を出力してその節に戻ってきたときに出力する方法が「帰りがけ」、子を出力する途中でその節に戻ってきたときに出力する方法が「通りがけ」です。
二分木は「左の子 < 節のデータ < 右の子」という関係が成り立つので、通りがけ順に出力すれば、ソートされた出力結果を得ることができます。この処理も、再帰定義を使えば簡単に実現できます。次のリストを見てください。
リスト : 木の巡回 (define (for-each-node fn node) (when (node? node) (for-each-node fn (left node)) (fn (data node)) (for-each-node fn (right node))))
関数 for-each-node は高階関数で、通りがけ順で木を巡回して節のデータに関数 fn を適用します。node が空リストでなければ、再帰呼び出しで左部分木を巡回してから (fn (data node)) を評価し、そのあとで右部分木を巡回します。たとえば、(lambda (x) (display x) (newline)) を引数 func に与えれば、二分木のデータを昇順に表示することができます。
次は二分木を操作する関数を作ります。プログラムは次のようになります。
リスト : 二分木の操作関数
;;; 二分木
(define-record-type Tree
(create-tree root comp)
tree?
(root root set-root!)
(comp comp))
;;; 生成
(define (make-tree cmp) (create-tree '() cmp))
;;; 探索
(define (search-tree tree x)
(search-node (root tree) x (comp tree)))
(define (max-tree tree)
(if (null? (root tree))
#f
(search-max-node (root tree))))
(define (min-tree tree)
(if (null? (root tree))
#f
(search-min-node (root tree))))
;;; 挿入
(define (insert-tree! tree x)
(set-root! tree (insert-node! (root tree) x (comp tree))))
;;; 削除
(define (delete-tree! tree x)
(set-root! tree (delete-node! (root tree) x (comp tree))))
(define (delete-max-tree! tree)
(when
(node? (root tree))
(set-root! tree (delete-max-node! (root tree)))))
(define (delete-min-tree! tree)
(when
(node? (root tree))
(set-root! tree (delete-min-node! (root tree)))))
;;; 巡回
(define (for-each-tree fn tree)
(for-each-node fn (root tree)))
二分木はレコード型 Tree で表します。二分木の生成は make-tree で、探索は search-tree, min-tree, max-tree で、挿入は inset-tree! で、削除は delete-tree!, delete-min-tree!, delete-max-tree! で行います。木の巡回は for-each-tree で行います。それぞれ対応する節の操作関数を呼び出すだけです。
それでは実際に実行してみましょう。
リスト : 簡単なテスト (define a (make-tree (lambda (x y) (- x y)))) (for-each (lambda (x) (display "insert ") (display x) (newline) (insert-tree! a x) (print-tree a)) '(5 7 3 6 4 8 2 9 1 0)) (for-each (lambda (x) (display "search ") (display x) (display " ") (display (search-tree a x)) (newline)) '(-1 0 1 2 3 4 5 6 7 8 9 10)) (display "min: ") (display (min-tree a)) (newline) (display "max: ") (display (max-tree a)) (newline) (display "delete min") (newline) (delete-min-tree! a) (print-tree a) (display "delete max") (newline) (delete-max-tree! a) (print-tree a) (for-each (lambda (x) (display "delete ") (display x) (newline) (delete-tree! a x) (print-tree a)) '(0 1 2 3 4 5 6 7 8 9))
print-tree は木の形を表示する関数です。詳細はプログラムリストをお読みください。実行結果を示します。
$ gosh tree.scm
insert 5
5
insert 7
5
7
insert 3
3
5
7
insert 6
3
5
6
7
insert 4
3
4
5
6
7
insert 8
3
4
5
6
7
8
insert 2
2
3
4
5
6
7
8
insert 9
2
3
4
5
6
7
8
9
insert 1
1
2
3
4
5
6
7
8
9
insert 0
0
1
2
3
4
5
6
7
8
9
search -1 #f
search 0 0
search 1 1
search 2 2
search 3 3
search 4 4
search 5 5
search 6 6
search 7 7
search 8 8
search 9 9
search 10 #f
min: 0
max: 9
delete min
1
2
3
4
5
6
7
8
9
delete max
1
2
3
4
5
6
7
8
delete 0
1
2
3
4
5
6
7
8
delete 1
2
3
4
5
6
7
8
delete 2
3
4
5
6
7
8
delete 3
4
5
6
7
8
delete 4
5
6
7
8
delete 5
6
7
8
delete 6
7
8
delete 7
8
delete 8
delete 9
正常に動作していますね。興味のある方はいろいろ試してみてください。
;;;
;;; tree.scm : 二分木
;;;
;;; Copyright (C) 2020 Makoto Hiroi
;;;
(import (scheme base) (scheme write))
;;;
;;; 節
;;;
(define-record-type Node
(make-node data left right)
node?
(data data set-data!)
(left left set-left!)
(right right set-right!))
;;; データの探索
(define (search-node node x comp)
(if (null? node)
#f
(let ((r (comp x (data node))))
(cond
((zero? r)
(data node))
((negative? r)
(search-node (left node) x comp))
(else
(search-node (right node) x comp))))))
;;; データの挿入
(define (insert-node! node x comp)
(if (null? node)
(make-node x '() '())
(let ((r (comp x (data node))))
(cond
((zero? r) node)
((negative? r)
(set-left! node (insert-node! (left node) x comp))
node)
(else
(set-right! node (insert-node! (right node) x comp))
node)))))
;;; 最大値の探索
(define (search-max-node node)
(if (null? (right node))
(data node)
(search-max-node (right node))))
;;; 最大値の削除
(define (delete-max-node! node)
(cond
((null? (right node))
(left node))
(else
(set-right! node (delete-max-node! (right node)))
node)))
;;; 最小値の探索
(define (search-min-node node)
(if (null? (left node))
(data node)
(search-min-node (left node))))
;;; 最小値の削除
(define (delete-min-node! node)
(cond
((null? (left node))
(right node))
(else
(set-left! node (delete-min-node! (left node)))
node)))
;;; データの削除
(define (delete-node! node x comp)
(if (null? node)
node
(let ((r (comp x (data node))))
(cond
((zero? r)
(cond
((null? (left node))
(right node))
((null? (right node))
(left node))
(else
(set-data! node (search-min-node (right node)))
(set-right! node (delete-min-node! (right node)))
node)))
((negative? r)
(set-left! node (delete-node! (left node) x comp))
node)
(else
(set-right! node (delete-node! (right node) x comp))
node)))))
;;; 巡回
(define (for-each-node fn node)
(when
(node? node)
(for-each-node fn (left node))
(fn (data node))
(for-each-node fn (right node))))
;;;
;;; 二分木
;;;
(define-record-type Tree
(create-tree root comp)
tree?
(root root set-root!)
(comp comp))
;;; 生成
(define (make-tree cmp) (create-tree '() cmp))
;;; 探索
(define (search-tree tree x)
(search-node (root tree) x (comp tree)))
(define (max-tree tree)
(if (null? (root tree))
#f
(search-max-node (root tree))))
(define (min-tree tree)
(if (null? (root tree))
#f
(search-min-node (root tree))))
;;; 挿入
(define (insert-tree! tree x)
(set-root! tree (insert-node! (root tree) x (comp tree))))
;;; 削除
(define (delete-tree! tree x)
(set-root! tree (delete-node! (root tree) x (comp tree))))
(define (delete-max-tree! tree)
(when
(node? (root tree))
(set-root! tree (delete-max-node! (root tree)))))
(define (delete-min-tree! tree)
(when
(node? (root tree))
(set-root! tree (delete-min-node! (root tree)))))
;;; 巡回
(define (for-each-tree fn tree)
(for-each-node fn (root tree)))
;;; デバッグ用
(define (print-tree tree)
(define (print-space n)
(when
(positive? n)
(display " ")
(print-space (- n 1))))
(define (print-tree-node node n)
(when
(node? node)
(print-tree-node (left node) (+ n 1))
(print-space (* n 2))
(display (data node))
(newline)
(print-tree-node (right node) (+ n 1))))
;;
(print-tree-node (root tree) 0)
(newline))
;;; 簡単なテスト
(define a (make-tree (lambda (x y) (- x y))))
(for-each
(lambda (x)
(display "insert ") (display x) (newline)
(insert-tree! a x)
(print-tree a))
'(5 7 3 6 4 8 2 9 1 0))
(for-each
(lambda (x)
(display "search ") (display x) (display " ")
(display (search-tree a x)) (newline))
'(-1 0 1 2 3 4 5 6 7 8 9 10))
(display "min: ") (display (min-tree a)) (newline)
(display "max: ") (display (max-tree a)) (newline)
(display "delete min") (newline)
(delete-min-tree! a) (print-tree a)
(display "delete max") (newline)
(delete-max-tree! a) (print-tree a)
(for-each
(lambda (x)
(display "delete ") (display x) (newline)
(delete-tree! a x)
(print-tree a))
'(0 1 2 3 4 5 6 7 8 9))