二分探索木

説明

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

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

配列[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を使って作成しました。