２分探索木

各ノードに値をもち、 その値が左の子ノードの値以上で、 右の子ノードの値以下であるような２分木を、２分探索木 binary search tree といいます。

値の等しいノードを許さない、許す場合左右どちらに追加するかなどバリエーションがあります。

ここでは、２分探索木の検索・挿入・削除のアルゴリズムを紹介します。 走査については、２分木の走査を参照してください。 ２分探索木を通りがかり順に歩くと、ノードの値を昇順に取り出すことができます。 ２分探索木の順序を保持したまま、木のバランスを変えるローテーションについては、 木のローテーションを参照してください。

その他の関連項目

木
赤黒木

２分探索木についてはＷｅｂサイトでも数多く紹介されています。 木については WIKIPEDIA にかなり丁寧な解説があります。 ２分探索木についても Binary search tree を参考にしました。

以下の解説では、 等しい要素を許すような２分探索木を扱います。 等しい要素は右部分木に挿入します。

実際のプログラムは J2SE 5.0 で作成してみました。 ノードの値をジェネリック（Comparable を実装した Object）にしましたので、 J2SE 1.4 ではコンパイル・エラーになります。 J2SE 1.4 用に Object に書き直してみました。 行数は変わりませんので、都合のよいほうを参照してください。

(1)BinaryTree.java (J2SE 5.0)
(2)BinaryTree.java (J2SE 1.4)

(3)(1) の行番号付きリスト
赤字の部分が差異部分です。
同じ名前ですが、別のプログラムですので注意してください。

木のノードには、

を保持することにします。 (BinaryTree.java 11〜14 行目)

NIL は値が「ない」状態 (Null In List) を示す「もの」です。 Ｊａｖａの null または定数で実装するのが普通ですが、 NIL を他の部分木で置き換える処理の記述が簡略になるように、 値が null であるようなノードを使います。 通常の NIL と振る舞いが異なるのは、 NIL どうしの比較をするといつも「等しくない」点です。

検索アルゴリズム

２分索木 t にある値 v を検索するには、
  1. t が NIL であれば、「見つからない」（終り）
  2. v が t の値より小さければ、左部分木を検索する
  3. v が t の値より大きければ、右部分木を検索する
  4. 「見つかった」（終り）
見つかった場合は、根の値が v である部分木を返し、 見つからなかった場合は NIL を返すことにします。
さらに等しい値を探す場合は、「見つかった」部分木の右部分木を検索すればよいことになります。

(BinaryTree.java 152〜157 行目)

挿入アルゴリズム

２分探索木 t に値 v を挿入するには、
  1. t が NIL であれば、v を値とするノード(v,NIL,NIL)を作成し t と置き換える
  2. v が t の値より小さければ、左部分木に挿入する
  3. v が t の値以上ならば、右部分木に挿入する
検索アルゴリズムを利用する場合は、 (BinaryTree.java 165〜173 行目)
  1. v を検索する
  2. 見つからなかった場合は、その場所にあった NIL を (v,NIL,NIL) で置き換える
  3. 見つかった場合は、右部分木に挿入する

削除アルゴリズム

２分探索木 t から値 v を削除するには、 (BinaryTree.java 181〜209 行目)
  1. v を検索する
  2. 返された部分木が NIL ならば、「みつからない」（終）
  3. 返された部分木を t として、
    1. t に子がなければ t を NIL に置き換える（終）
    2. t に子が１つしかなければ、t をその子で置き換える（終）
    3. t の値より小さい値のうちの最大値をさがし、t の値を置き換える
    4. その最大値のあったノードに子がなければ、そのノードを NIL に置き換える（終）
    5. その最大値のあったノードに左部分木があれば、そのノードをその左部分木で置き換える（終）
    6. （終）右部分木はない
binary-tree-4.gif 上記 4-3. の 「 より小さい値のうちの最大値 」は 「 に等しいか大きい値のうちの最小値 」 でもかまいません。 その場合は、4-5. の 「左部分木」を「右部分木」に、 4-6. の 「右部分木」を「左部分木」に読み替えます。

「より小さい値のうちの最大値」の見つけ方
t の左の子から始めて、右の子がある限りたどる

「に等しいか大きい値のうちの最小値」の見つけ方
t の右の子から始めて、左の子がある限りたどる

動作確認テスト

tree-2a.gif JUnit をつかって J2SE 5.0版の動作確認をします。

左図のような２分探索木と空木についての動作確認です。

JUniit については、 テスティングフレームワーク JUnit を参考にしました。

テスト・プログラム BinaryTreeTester.java

コンパイルと実行

binary-tree-6.gif

実行結果

binary-tree-7.gif

Top Page
更新日：2005-10-15