「二分木の行きがけ順、通りがけ順」（中級）:OCaml演習 -59問目-
二分木についての練習問題と答案です。問題は、OCaml公式ページのものを使いました。答案の作成時間は、約一日でした。
問題 59.
本問題においては、各節が、その節の値により識別されるような二分木を考える$${^※}$$。
※ つまり、節の値がユニークな二分木しか対象にしません。
問一 二分木の節の値を、行きがけ順でリストに集める関数preorderと、通りがけ順でリストに集める関数inorderを書け。
問二 関数preorderによるリストから二分木を生成する関数を書けるならば書け。無理な場合は、高度の柔軟性を維持しつつ臨機応変に対処せよ。
問三 関数preorderと関数inorderとによる二つリストから二分木を生成する関数pre_in_treeを書け。
問四 問一から問三を差分リストを用いて解け。 シャーシャー! また、それらの答えの実行時間を比較せよ。
定義と用語
行きがけ順：親、左部分木、右部分木の順
通りがけ順：左部分木、親、右部分木の順
高度の柔軟性を維持しつつ臨機応変に対処：行き当たりばったり
差分リスト：リストの表現であって、そのリストを他のリストの前方（左）に連接する関数で表した表現
答案
本問の解き方
問一 問題文のままです。木を巡り節の値を集めます。
問ニ 当たり前ですが関数preorderによるリストだけでは一意的に二分木を決定することができません。
例えば、関数preorderの戻り値がリスト['a'; 'b']の場合、元の二分木は、
Node ('a', Node ('b', Empty, Empty), Empty)
または、
Node ('a', Empty, Node ('b', Empty, Empty))
いずれの可能性もあります。
これらの二分木とリストとを比較すると、二分木の要素が{'a', 'b', Empty, Empty, Empty}の五つであるのに対して、リストの要素は{'a', 'b'}の二つしかありません。
リストには、Emptyが存在していません。つまり、リストからは、子が存在しない（部分木が空である）と言う情報が欠落しているのです。
ところで、問題文によれば、問ニでは、必要に応じた変更（何に対して？）が許されるそうです。
そこで、部分木が空の場合であるに、その情報を補ったリストを生成するように関数preorderを改造します。
具体的には、二分木に節を補って完全二分木（perfect binary tree）を構成すると共に、補った節に「空であることを示す値」を設定します。
さらに「空であることを示す値」は、引数である二分木の型に依存するので、これも引数とします。
…と言う具合に、一度は答案を作りました。しかし、この誰でもすぐに思いつく解法を出題者が次の問題60として出題しやがりました。
しかたがないので、別の解法による答案を作成することにします。
まず、すぐに気づくことですが、空の部分木がなければ、つまり完全二分木（perfect binary tree）ならば、節の位置は一意的に定まります。
そこで、節の値に、完全二分木における節の位置の情報を付け足すことが考えられます。
位置情報としては、例えば、左右の別および深さ、または深さ順の順番（下図参照）などがあります。
本答案では、逆作用関数の作り易さを考えて、深さ順の順番を用いました。
問三 理屈立てた解き方を思いつかなかったので、行き当たりばったりに解きました。
高さ3の完全二分木（perfect binary tree）について、関数preoderによるリスト（pre_list）と関数inorderによるリスト（in_list）との関係を考えます。
> let perfect_tree = create_perface 3;;
val perfect_tree : int Binary_tree.t =
Node (1, Node (2, Node (4, Empty, Empty), Node (5, Empty, Empty)),
Node (3, Node (6, Empty, Empty), Node (7, Empty, Empty)))
> let pre_list = preorder perfect_tree;;
val pre_list : int list = [1; 2; 4; 5; 3; 6; 7]
> let in_list = inorder perfect_tree;;
val in_list : int list = [4; 2; 5; 1; 6; 3; 7] まず、pre_listの最初の要素である根'1'について注目します。in_listでは、'1'よりも前の部分リスト[4; 2; 5]が左部分木の値を集めたリストに、後ろの部分リスト[6; 3; 7]が右部分木の値を集めたリストになっています。
次に、pre_listの二番目の要素である節'2'について注目します。ここで、'2'が'1'の左部分木においては根であることから、in_listの代わりに先ほどの前の部分リスト[4; 2; 5]を用います。
そうすると、'2'の前の部分リスト[4]が左部分木の値を集めたリストに、後ろの部分リスト[5]が右部分木の値を集めたリストになっていることが分かります。
このような規則性があるのは、通りがけ順（inorder）では、左部分木、親、右部分木の順に要素を集めるからです。改めて言うほどのことでもないのですが…
そこで、この規則を基に二分木を生成します。
具体的には、まず、pre_listの先頭要素を親とし、in_listにおいて、その要素よりも前の部分リストを左の子、要素よりも後ろの部分リストを右の子として節（根）を生成します。
次に、pre_listの二番目の要素を親とし、その二番目の要素が根の左右いずれの部分木の親になるかを判断し、左なら前の部分リスト、右なら後ろの部分リストをin_listの代わりにとして根の場合と同様に節を生成します。
さらに、pre_listが空になるまで同様の処理を繰り返します。
なお、二分木が完全二分木でない場合は、当然にリストに抜けが発生しますが、それについては適当に処理します。
問四 問題文の通りに差分リストを用います。ただし、差分リストは、リスト連接の関数'@'についての表現なので、リスト連接以外の処理は、通常のリストに戻して行います。
コード
二分木のモジュール
module Binary_tree : (sig
(* 二分木の型定義 *)
type 'a t = Empty | Node of 'a*'a t*'a t
end)
= (struct
type 'a t = Empty | Node of 'a*'a t*'a t
end)問一
open Binary_tree
let rec preorder = function
| Empty -> []
| Node (a, l, r) -> a::(preorder l)@(preorder r)
let rec inorder = function
| Empty -> []
| Node (a, l, r) -> (inorder l)@[a]@(inorder r)問二
open Binary_tree
(*
二分木trについて(a, i)からなるタプルのリストを生成する関数
a: 節の値
i: 完全二分木（perfect binary tree）における行きがけ順での節の順番
*)
let preorder' tr =
let rec loop d = function
| Empty -> []
| Node (a, l, r) -> (a, d)::(loop (2*d) l)@(loop (2*d+1) r) in
loop 1 tr
(* preorder'によるリストから二分木を再現する関数 *)
let inv_preorder = function
| [] -> Empty
| (root, _)::tl ->
let rec loop tr = function
| [] -> tr
| (a, i)::tl ->
let rec append d = function
| Empty -> Empty
| Node (x, Empty, r) when i = 2*d -> Node (x, Node (a, Empty, Empty), r)
| Node (x, l, Empty) when i = 2*d+1 -> Node (x, l, Node (a, Empty, Empty))
| Node (x, l, r) -> let d' = 2*d in Node (x, append d' l, append (d'+1) r) in
loop (append 1 tr) tl in
loop (Node (root, Empty, Empty)) tl問三
open Binary_tree
(* リストを前後に分割する関数 *)
let split_at d lst =
let rec loop = function
| [] -> ([], [])
| hd::tl when hd = d -> ([], tl)
| hd::tl -> let (h, t) = loop tl in (hd::h, t) in
loop lst
let pre_in_tree tr =
let rec loop ilist plist = match (ilist, plist) with
| ([], lst) -> (Empty, lst)
| (hd::[], _::tl) -> (Node (hd, Empty, Empty), tl)
| (_, hd::tl) ->
let (lf, rt) = split_at hd ilist in
let (l, tl) = loop lf tl in
let (r, tl) = loop rt tl in
(Node (hd, l, r), tl)
| _ -> failwith "Invalid argument" in
let (ret, _) = loop (inorder tr) (preorder tr) in ret差分リストのモジュール
module Binary_tree : (sig
(* 差分リストの型定義 *)
type 'a t = Dlist of ('a list -> 'a list)
(* リストの差分リスト表現を生成する関数 *)
val dlist_of : 'a list -> 'a t
(* 差分リストをリストに戻す関数 *)
val to_list : 'a t -> 'a list
(* リストを連接する関数 *)
val ( @@ ) : 'a t -> 'a t -> 'a t
end)
= (struct
type 'a t = Dlist of ('a list -> 'a list)
let to_list (Dlist a) = a []
let dlist_of a = Dlist (fun x -> a@x)
let ( @@ ) (Dlist f) (Dlist g) = Dlist (fun x -> f (g x))
end)問四
open Binary_tree
open Dlist
(* 空リストの差分リスト表現 *)
let nil = dlist_of []
(*
以下、問一および問三と同名の関数は、同じ作用を持つ関数の差分リスト版
問二については、作り直すのが面倒くさかったので、
当初答案の関数（空の木の情報を補完したリストを作成する関数）の差分リスト版
*)
let rec preorder = function
| Empty -> nil
| Node (a, l, r) -> (dlist_of [a])@@(preorder l)@@(preorder r)
let rec inorder = function
| Empty -> nil
| Node (a, l, r) -> (inorder l)@@(dlist_of [a])@@(inorder r)
let preorder' empty tr =
let rec loop = function
| Empty -> dlist_of [empty]
| Node (a, l, r) -> (dlist_of [a])@@(loop l)@@(loop r) in
loop tr
let inv_preorder empty lst =
let rec loop = function
| a::tl when a = empty -> (Empty, tl)
| a::tl ->
let (l, tl) = loop tl in
let (r, tl) = loop tl in
(Node (a, l, r), tl)
| _ -> failwith "Invalid argument" in
let (ret, _) = loop (to_list lst) in ret
let split_at d lst =
let rec loop = function
| [] -> ([], [])
| hd::tl when hd = d -> ([], tl)
| hd::tl -> let (h, t) = loop tl in (hd::h, t) in
loop lst
let pre_in_tree tr =
let rec loop ilist plist = match (ilist, plist) with
| ([], lst) -> (Empty, lst)
| (hd::[], _::tl) -> (Node (hd, Empty, Empty), tl)
| (_, hd::tl) ->
let (lf, rt) = split_at hd ilist in
let (l, tl) = loop lf tl in
let (r, tl) = loop rt tl in
(Node (hd, l, r), tl)
| _ -> failwith "Invalid argument" in
let (ret, _) = loop (to_list (inorder tr)) (to_list (preorder tr)) in ret感想
何が起こるか
問三について、出題者から、追加で「二分木に同じ値の節が出現する場合に、何が起こるか？」が問われています。
本答案の算法では、節（部分木の根）の値を区切りにして関数inorderによるリストを前後（二分木の左右）に分けているので、区切りの別がつかない場合は、元の二分木を再現できません。
より詳細には、本答案の算法では、関数inorderによるリストに同じ値が連続して出現する場合に、それらの値の間には、空の部分木（Empty）が存在しないものと仮定して、二分木を生成します。
例えば、関数inorderによるリストを['a', 'a']とします。ここで、空の木（Empty）を''で表した場合、['a', 'a']は、['a', 'a', '']と['a', '', 'a']のいずれにも当てはまります。
本答案の解法は、前者['a', 'a', '']であると仮定して、Node ('a', Node ('a', Empty, Empty), Empty)を生成します。
そのため、['a', 'a']が、['a', '', 'a']である場合は、Node ('a', Empty, Node ('a', Empty, Empty))を再現できません。
Cool!
問四において、出題者は、差分リストに対してシャーシャー！と書いているのですが、実際のところ、差分リストはちっともクールじゃありません。
確かに差分リストが有利になるような極端な二分木（左の子しか存在しない二分木）で比較すれば、差分リストのほうが実行時間は短くなります。
しかし、左右がほぼ均等な二分木、例えば、完全二分木（perfect binary tree）では、差分リストのほうが遅くなります。
OCamlがリスト連接関数@について特別な実装をしているわけではなく、一般的な実装でも同じ結果になります。
シャーシャー！と書いた意図がまったく理解できません。覚えたての言葉を使いたいいたいお年頃なのでしょうか？中学生がやたらと因数分解を使いたがるように…
長いよ…ソースコード抜いても3500文字だよ…
予告
「本問の解き方」の「問二」にも書いたように、次回の問題60は、問二の当初答案にて既に解いています。なので、簡単でしょう。
出題者には、早く数字の勘定を憶えてもらいたいですね。一つの問題で四問も出題していたら「九十九問」じゃなくなりますよ?
いいなと思ったら応援しよう！
