二分探索木

説明

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

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

たとえば、配列[1, 3, 4, 5]があり、そこに2を追加して[1, 3, 4, 5, 2]になったとします。 すると、配列全体をまた並べ替えなければなりません！ 新しい要素のために場所を空けて[1, nil, 3, 4, 5]とし、空けた場所にその要素を追加すればよいと気づけば、これを改善できます。 しかし、それでも多くの要素を1つずつずらす必要があります。

一方、二分探索木はソートされたデータをはるかに効率よく扱うことができます。

二分探索木は、つながったノードの集まりでできています。 各ノードは、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を使って作成しました。