二分探索木

説明

二分木に数値を挿入し、検索します。

ソートされたデータを表すとき、配列は適したデータ構造とは言えません。

配列[1, 3, 4, 5]があって、そこに2を追加して[1, 3, 4, 5, 2]になったとします。すると、配列全体をもう一度ソートし直さなければなりません！　新しい要素のために場所をひとつ空けて[1, nil, 3, 4, 5]とし、空けた場所に要素を追加すればよいと考えれば、これは改善できます。しかし、それでも多くの要素をひとつ後ろにずらす必要があります。

しかし、二分探索木なら、ソートされたデータをはるかに効率よく扱えます。

二分探索木は、つながったノードの連なりからできています。各ノードは、1つのデータ（たとえば数値の3）、leftという名前の変数、そしてrightという名前の変数を保持します。leftとrightの変数は、nilか、別のノードを指します。それらのノードの下にはさらにノードが続くので、leftとrightの変数は部分木を指していると言います。左の部分木のデータはすべて現在のノードのデータ以下で、右の部分木のデータはすべて現在のノードのデータより大きくなっています。

たとえば、データ4を持つノードに、データ2を追加すると、木は次のようになります。

      4
     /
    2

さらに6を追加すると、次のようになります。

      4
     / \
    2   6

さらに3を追加すると、次のようになります。

       4
     /   \
    2     6
     \
      3

そしてさらに1、5、7を追加すると、次のようになります。

          4
        /   \
       /     \
      2       6
     / \     / \
    1   3   5   7

クレジット

画像はhabere-et-dispertireが、Till TantauによるPGF/TikZを使って作成しました。

実装

Cairo（あるいは、イミュータブルなメモリを持つ純粋関数型言語）で、効率的で変更可能な木構造を実装するのは難しい作業です。これらの言語は、一度作成したデータを変更しないように設計されているからです。 このイミュータブルという性質のため、木のノードを直接更新するのではなく、変更するたびに木の新しいバージョンを作成する必要があります。

なぜそうなるのかを見るために、各ノードが左と右の子を持つシンプルな二分木構造を想像してみましょう。 次のような小さな木から始めるとします。

       1
      / \
     2   3

ここで、ノード2の左の子として新しいノード4を追加したいとします。 純粋関数型言語（CairoやHaskellなど）ではメモリはイミュータブルなので、ノード4を2に直接追加するわけにはいきません。 代わりに、根から変更するノードまでの経路上にある各ノードの新しいバージョンを作成する必要があります。その経路上のノードはすべて、新しい、あるいは変更された部分木を指すようになるからです。

処理の流れは次のようになります。

1. ノード4をノード2に追加する:

   • ノード2の新しいバージョンを作成します。このノードは4を左の子として持ちます。

       2'
      / 
     4   
   

2. 根のノードを更新する:

   • ノード1はもともと古い2を指していたので、根のノードの新しいバージョン1'を作成します。これは、左側で更新されたノード2'を指し、右側ではノード3を保ちます。

       1'
      / \
     2'  3
   

すると、できあがる木は次のようになります。

       1'
      / \
     2'  3
    /
   4

この新しい木（1'）は元の木とよく似ていますが、経路が更新されています。 重要なのは、イミュータブルを保つために、経路上の各ノード（1から2）を作り直す必要があったという点です。既存のノードはその場で変更できないからです。 元の木はそのまま残っています（たとえば、元の根1を参照しているすべてのものにとって）。一方、この新しい木が変更後の状態を表しています。

大きな木では、この方法はコストが高くなる可能性があります。実際に変更されるのが木のごく一部であっても、変更のたびに、根から更新されたノードまでの経路のノードを作り直す必要があるからです。