「平衡二分木」:関数型プログラミングの初級問題 -44問目- （3日）

　二分木についての練習問題と答案です。問題は、OCaml公式ページのものを使いました。答案の作成時間は、約3日でした。

問題44.

　完全な平衡二分木とは、全ての節が、特徴：「部分木の節の数が左右でほぼ等しい（差が高々1である）」を満たすものを言う。
　与えられた数の節を有する完全な平衡二分木を全て列挙してなるリストを生成する関数cbal_treeを書け。
　列挙にはバックトラッキングを用いるべきである。
　二分木の型には以下の定義を用いよ。
type 'a binary_tree =
| Empty
| Node of 'a * 'a binary_tree * 'a binary_tree
　節の値は'x'とせよ。

答案

本問の解き方

　各種の二分木は文献により定義が異なります。そこで、この記事に於ける用語を定義します。
　完全二分木：葉の深さが全て等しい二分木
　平衡二分木：葉の深さの差が高々1である二分木

　本答案の基本的な発想は以下の通りです。
　まず、所与の数$${n}$$に対し、節数$${m(\leqq nかつ最大)}$$からなる完全二分木$${CT_m}$$を生成します。
　例えば、$${n=4}$$とすると、$${m=3}$$の完全二分木$${CT_{m=3}}$$を生成します。

m=3の完全二分木

　このとき$${n-m=1}$$なので、節数4の二分木にするには、完全二分木$${CT_{m=3}}$$の葉に節を一つだけ付け加えます。
　このように節が加えられた二分木は、平衡二分木になります。
　節を付けることができる位置は葉の数$${k}$$×左右二箇所であり、節の数は$${n-m}$$です。
　つまり、$${_{2k}\mathrm{C}_{n-m}}$$の組合せになります。

n=4, (節の位置、左？)=(1, true)

n=4, (節の位置、左？)=(1, false)

n=4, (節の位置、左？)=(2, true)

n=4, (節の位置、左？)=(2, false)

　この組合せをバックトラッキングにより求めて、平衡二分木のリストBTLを生成します。

　次に、平衡二分木のリストBTLから「完全な」二分木を選び出します。「完全な」の意味は問題文の特徴そのままです。

　以上により、完全な平衡二分木のリストが生成されます。

　細かい点としては、完全二分木の節の値に位置を示す数字を設定しています。

　これは、平衡二分木の実装とデバッグのためのものです。最終的には全ての値を'x'に置き換えています。

コード

type 'a binary_tree = Empty | Node of 'a*'a binary_tree*'a binary_tree

let rec pow2 n = if n = 0 then 1 else 2*pow2 (n-1)

let complete_binary_tree depth =
 let rec loop sn level =
  if level = 0 then Node (sn, Empty, Empty)
  else let s = pow2 (depth-level+1)-1+2*(sn-(pow2 (depth-level)-1)) in
  Node (sn, loop s (level-1), loop (s+1) (level-1)) in
 loop 0 depth

let rec leaf_list = function
 | Node (sn, Empty, Empty) -> [(sn, true); (sn, false)]
 | Node (_, left, right) -> leaf_list left@leaf_list right
 | Empty -> []

let rec append tpl =
 let (sn, is_left) = tpl in
 function
  | Node (label, left, right) when label = sn ->
   if is_left then Node (label, Node (-1, Empty, Empty), right)
   else Node (label, left, Node (-1, Empty, Empty))
  | Node (label, left, right) -> Node (label, append tpl left, append tpl right)
  | _ as node -> node

let rec balanced_tree n lst tr =
 if n = 0 then [tr]
 else match lst with [] -> []
   | head::tail -> balanced_tree (n-1) tail (append head tr)@balanced_tree n tail tr

let rec replace =
 let rec loop = function Empty -> Empty
  | Node (_, left, right) -> Node ('x', loop left, loop right) in
 function [] -> [] | head::tail -> loop head::replace tail

let nodes_to_depth n =
 let rec loop i = if n < pow2 (i+1)-1 then i else loop (i+1) in loop 0
 let rec depth_to_nodes d = if d = 0 then 1 else (pow2 d)+depth_to_nodes (d-1)

let rec number_of_nodes = function Empty -> 0
 | Node (_, left, right) -> (number_of_nodes left)+(number_of_nodes right)

let rec is_completely = function Empty -> true
 | Node (_,left, right) -> number_of_nodes left = number_of_nodes right && is_completely left && is_completely right

let cbal_tree n =
 let d = nodes_to_depth n in
 let cbt = complete_binary_tree (d-1) in
 let rec loop = function [] -> []
  | head::tail -> if is_completely head then head::loop tail else loop tail in
 replace (loop (balanced_tree (n-(depth_to_nodes (d-1))) (leaf_list cbt) cbt))

　関数complete_binary_treeは、深さdepthの完全二分木を生成します。
　関数leaf_listは、引数の二分木の葉の値（位置）と、左右を示すブール値とからなる枝タプルを要素とするリストを生成します。
　関数appendは、枝タプルで示される位置に、葉を付け加えます。
　関数balanced_treeは、付け加える節の数nと、枝タプルのリストlstと、完全二分木trとから平衡二分木を生成します。
　後は、だいたい名前の通りの働きをする関数です。　　

感想

　今回の問題は、非常に時間が掛かりましたが何とか解けました。二分木の扱いに馴れていないために、冗長なコードになっています。

　一番の難点は、バックトラッキングでした。
　命令型プログラミングでは、破壊的代入により、バックトラッキング前の状況を保存しておけるのですが、関数型ではそれができません。
　これは、タイムリープで過去に戻ったときに、記憶も戻ってしまう場合に似ています。何も憶えていないので、同じ行動しかできません。
　本答案では、状況を保存するためのリストを引数にすることで解決しました。

　関数型プログラミングでは、その場しのぎの改造をすると、関数と引数がどんどん増えていきます。今回のコードにはそれが如実に表れています。

　次回は、第45問です。今回から出題分野が二分木になりました。まだ二分木処理の定石をつかめません。次も時間が掛かりそうです…