Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
0
Help us understand the problem. What is going on with this article?
@Asya-kawai

Btreeを雑に書く

More than 1 year has passed since last update.

これは何?

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))

まとめ

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

0
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Asya-kawai
ふにゃ〜

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
0
Help us understand the problem. What is going on with this article?