「対称な平衡二分木」:関数型プログラミングの初級問題 -47問目- （5分）

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

問題47.

　与えられた数の節を有する対称かつ完全な平衡二分木を全て列挙してなるリストを生成する関数であって、列挙を総当たりにより行う関数sym_cbal_treesを書け。

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

答案

本問の解き方

　問題44の答案で、完全な平衡二分木のリストを生成する関数cbal_treeを作成しました。
　問題45の答案で、二分木が対称か否かを判定する関数is_symmetricを作成しました。
　そこで、関数cbal_treeにより生成されたリストを、関数is_symmetricにより選別することで、対称かつ完全な平衡二分木のリストが得られます。
　もとより関数cbal_treeは総当たりでリストを生成するので、問題文の条件を満たします。

コード　　

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


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

	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 in

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

	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 in

	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 in

	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 in

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

	let rec depth_to_nodes d = if d = 0 then 1 else (pow2 d)+depth_to_nodes (d-1) in

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

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

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


let is_symmetric =
	let rec reverse = function Empty -> Empty
		| Node (label, left, right) -> Node (label, reverse right, reverse left) in

	let rec is_same = function
		| (Node (_, left_a, right_a), Node (_, left_b, right_b)) -> 
			is_same (left_a, left_b) && is_same (right_a, right_b)
		| (Empty, Empty) -> true
		| _ -> false in

	function Empty -> true
		| Node (_, left, right) -> is_same (left, (reverse right))

let rec filter p = function [] -> []
	| head::tail -> if p head then head::filter p tail else filter p tail

let sym_cbal_trees n = filter is_symmetric (cbal_tree n)

　今回はnoteの「コード」機能を使いました。
　相変わらずとても高度なハイライト処理です。この驚異的な技術力の高さは、小学校高学年、いや中学1年に匹敵すると言っても過言ではありません。

感想

　今回の問題は、以前の答案を流用するだけなので簡単でした。

僕の本当の実力
　本来の問題47には、上記の問題文から更に続きがあります。
　その続きには、「節数57の木の数はいくつか？」や、節数と木の数との関係についての「条件式を導け」など、情報科学的な問題が記載されています。
　しかし、私は「プログラミングの練習問題を解きたい」のであって、出題者の「先生ごっこに付き合いたい」訳ではありません。
　なので、全て無視しました。

　「僕こんなことも知っているんだ！」をやりたいが、それらの知識を纏めてプログラミングの問題とする能力はない。
　いつもながら幼稚な精神性が若々しくて素敵です。

　平衡二分木について
　今更ですが問題44における平衡木について、問題文と答案とで定義が異なっています。
　問題文の平衡木は、「数」についての平衡木（数平衡木）です。
　これに対し、答案の平衡木は、「高さ」についての平衡木（高さ平衡木）であり、数平衡木ではありません。
　しかし、「完全な」（部分木に含まれる節数の左右差が高々1以内）数平衡木は、高さ平衡木（左右の部分木の高さの差が高々1以内）でもあります。
　なぜなら、一つの節で生じる高さ（深さ）は1だからです。
　したがって、完全な数平衡二分木のクラスは、高さ平衡二分木のクラスに含まれます。

　何が言いたいかというと、定義は違っているけれでも、答案は間違ってないということです。
　そして、その答案を使いまわした今回の答案も間違っていないはずです。

　次回は、第48問です。無駄に長くなってしまった…