「高さ平衡二分木」:関数型プログラミングの初級問題 -48問目- （5分）

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

問題48.

　高さ平衡二分木では、全ての節が性質「左部分木の高さと右部分木の高さがほぼ等しい（高さの差が1を越えない）」を満たす。
　与えられた高さを有する高さ平衡二分木を全て列挙してなるリストを生成する関数hbal_treesを書け。
　関数はバックトラッキングによって全ての解を求めるべきである。
　全ての節の値に'x'を設定せよ。

※　前回と同様に二分木の型には以下の定義を用います。
type 'a binary_tree =
| Empty
| Node of 'a * 'a binary_tree * 'a binary_tree

答案

本問の解き方

　問題44の答案で、所与の節数を有する高さ平衡二分木のリストを生成する関数balanced_treeを作成しました。
　この関数blanced_treeは完全二分木に葉を追加することで、高さ平衡二分木を生成します。
　また、高さ平衡二分木においては、高さに対して取りうる節数は一意的には定まらずある範囲を取ります。

　したがって、解き方は以下のようになります。
　所与の高さから二分木の節数の範囲を求めます。
　その節数の範囲から完全二分木に追加する葉の数の範囲を求めます。
　その葉数の範囲から関数balanced_treeにより高さ平衡二分木のリストを生成します。
　それらのリストを合わせて一つのリストにします。
　以上により、所与の高さを有する高さ平衡二分木のリストが生成されます。

コード

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 range a b = if a <= b then a::range (a+1) b else []

let hbal_tree h =
 let cbt = complete_binary_tree (h-2) in
 let ll = leaf_list cbt in
 let n = depth_to_nodes (h-1) in
 let rec loop = function [] -> []
  | head::tail -> (balanced_tree head ll cbt)@loop tail in
 replace (loop (range 1 ((depth_to_nodes h)-n-1)))

感想

　今回の問題も、以前の答案を使い回すだけなので簡単でした。
　OCamlの練習問題では何度も繰り返されてきたように、また問題の難易度が逆転しています。今回は、私が「平衡木」を「高さ平衡木」と早とちりしたせいでもあるので、文句を言える立場ではありません。

　それでも、過去に作成した答案の一部を切り貼りする作業は退屈です。
　書いている私ですら退屈なのですから、読む人はもっとでしょう。
　なんとかしないといけません。

　次回は、第49問です。全99問の半分に達しました。正直なところ、同じような問題ばかりで飽きてきました。まあ、練習問題とはそういうものなのですが…

追記

　上述の答案（および参照している一連の答案）は、間違っています。
　答案は、完全二分木に対して単純に葉を追加することしか考慮していません。
　しかし、完全二分木から葉を削除して、それを補う（つまり、節を付け替える）場合も考慮しなくてはなりません。

　実装すべきアルゴリズムは思いついているのですが、OCamlを使うとなると面倒くさくてやる気が起きません。

　と言う訳で、「関数型プログラミングの初級問題」は放置状態にあります。
　OCamlの構文や関数型プログラミングの方法を忘れてしまう前に再開できるといいですね。