今日の記録 2020/6/14

勉強した

プログラミング Erlang P171~177

Erlang と C での通信の実装方法。Cでのバイトデータの取り扱いも含めてこれまでやったことがない分野であるため、一旦全体を読んだ。明日細部に注目しつつ実装してみる。

みんなのデータ構造 P125 - 問6.6

ツリーがサイズについてバランスされているかどうかの判定関数を、O(n) で書け、という問題。バランスされていることの定義は、任意のノードにおいて左右の子のサイズの差が1以下であるので、ルートの左右の子のサイズを見るだけではなく、全てのノードについて差が1以下であるかを調べる必要がある。計算量の導出が怪しいことと、 Erlang を使った場合、現在の知識だと、変数を使えないので計算量が少ない実装をするには特殊な方法を取る必要がありそうだったので、ひとまず単純な実装で試すことにした。

まずツリーのサイズを計算する関数は以下になる。

% ツリーが持つノードの数
t_size(nil) ->
   0;
t_size({node, _, Left, nil}) ->
   1 + t_size(Left);
t_size({node, _, nil, Right}) ->
   1 + t_size(Right);
t_size({node, _, Left, Right}) ->
   1 + t_size(Left) + t_size(Right).

t_size_test() ->
   0 = t_size(nil),
   1 = t_size({node, 1, nil, nil}),
   2 = t_size({node, 1, {node, 1, nil, nil}, nil}),
   Tree = {node, 1, {node, 2, {node, 4, nil, nil}, nil}, {node, 4, nil, {node, 8, nil, nil}}},
   5 = t_size(Tree).

そしてこれを使って、ツリーがバランスかどうかを判定する関数は以下のように実装した。

t_balanced({node, _, nil, nil}) -> true;
t_balanced({node, _, nil, {node, _, nil, nil}}) -> true;
t_balanced({node, _, {node, _, nil, nil}, nil}) -> true;

t_balanced({node, _, Left, Right}) ->
   case abs(t_size(Left) - t_size(Right)) > 1 of
       true -> false;
       false -> t_balanced(Left) and t_balanced(Right)
   end.

t_balanced_test() ->
   Tree1 = {node, 1, nil, nil},
   true = t_balanced(Tree1),
   Tree2 = {node, 2, nil, {node, 3, nil, nil}},
   true = t_balanced(Tree2),
   Tree3 = {node, 1, nil, {node, 2, nil, {node, 3, nil, nil}}},
   false = t_balanced(Tree3),
   Tree4 = {node, 1, {node, 2, nil, nil}, {node, 4, nil, nil}},
   true = t_balanced(Tree4),
   Tree5 = {node, 1, {node, 2, {node, 3, nil, nil}, nil}, nil},
   false = t_balanced(Tree5),
   % ルートの両方の子のサイズは同じだが、その下でバランスされていないツリーでの
   Tree6 = {node, 1, {node, 2, {node, 6, {node, 8, nil, nil}, nil}, nil}, {node, 3, {node, 9, nil, nil}, {node, 7, nil, nil}}},
   false = t_balanced(Tree6).

まず基底部として、3パターンの最小のツリーがバランスであることを最初の3行で定義する。それ以外の場合は、子のサイズを見て差が1より大きければその時点でバランスでないとなる。そうでなければ、両方の子のバランスを見てその結果を and で取ったものが true か false かで木全体がバランスであるかを決定する。各ノード事に t_size 関数を使っているため、計算量はかなり多い。

データ構造とは関係がないが、Erlang ではガード部（関数定義のガード、またはifの条件式）に自分で実装した関数を使うことができないという制限があることを知らずに少し困った。 caseの場合だと問題なく使えたのでcaseを使って実装した。