二分探索木

説明

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

ソート済みのデータを表現したいとき、配列はあまり良いデータ構造とは言えません。

たとえば、[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

ヒント

この演習を完了するには、EqとShowのインスタンスを持つデータ型BSTを作成し、次の関数を実装する必要があります。

• bstLeft
• bstRight
• bstValue
• empty
• fromList
• insert
• singleton
• toList

ダミーのデータ宣言と型シグネチャはすでに用意されていますが、関数を定義し、意味のあるデータ型やnewtype、型シノニムを作成するのは自分で行う必要があります。