Btreeを雑に書く

これは何？

OCamlで Btree実装やってみた（やってみた系記事）。

なんで書こうと思ったか

下記の記事でGo言語によるbtreeの実装があり、おぉ！と思ったのとOCamlで実装したら確か楽に実装できたな、と思ったので。
https://qiita.com/Tommy_/items/6af8f820a3a692e5cde3

Btreeとは

この記事にまとまっているので、見てね（上と同じ記事やが）
https://qiita.com/Tommy_/items/6af8f820a3a692e5cde3

注意

ポエムなので雑に書く。
今後、このようなクソ記事を表示させたくない皆さまに置かれましては、
検索キーワードで "やってみた" を除外すると幸せになれる。

一般的？なbtree実装

type 'a bt = Empty | Node of 'a * 'a bt * 'a bt
let rec member x bt = 
  match bt with
  | Empty -> false
  | Node (y, left, right) ->
    if x = y then true
    else if x < y then member x left else member x right
let rec insert x bt =
  match bt with
    | Empty -> Node(x, Empty, Empty)
    | Node (y, left, right) ->
      if x <= y then Node(y, (insert x left), right)
      else Node(y, left, (insert x right))

'a bt は多相ヴァリアントといい、'aは任意の型を受け取るためのおまじない。
だから int型でもstring型でも入れれるbtreeができたわけ。

type 'a bt = Empty | Node of 'a * 'a bt * 'a bt は btreeを構成するコンポーネントを表現していて、

葉であれば、 Node (x, Empty, Empty) といった具合にかける。
ノードであれば、 Node x, (Node (y, Empty, Empty)), (Node (z, Empty, Empty)) といった具体だ。
※これは、ノードがxという値を持ち且つ子にyとzの葉を持つ、という形を表している。

実行例

こんな感じで実行できる。utop[x]> はプロンプト。

    utop[9]> let bt = Node (3, Node (1, Empty, Empty), Node(4, Empty, Empty)) ;;
    val bt : int bt = Node (3, Node (1, Empty, Empty), Node (4, Empty, Empty))
    utop[10]> member 1 bt ;;
    - : bool = true
    utop[11]> member 2 bt ;;
    - : bool = false
    utop[12]> insert 2 bt ;;
    - : int bt =
    Node (3, Node (1, Empty, Node (2, Empty, Empty)), Node (4, Empty, Empty))

ちょっと変わった実装

こんなふうにbtreeの型を書いてもよい。

type 'a t = Leaf of 'a | Node of 'a t * 'a t

この時の find と insertはこんな感じになる。

exception Node_format_error
let rec find2 v (t:'a t) = match t with
  | Leaf x -> if x = v then true else false
  | Node (Leaf x, Leaf y) -> if x = v || y = v then true else false
  | Node (Leaf x, Node (y, z)) 
  | Node (Node (y, z), Leaf x) -> if x = v then true else
    if x >= v then find2 v y else find2 v z
  | _ -> raise Node_format_error

let rec insert2 v (t:'a t) = match t with
  | Leaf x -> if x <= v then Node(Leaf x, Leaf v) else Node (Leaf v, Leaf x)
  | Node (Leaf x, Leaf y) -> Node (Leaf x, (insert2 v (Leaf y)))
  | Node (Leaf x, Node (y, z))
  | Node (Node (y, z), Leaf x) -> if x >= v then Node (Leaf x, Node ((insert2 v y), z))
    else Node (Leaf x, Node (y, (insert2 v z)))
  | _ -> raise Node_format_error

Node が 'a t のタプルで表現されているため、前後のどちらに Leaf 型が来るかわからないため、パターンマッチにてごちゃごちゃする必要がある。

型を少ない要素で実装できた分、これを操作するためのmethodが複雑になってしまった。
ただし、データ構造はかなりスッキリした形で見える。

実行例

スッキリ見えるではないか！

    utop[16]> let t = Node (Leaf 3, Node (Leaf 1, Leaf 4)) ;;
    val t : int t = Node (Leaf 3, Node (Leaf 1, Leaf 4))
    utop[20]> find2 1 t ;;
    - : bool = true
    utop[21]> find2 2 t ;;
    - : bool = false
    utop[22]> insert2 2 t ;;
    - : int t = Node (Leaf 3, Node (Node (Leaf 1, Leaf 2), Leaf 4))

まとめ

特に無し。後で自分のブログに移すかも（その時はちゃんと書く）。
コメントやマサカリ待ってます