Common Lisp Programming

二分探索木

今回は「二分探索木 (binary search tree)」という探索アルゴリズムを Common Lisp で実装してみましょう。

あるデータの中から特定のデータを探す場合、データ数が少なければ力任せに探索しても何とかなりますが、データ数が多くなると探索に時間がかかるようになります。このような場合、あらかじめデータを整理整頓しておくことで、特定のデータを高速に見つけることができるようになります。この代表的なアルゴリズムが「ハッシュ法」と「二分探索木」です。

Common Lisp にはハッシュ表が用意されているので、二分探索木を使う機会は少ないでしょう。ですが、二分探索木にはハッシュにはない特徴があります。格納されたデータをある順番で出力すると、それはソートした結果と同じになるのです。また、データの中から最大値や最小値を簡単に見つけることができます。データを見つけることだけならばハッシュの方が高速なのですが、データの大小関係が絡む処理には、二分探索木の方が適しています。

●木構造とは？

二分木 (binary tree) は「木構造 (tree structer)」または「木 (tree)」と呼ばれるデータ構造の一つです。木は節 (ノード) と呼ばれる要素に対して、階層的な関係を表したものです。身近な例では、ディレクトリの階層構造が木にあたります。ディレクトリに「ルートディレクトリ」があるように、木にも「根 (ルート)」と呼ばれる節が存在します。下図を見てください。

          図 : 一般的な木構造の一例

木を図示する場合、階層関係がはっきりわかるように、根を上にして、同じ階層にある節を並べて書きます。根からレベル 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 を見つけることができます。

二分探索木の探索は「二分探索」と同じ原理です。左右どちらかの子をたどるたびに、探索するデータ数は半分になります。上図の場合でも、探索するデータ数が 15, 7, 3, 1 となり、最後に見つけることができました。

データ数を n とすると、単純な線形探索では平均で n / 2 回の比較が必要になりますが、二分探索木を使うと log₂ n 程度の回数で収まります。たとえば、データが 100個ある場合、線形探索では 50 回データを比較しなければいけないのに、二分探索木では 7 回程度の比較で済むわけです。

ただし、これは左右の部分木のバランスがとれている理想的な状態での話です。バランスが崩れると二分探索木の性能は劣化し、最悪の場合は線形探索と同じになってしまいます。そこで、左右のバランスを一定の範囲に収める「平衡木 (balanced tree)」が考案されています。有名なところでは AVL 木、2 色木 (赤黒木)、2-3 木、B 木、B* 木などがあります。

●節の定義

それではプログラムを作りましょう。今回はプログラムを簡単にするため、格納するデータを数値に限定します。データ型のチェックは省略するので、数値以外のデータは扱わないようにしてください。

まず最初に、節を表すクラスを定義します。

リスト : 節の定義

(defstruct node data left right)

スロット DATA にデータを格納し、LEFT は左側の子、RIGHT は右側の子を格納します。スロット LEFT からデータを取り出せば、左側の節へ移動することができ、RIGHT からデータを取り出せば、右側の節へ移動することができます。子がない場合、LEFT と RIGHT には NIL をセットすることにします。節を箱で表すと下図のようになります。

             図 : 二分木の構造

ルートへの参照を変数 root に格納しておけば、この変数を使って二分木にアクセスすることができます。また、節が一つもない空の木は、変数 root に NIL をセットすれば表すことができます。なお、NIL のかわりに終端を表す節を用意する方法もあります。

今回はルートを格納する構造体 binary-tree を定義して、それで二分木を表すことにします。二分木の操作は関数 xxxx-tree で行いますが、実際の処理は節を操作する関数 xxxx-node が担当します。

●データの探索

それでは、データを探索する関数 search-node から作りましょう。次のリストを見てください。

リスト : データの探索

(defun search-node (node x)
  (cond
   ((null node) nil)
   ((= (node-data node) x) t)
   ((< x (node-data node))
    (search-node (node-left node) x))
   (t
    (search-node (node-right node) x))))

関数 search-node には節 NODE と探索するデータ X を渡します。NODE に格納されている DATA と X を比較し、値が等しければ T を返します。X が小さいのであれば左の子をたどり、そうでなければ右の子をたどります。たどるべき木がなくなれば NODE の値は NIL になります。この場合、X は見つからなかったので NIL を返します。二分探索木の動作をそのままプログラムしているだけなので、難しいところはないと思います。

●データの挿入

次は、データを挿入する関数 insert-node を作ります。この関数は木を引数として受け取り、データを挿入した新しい木を返します。たとえば、変数 root に木が格納されている場合、データを挿入するときは次のように呼び出します。

(setq root (insert-node root x))

この処理は再帰定義を使うと簡単にプログラムできます。次のリストを見てください。

リスト : データの挿入

(defun insert-node (node x)
  (cond
   ((null node) (make-node :data x))
   ((= (node-data node) x) node)
   ((< x (node-data node))
    (setf (node-left node)
          (insert-node (node-left node) x))
    node)
   (t
    (setf (node-right node)
          (insert-node (node-right node) x))
    node)))

最初に節 NODE が NIL かチェックします。そうであれば木は空なので、新しい節を make-node で生成して返します。たとえば、変数 ROOT が NIL (空の木) の場合、新しい節が生成されて ROOT にセットされます。

そうでなければ、X とスロット DATA を比較します。X と等しいデータが見つかった場合は、新しいデータを挿入する必要はないので、何も行わずに NODE を返します。X が小さい場合は、左部分木に X を挿入します。ここで関数 insert-node を再帰呼び出しします。そして、その返り値をスロット LEFT にセットして NODE を返します。

LEFT が NIL の場合、再帰呼び出しの返り値は新しい節なので、それが LEFT にセットされ、木にデータが挿入されたことになります。そして、新しいデータが挿入された木 (NODE) を返せばいいわけです。X が DATA よりも大きければ、同様に右部分木にデータを挿入します。

けっきょく、子を格納している節には、同じ子が再度セットされることになります。無駄なように思われるかもしれませんが、その分だけ簡単にプログラムを作ることができます。

●データの削除

次はデータを削除する処理を作りましょう。これは今までと違って少々面倒です。削除するデータが「葉」の場合は、それを削除するだけなので簡単ですが、木の途中のデータを削除する場合は、二分木の構成を崩さないように注意しないといけません。最初に、葉を削除する場合を説明します。下図を見てください。

               図 : データの削除 (葉の場合)

15 を削除する場合を考えてみましょう。15 は「葉」にあたるので、それを削除するだけで大丈夫です。親の LEFT に NIL を代入するだけです。

次に、子が一つある場合を考えてみましょう。

            図 : データの削除 (子が一つの場合)

16 を削除する場合、その子である 15 と置き換えれば二分探索木の構成は保たれます。これも簡単ですね。問題は、子が二つある節を削除する場合です。

            図 : データの削除 (子が二つの場合)

この場合、削除するデータの右部分木の中から最小値のデータ ^[*1] を探し、それと削除するデータと置き換えれば「右部分木 < 節 < 左部分木」の構成を崩さなくてすみます。上図で、14 を削除することを考えてみましょう。右部分木の中で 15 が最小値なので、それと 14 を置き換えます。そして、15 を格納していた節は削除します。節が最小値を格納している場合、その節の左側の子は存在しないので、その節を削除することは簡単です。

まず、木の中から最小値を探す関数と、最小値の節を削除する関数を作成しましょう。次のリストを見てください。

リスト : 最小値の探索と削除

;;; 最小値の探索
(defun search-min-node (node)
  (if (null (node-left node))
      (node-data node)
    (search-min-node (node-left node))))

;;; 最小値の削除
(defun delete-min-node (node)
  (cond
   ((null (node-left node))
    (node-right node))
   (t
    (setf (node-left node)
          (delete-min-node (node-left node)))
    node)))

最小値は簡単に求めることができます。左の子を順番にたどっていき、左の子がない節に行き着いたとき、その節のデータが最小値になります。関数 search-min-node は最小値を求めてそれを返します。最初に、LEFT の値をチェックします。もし、NIL であれば左の子がないので、その節の DATA が最小値です。そうでなければ、search-min-node を再帰呼び出しして左の子をたどります。

関数 delete-min-node は最小値を格納している節を削除します。LEFT が NIL の節を探すのは search-min-node と同じです。見つけたら、もう一つの子 RIGHT を返します。これで、親の左部分木が書き換えられ、最小値を持つ節が削除されます。葉であれば RIGHT は NIL なので、単純に削除されることになります。

左の子があれば delete-min-node を再帰呼び出しして、その左部分木の中から最小値を探し出して削除します。そして、その返り値を LEFT にセットして NODE を返します。

それでは、データを削除する関数 delete-node を作ります。削除するデータを探索して、見つけたら子の有無に合わせた削除処理を行います。

リスト : データの削除

(defun delete-node (node x)
  (when node
    (cond
     ((= (node-data node) x)
      (cond
       ((null (node-left node))
        (node-right node))
       ((null (node-right node))
        (node-left node))
       (t
        (setf (node-data node)
              (search-min-node (node-right node))
              (node-right node)
              (delete-min-node (node-right node)))
        node)))
     ((< x (node-data node))
      (setf (node-left node)
            (delete-node (node-left node) x))
      node)
     (t
      (setf (node-right node)
            (delete-node (node-right node) x))
      node))))

まず、NODE が NIL ならば木は空なので、何もしないで NIL を返します。削除するデータが見つからない場合や空の木を与えた場合がこれに相当します。次に、削除するデータ X と DATA を比較します。等しい場合はその節を削除します。LEFT が NIL の場合は RIGHT を返し、RIGHT が NIL の場合は LEFT を返します。

子が 2 つある場合は、右部分木の最小値を関数 search-min-node で求め、DATA の値を書き換えます。そして、関数 delete-min-node で最小値を格納していた節を削除します。これで、削除するデータを最小値で置き換え、不要になった節を二分木から削除することができます。

X と DATA が等しくない場合は、左右の部分木をたどって削除するデータを探索します。この処理は今までと同じです。

●巡回 (traverse)

次は、二分木の全データにアクセスする関数を作りましょう。二分木はデータの大小関係を使って構成されているので、ある順番で節をすべて出力すると、それはソートした結果と同じになります。「木」のすべての節を規則的な順序で回ることを「巡回 (traverse)」といいいます。このなかで、次の 3 つの方法が重要です。

1. 行きがけ順
   まず節のデータを出力、その後左の子、右の子の順番で出力する。
2. 帰りがけ順
   左の子、右の子と出力してから、節のデータを出力する。
3. 通りがけ順
   左の子を出力、次に節のデータを出力、最後に右の子を出力する。

名前の由来は、節のデータを出力するタイミングからきています。節に最初に到達したときに出力する方法が「行きがけ」、子を出力してその節に戻ってきたときに出力する方法が「帰りがけ」、子を出力する途中でその節に戻ってきたときに出力する方法が「通りがけ」です。

二分木は「左の子 < 節のデータ < 右の子」という関係が成り立つので、通りがけ順に出力すれば、ソートされた出力結果を得ることができます。この処理も、再帰定義を使えば簡単に実現できます。次のリストを見てください。

リスト : 木の巡回

(defun traverse-node (func node)
  (when node
    (traverse-node func (node-left node))
    (funcall func (node-data node))
    (traverse-node func (node-right node))))

関数 traverse-node は高階関数で、通りがけ順で木を巡回し、データに関数 FUNC を適用します。NODE が NIL でなければ、再帰呼び出しで左部分木を巡回してから FUNC を実行し、そのあとで右部分木を巡回します。たとえば、データを出力する関数 #'print を引数 FUNC に与えれば、二分木のデータを昇順に表示することができます。

●binary-tree の作成

最後に、二分木を表す構造体 binary-tree とその操作関数を作ります。

リスト : 二分木

;;; 木の定義
(defstruct binary-tree root)

;;; 探索
(defun search-binary-tree (tree x)
  (search-node (binary-tree-root tree) x))

;;; 最大値を求める
(defun search-max-binary-tree (tree)
  (when (binary-tree-root tree)
    (search-max-node (binary-tree-root tree))))

;;; 最小値を求める
(defun search-min-binary-tree (tree)
  (when (binary-tree-root tree)
    (search-min-node (binary-tree-root tree))))

;;; 挿入
(defun insert-binary-tree (tree x)
  (setf (binary-tree-root tree)
        (insert-node (binary-tree-root tree) x)))

;;; 削除
(defun delete-binary-tree (tree x)
  (setf (binary-tree-root tree)
        (delete-node (binary-tree-root tree) x)))

;;; 最大値を削除
(defun delete-max-binary-tree (tree)
  (when (binary-tree-root tree)
    (setf (binary-tree-root tree)
          (delete-max-node (binary-tree-root tree)))))

;;; 最小値を削除
(defun delete-min-binary-tree (tree)
  (when (binary-tree-root tree)
    (setf (binary-tree-root tree)
          (delete-min-node (binary-tree-root tree)))))

;;; 巡回
(defun traverse-binary-tree (func tree)
  (traverse-node func (binary-tree-root tree)))

;;; 表示
(defun print-binary-tree (tree)
  (traverse-node (lambda (x) (format t "~d " x)) (binary-tree-root tree))
  (terpri))

binary-tree のスロットは ROOT で、これが二分木の根 (ルート) になります。あとは、処理に対応する関数を呼び出すだけです。

●実行例

それでは実際に実行してみましょう。次に示す簡単なテストを行ってみました。

リスト : 簡単なテスト

;;; 乱数データの生成
(defun make-random-data (n)
  (let (buff)
    (dotimes (i n buff)
      (push (random 10000) buff))))

;;; テスト
(defun test ()
  (let ((tree (make-binary-tree))
        (data (make-random-data 10)))
    (dolist (x data)
      (format t "insert ~4D : " x)
      (insert-binary-tree tree x)
      (print-binary-tree tree))
    (dolist (x data)
      (format t "~4D => ~A~%" x (search-binary-tree tree x))
      (format t "~4D => ~A~%" (1+ x) (search-binary-tree tree (1+ x))))
    (format t "max = ~D~%" (search-max-binary-tree tree))
    (format t "min = ~D~%" (search-min-binary-tree tree))
    (format t "delete max : ")
    (delete-max-binary-tree tree)
    (print-binary-tree tree)
    (format t "delete min : ")
    (delete-min-binary-tree tree)
    (print-binary-tree tree)
    (dolist (x data)
      (delete-binary-tree tree x)
      (format t "delete ~4D : " x)
      (print-binary-tree tree))))

実行結果を示します。

* (test)
insert 2055 : 2055
insert 9390 : 2055 9390
insert 3121 : 2055 3121 9390
insert 7995 : 2055 3121 7995 9390
insert 5144 : 2055 3121 5144 7995 9390
insert 9810 : 2055 3121 5144 7995 9390 9810
insert 9386 : 2055 3121 5144 7995 9386 9390 9810
insert  311 : 311 2055 3121 5144 7995 9386 9390 9810
insert 1203 : 311 1203 2055 3121 5144 7995 9386 9390 9810
insert 5393 : 311 1203 2055 3121 5144 5393 7995 9386 9390 9810
2055 => T
2056 => NIL
9390 => T
9391 => NIL
3121 => T
3122 => NIL
7995 => T
7996 => NIL
5144 => T
5145 => NIL
9810 => T
9811 => NIL
9386 => T
9387 => NIL
 311 => T
 312 => NIL
1203 => T
1204 => NIL
5393 => T
5394 => NIL
max = 9810
min = 311
delete max : 311 1203 2055 3121 5144 5393 7995 9386 9390
delete min : 1203 2055 3121 5144 5393 7995 9386 9390
delete 2055 : 1203 3121 5144 5393 7995 9386 9390
delete 9390 : 1203 3121 5144 5393 7995 9386
delete 3121 : 1203 5144 5393 7995 9386
delete 7995 : 1203 5144 5393 9386
delete 5144 : 1203 5393 9386
delete 9810 : 1203 5393 9386
delete 9386 : 1203 5393
delete  311 : 1203 5393
delete 1203 : 5393
delete 5393 :
NIL

正常に動作しているようです。興味のある方はいろいろ試してみてください。

●プログラムリスト

;;;
;;; binarytree.lisp : 二分探索木
;;;
;;;                   Copyright (C) 2020 Makoto Hiroi
;;;

;;; 節
(defstruct node data left right)

;;; 探索
(defun search-node (node x)
  (cond
   ((null node) nil)
   ((= (node-data node) x) t)
   ((< x (node-data node))
    (search-node (node-left node) x))
   (t
    (search-node (node-right node) x))))

;;; 挿入
(defun insert-node (node x)
  (cond
   ((null node) (make-node :data x))
   ((= (node-data node) x) node)
   ((< x (node-data node))
    (setf (node-left node)
          (insert-node (node-left node) x))
    node)
   (t
    (setf (node-right node)
          (insert-node (node-right node) x))
    node)))

;;; 最小値の探索
(defun search-min-node (node)
  (if (null (node-left node))
      (node-data node)
    (search-min-node (node-left node))))

;;; 最小値の削除
(defun delete-min-node (node)
  (cond
   ((null (node-left node))
    (node-right node))
   (t
    (setf (node-left node)
          (delete-min-node (node-left node)))
    node)))

;;; 最大値の探索
(defun search-max-node (node)
  (if (null (node-right node))
      (node-data node)
    (search-max-node (node-right node))))

;;; 最大値の削除
(defun delete-max-node (node)
  (cond
   ((null (node-right node))
    (node-left node))
   (t
    (setf (node-right node)
          (delete-max-node (node-right node)))
    node)))

;;; 削除
(defun delete-node (node x)
  (when node
    (cond
     ((= (node-data node) x)
      (cond
       ((null (node-left node))
        (node-right node))
       ((null (node-right node))
        (node-left node))
       (t
        (setf (node-data node)
              (search-min-node (node-right node))
              (node-right node)
              (delete-min-node (node-right node)))
        node)))
     ((< x (node-data node))
      (setf (node-left node)
            (delete-node (node-left node) x))
      node)
     (t
      (setf (node-right node)
            (delete-node (node-right node) x))
      node))))

;;; 巡回
(defun traverse-node (func node)
  (when node
    (traverse-node func (node-left node))
    (funcall func (node-data node))
    (traverse-node func (node-right node))))

;;; 木の定義
(defstruct binary-tree root)

;;; 探索
(defun search-binary-tree (tree x)
  (search-node (binary-tree-root tree) x))

(defun search-max-binary-tree (tree)
  (when (binary-tree-root tree)
    (search-max-node (binary-tree-root tree))))

(defun search-min-binary-tree (tree)
  (when (binary-tree-root tree)
    (search-min-node (binary-tree-root tree))))

;;; 挿入
(defun insert-binary-tree (tree x)
  (setf (binary-tree-root tree)
        (insert-node (binary-tree-root tree) x)))

;;; 削除
(defun delete-binary-tree (tree x)
  (setf (binary-tree-root tree)
        (delete-node (binary-tree-root tree) x)))

(defun delete-max-binary-tree (tree)
  (when (binary-tree-root tree)
    (setf (binary-tree-root tree)
          (delete-max-node (binary-tree-root tree)))))

(defun delete-min-binary-tree (tree)
  (when (binary-tree-root tree)
    (setf (binary-tree-root tree)
          (delete-min-node (binary-tree-root tree)))))

;;; 巡回
(defun traverse-binary-tree (func tree)
  (traverse-node func (binary-tree-root tree)))

;;; 表示
(defun print-binary-tree (tree)
  (traverse-node (lambda (x) (format t "~d " x)) (binary-tree-root tree))
  (terpri))

;;; 乱数データの作成
(defun make-random-data (n)
  (let (buff)
    (dotimes (i n buff)
      (push (random 10000) buff))))

;;; テスト
(defun test ()
  (let ((tree (make-binary-tree))
        (data (make-random-data 10)))
    (dolist (x data)
      (format t "insert ~4D : " x)
      (insert-binary-tree tree x)
      (print-binary-tree tree))
    (dolist (x data)
      (format t "~4D => ~A~%" x (search-binary-tree tree x))
      (format t "~4D => ~A~%" (1+ x) (search-binary-tree tree (1+ x))))
    (format t "max = ~D~%" (search-max-binary-tree tree))
    (format t "min = ~D~%" (search-min-binary-tree tree))
    (format t "delete max : ")
    (delete-max-binary-tree tree)
    (print-binary-tree tree)
    (format t "delete min : ")
    (delete-min-binary-tree tree)
    (print-binary-tree tree)
    (dolist (x data)
      (delete-binary-tree tree x)
      (format t "delete ~4D : " x)
      (print-binary-tree tree))))