f# - ソートされた二分木 F#

Question

こんにちは、F# でソートされたバイナリ ツリー データ型を作成する方法についての良い情報を探していましたが、理解できるものは見つかりませんでした。msdn-page で例を確認しましたが、わかりません。

Answer 1

既存の実装を探している場合、FSharpXライブラリにはかなりの数のデータ構造（いくつかのツリーを含む）があります。ソートされた二分木の簡単な実装はないと思いますが。F＃からすべての.NETコレクションにアクセスすることもできますが、.NETにもバイナリツリーがあるとは思いません。それはあなたが何をしようとしているのかによってはあなたにとってちょうど良いかもしれないソートされたリストを持っています。

独自に実装する場合は、ツリーを表すデータ型を定義することから始める必要があります。

type SortedTree<'T when 'T : comparison> =
  | Node of SortedTree<'T> * 'T * SortedTree<'T>
  | Leaf of 'T

このNode要素は、左側のすべての値がノードに格納されている値よりも小さく、大きい（または等しい）値がすべて右側にあることを意味します。'T : comparison比較可能な要素のツリーのみを作成できることを意味する制約を追加しました（これは、ツリーをソートするための実装で必要です）。

すべての一般的なツリー操作を実装することは非常に多くの作業になりますが、挿入の単純な試み（ツリーのバランスを維持しない）は次のようになります。

let rec insert element tree = 
  match tree with
  | Leaf v when element < v -> Node(Leaf element, v, Leaf v)
  | Leaf v -> Node(Leaf v, element, Leaf element)
  | Node(left, key, right) when element < key -> Node(insert element left, key, right)
  | Node(left, key, right) -> Node(left, key, insert element right)

パターンマッチングは、4つの興味深いケースを処理します。ツリーがLeafの場合、左側または右側のいずれかに新しい要素を使用して新しいノードを構築する必要があります。ツリーがの場合Node、キーの値に応じて、左または右に挿入します。