にぶんぎ？にぶんぎ！

二分木！ in OCaml

Ocamlで二分木書きました。再帰大得意な関数型言語の強みを味わいました……凄いですね。

2-3木

問題はこっち……ものすごく時間をかけたものの、削除関数だけ実装できず。
アルゴリズムを勉強していないもので（ｳｯ）、2-3木の実装は初めてでした。せっかくなので貼っちゃいますか。本当ならGitとかに上げておくと便利なんでしょうけど、それはまた後ででいいや。
型定義部。

type 'a tt_tree = Nil 
  | Leaf1 of 'a
  | Leaf2 of 'a * 'a
  | Leaf3 of 'a * 'a * 'a
  | Node2 of 'a * 'a tt_tree * 'a tt_tree
  | Node3 of 'a * 'a * 'a tt_tree * 'a tt_tree * 'a tt_tree;;

挿入関数。

let rec tt_tree_insert x t =
  let rec ins x t = (*return (bool active, 'a head, tt_tree left, tt_tree right)*)
    match t with Nil -> (false, 0, Leaf1(x), Nil)
    | Leaf1(v) ->
      if x < v then (false, 0, Leaf2(x, v), Nil)
      else (false, 0, Leaf2(v, x), Nil)
    | Leaf2(l, r) ->
      if x < l then (false, 0, Leaf3(x, l, r), Nil)
      else if x < r then (false, 0, Leaf3(l, x, r), Nil)
      else (false, 0, Leaf3(l, r, x), Nil)
    | Leaf3(l, c, r) ->
      if x < l then (true, c, Leaf2(x, l), Leaf1(r))
      else if x < c then (true, c, Leaf2(l, x), Leaf1(r))
      else if x < r then (true, x, Leaf2(l, c), Leaf1(r))
      else (true, r, Leaf2(l, c), Leaf1(x))
    (*in the case of Node2 or Node3, you need to check only keys. not mention to values*)
    | Node2(k, l, r) -> (*always return false*)
      if x < k then let (b, h, rl, rr) = ins x l
        in if b then (false, 0, Node3(h, k, rl, rr, r), Nil)
          else (false, 0, Node2(k, rl, r), Nil)
      else let (b, h, rl, rr) = ins x r
        in if b then (false, 0, Node3(k, h, l, rl, rr), Nil)
          else (false, 0, Node2(k, l, rl), Nil)
    | Node3(k1, k2, l, c, r) -> (*if receive true, return true*)
      if x < k1 then let (b, h, rl, rr) = ins x l
        in if b then (true, k1, Node2(h, rl, rr), Node2(k2, c, r))
          else (false, 0, Node3(k1, k2, rl, c, r), Nil)
      else if x < k2 then let (b, h, rl, rr) = ins x c
        in if b then (true, h, Node2(k1, l, rl), Node2(k2, rr, r))
          else (false, 0, Node3(k1, k2, l, rl, r), Nil)
      else let (b, h, rl, rr) = ins x r
        in if b then (true, k2, Node2(k1, l, c), Node2(h, rl, rr))
          else (false, 0, Node3(k1, k2, l, c, rl), Nil)
  in let (b, h, rl, rr) = ins x t
  in if b then Node2(h, rl, rr)
    else rl;;

検索関数。

let rec tt_tree_find x t = match t with Nil -> false
  | Leaf1(v) -> x = v
  | Leaf2(l, r) -> x = l || x = r
  | Leaf3(l, c, r) -> x = l || x = c || x = r
  | Node2(k, l, r) -> 
    x = k ||
      if x < k then tt_tree_find x l
      else tt_tree_find x r
  | Node3(k1, k2, l, c, r) ->
    x = k1 || x = k2 ||
      if x < k1 then tt_tree_find x l
      else if x < k2 then tt_tree_find x c
      else tt_tree_find x r

……ええ。汚いとは自分でも思ってます。思ってますとも。
再帰的な構造を意識した結果、返すものがいちいちヴァリアントになってますね。しかもそれの値を上でif文で評価して使う。いろいろ手間です。列挙型使ってまとめてしまうとか（それはそれでif文を使うことになるけど見易くはなる）何か出来たんじゃないかなと思います。
もしこの弱いブログを読んでくださった方が万が一にもいて、もし、もしもの話ですが、改善方法をご教授くださったら泣いて喜びます。流石に知恵袋とかでレビューお願いします、と投げるのはなんかなぁと思うので……贅沢ですね、すみません。

削除関数は省略。あまりに散らかったままなので、人に見せるものでは無いです。
なお、こちらのページの図がすごく参考になりました。2-3木ってなんぞや？から6時間くらいでだいたい理解し、削除関数以外実装出来ました。のんびりやっていた感は否めませんが。

ちなみにコードは提出したものの一部を切り取ってきました。提出物とかぶってる、コピペか、と怒らないでください先生。まぁこんなブログ見つからないと思いますけど_(:3 」∠ )_

タスク

ひぃぃぃぃ！
パターソン・ヘネシーを読むことになりました。その方面の研究をするなら常識、むしろ他の方面の人にとっての本であり、むしろそれを専門にするならヘネパタを読めという話ではありますが、とりあえずパタヘネです。
早く……早く読まねば……
やること多くて忙しいですが、充実感もあります。あとデスマっぽくないのが心に優しい。

DDR

先日、また判定のアプデがあったようで。少しだけ踏んで来ましたが、だいぶスコア出ますね。UNBELIEVABLE EDPで90万超えました。ライフ4抜けは難しそうですが。ひとまず15と16でライフ4抜けを増やしつつ、17を再クリア埋めします。体力取り戻さないとな……

l_n_m’s diary

よわい電気系の日記（本当にただの日記）

にぶんぎ？にぶんぎ！

二分木！ in OCaml

2-3木

タスク

DDR