R-99: 99 の Ruby の問題 - 4. バイナリツリー
- 訳注1:問題番号の後のアスタリスクはPrologで解くときの難易度の目安。
バイナリツリー問題
バイナリツリーは、空か、ルート要素と二つのノードで構成されているバイナリツリー自体のいずれかである。
ここで用いる関数 t(X,L,R) では、X はルートノードを表し、L、R はそれぞれ左と右のサブツリー(訳注:部分木)を表す。 最小構成をnilと空ではないツリー、関数 t で表すツリーとする。
したがって、図4-1 のツリーは以下のように表すことができる。
T1 = t(a,t(b,t(d,nil,nil),t(e,nil,nil)),t(c,nil,t(f,t(g,nil,nil),nil)))
他の例は、ルートノードのみで構成されたバイナリツリーである。
T2 = t(a,nil,nil) # ルートノードのみのバイナリツリー
T3 = nil # 空のバイナリツリー
4.01 (*) 指定された関数がバイナリツリーを表しているかどうかを確認せよ
関数 istree(a) は、その引数はバイナリツリーを表すノードがある場合のみ成功するように書け。
例)
istree(t(a,t(b,nil,nil),nil)) => true
istree(t(a,t(b,nil,nil))) => false
4.02 (**) 完全にバランスの取れたバイナリツリーを作成せよ
完全にバランスの取れたバイナリツリー(訳注:以降「Bツリー」と呼ぶ)では、次の特性がノードごとに保持されている。 それは左サブツリーのノード数とその右サブツリーのノード数がほぼ等しく、それらの差が1以下であることを意味する。
ノードの数を指定された、Bツリーを作成するために関数 cbal_tree(a,b) を書く。 関数は、バックトラックを介してすべての解を生成する必要がある。 ツリーのすべてのノードに情報として文字 x を置く。
例)
x = "X"
T = t(x, t(x, nil, nil), t(x, nil, t(x, nil, nil)))
T = t(x, t(x, nil, nil), t(x, t(x, nil, nil), nil))
cbal_tree(4,T)
4.03 (**) 対称バイナリツリー
ルートノードを介して垂直線を描くことができるとき、右サブツリーが左サブツリーの鏡像である場合、 対称バイナリツリーと呼ぶことにする。 指定されたバイナリツリーが対称であるかどうかを確認する関数 symmetric(a) を書く。
参考: 一本のツリーが別の鏡像であるかどうかをチェックする関数 mirror(a,b) を書く。 ここでは、ツリーの構造にだけチェックできればよく、ノードの値は無視して良い。
4.04 (**) 二分探索ツリー (辞書)
例)
construct([3,2,5,7,1],T).
T = t(3, t(2, t(1, nil, nil), nil), t(5, nil, t(7, nil, nil)))
そして、この問題の解答をテストするには、この関数を使用している。
例)
test_symmetric([5,3,18,1,4,12,21]) => true
test_symmetric([3,2,5,7,4]) => false
4.05 (**) 生成と検査の方法
指定された数のノードを使用して、Bツリーを 作成するために生成と検査の方法を適用する。
(訳注: 生成と検査の方法(generate-and-test paradigm)とは、 複数の解を生成し、与えられた評価基準を満たさないものを排除することとによる問題解決方法のこと。)
例)
sym_cbal_trees(5)
=> [t(x, t(x, nil, t(x, nil, nil)), t(x, t(x, nil, nil), nil)), t(x, t(x, t(x, nil, nil), nil), t(x, nil, t(x, nil, nil)))]
57のノードがあるツリーがいくつあるか？ 指定された数のノードのためにいくつ解があるかについて調査せよ。 数が偶数である場合はどうすれば？ 適切な関数を書け。
4.06 (**) 高さバランスバイナリツリーの作成
高さバランスバイナリツリーにおいて、ノードごとに次の特徴がある。 その左のサブツリーの高さとその右のサブツリーの高さは、その差が1より大きくないことを意味し、ほぼ等しい。
所定の高さのために高さバランスバイナリツリーを作成するための関数 hbal_tree(a,b) を書く。 その関数は、バックトラックを介してすべての解を生成する必要がある。 ツリーのすべてのノードに情報としての文字'X'をセットする。
例)
hbal_tree(3) =>
t(x, t(x, t(x, nil, nil), t(x, nil, nil)), t(x, t(x, nil, nil), t(x, nil, nil)))
t(x, t(x, t(x, nil, nil), t(x, nil, nil)), t(x, t(x, nil, nil), nil))
false
4.07 (**) 指定された数のノードの高さバランスBツリーを作成
高さ H の高さバランスバイナリツリーを考える。それに含めることができるノードの最大数はいくつか？ MaxN = 2**H -1であることが明らかな時、最も小さなMaxNはいくつか？ この問題は、より困難である。再帰的な式を発見するために、 関数minNodes(a)として定義することに挑戦せよ。
minNodes(H) => N # 高さ H の高さバランスバイナリツリーの最小数 N が返る
もう一つの問う。N個のノードを持つ高さバランスバイナリツリーが 持つことのできる最大の高さ H はいくつか？
maxHeight(N) => N # 高さ H は N 個のノードを持つ高さバランスバイナリツリーの最大の高さ
今、ノードの数を与えられたすべての高さバランスバイナリツリーを作成する問題に着手することができます。
hbal_tree_nodes(N) => T # T は N個のノードを持つ高さバランスバイナリツリーです。
N = 15であるいくつかの高さバランスツリーが存在する方法を確認せよ。
4.08 (*) バイナリツリーの葉の数をかぞえよ
「葉」とは、後が続かないノードのことである。それらをカウントする関数 count_leaves(a) を書け。
count_leaves(T) => N # バイナリツリー T には N 個の葉がある。
4.09 (*) 配列内のバイナリツリーの葉を集めよ
「葉」とは、後が続かないノードのことである。それらを配列にする関数 leaves(T) を書け。
leaves(T) => S # S はバイナリツリー T の全ての葉の配列である。
4.10 (*) 配列内のバイナリツリーに含まれるノードを集めよ
バイナリツリーに含まれるノードには、1つ、2つまたはノードを含まない場合のいずれかである。 配列にそれらを集めるために、関数 internals(T) を書きます。
internals(T) => S # S はバイナリツリー T に含まれるノードの配列です。
4.11 (*) 配列内の指定された高さでのノードを集めよ
バイナリツリーのノードでは、ルートノードからある高さにあるノード N へのパス(訳注:経路)は、長さ N - 1を持つ。 ルートノードは、高さ 1 にある。 配列内の指定された高さで、全てのノードを集める関数 atlevel(T,L) を書け。
atlevel(T,L) => S # S は高さ L にあるバイナリツリーのノードのリストである。
atlevel(T,L) を使用して、関数 levelorder を作成し、そのノードの高さの帰りがけ順の並びを 作成することは簡単である。 しかし、それを行うためのより効率的な方法がある。
4.12 (**) 完全バイナリツリーを作成せよ
次のように高さ H の完全バイナリツリーが定義されている。
高さ 1,2,3,...,H - 1は、ノードの最大数を含む。 つまり、2**(i - 1) が高さ i の時、ルートにの高さは 1 とカウントすることに注意せよ。
ノードの最大数よりも少なく、含まれても良い n 個の高さ H は、全てのノードが「左調整」 されています。 これは、全ての含まれるノードが最初に来る高さ順ツリー探索では、ノードが最初で、 2番目に葉、後に何もないもの(nil は実際にはノードではない!)がくる。
特に、完全バイナリツリーは、ヒープのためのデータ構造(またはアドレス指定方式)として使用されている。
数 1 でルートから始まる、高さの帰りがけ順のツリーに含まれるノードを列挙することによって、 完全バイナリツリー内の各ノードへのアドレス番号を割り当てることができる。 そうすることで、アドレス A を持つ全てのノード X は、次の特徴を保持していることを実現する。
X の左右に続くノードのアドレスは、2 * Aと2 * A + 1のそれぞれのノードが存在すると想定する。 この事実は優雅な完全バイナリツリー構造を構築することができる。 次に関数 complete_binary_tree(N) の仕様を書く。
complete_binary_tree(N) => T # T は N 個のノードを持つ完全バイナリツリーである。
適切な方法でその関数をテストせよ。
4.13 (**) バイナリツリーのレイアウト その1
Ruby のクラスとしてTree::initialize(X,L,R)というバイナリツリーが与えられる。 ツリーを描画するための準備として、レイアウトアルゴリズムは、矩形グリッド内の各ノードの位置を決定する ために必要とされる。いくつかのレイアウト方法の内の一つは、以下の図のように示すことができると考えられる。
このレイアウト方法において、ノード V の位置は、次の2つのルールによって得ることができる。
x(v)はノード v の位置に等しい正常なノードy(v)はツリーの帰りがけ順内のノード v の深さに等しい
ノードの位置を記憶するために、ノード(およびその次)を次のように表すように Ruby の用語を拡張します。
nilが(いつものように)空のツリーを表すt(W,X,Y,L,R)は(X,Y)に位置するルート W、およびサブツリー L と R の空でない バイナリツリーを表す。次の仕様で関数 layout_binary_tree(T) を書け
layout_binary_tree(T) => PT # PT はバイナリツリーから得られた「位置付け」バイナリツリーです。
適切な方法で作成した関数をテストせよ。
4.14 (**) バイナリツリーのレイアウト その2
代替のレイアウト方法は、上の図に示されている。規則を見つけ、対応する Ruby の関数を記述せよ。
ヒント: 指定された高さでは、隣接ノードとの水平距離は一定である。
問題 4.13 と同様の規則を使用して、適切な方法でその関数をテストせよ。
4.15 (***) バイナリツリーのレイアウト その3
されに別のレイアウト方法は、上の図に示されている。 この方法は、全てのノードで特定の対称性を維持しながら非常にコンパクトなレイアウトが得られる。 規則を見つけ、対応する Ruby 関数を書け。
ヒント: ノードとその後ろのノード間の水平距離を考慮せよ。
もれなく組み合わされたバイナリツリーを作成するためにどのように2つのサブツリーをひとまとめにするか？
問題 4.13 と 4.14 と同様の規則を使用して、適切な方法でその関数をテストせよ。
注: これは難しい問題だ。簡単に諦めてはいけない!
もっとも好みのレイアウトはどれか？
4.16 (**) バイナリツリーの文字列表現
誰かが次のタイプ(例を参照)の文字列としてバイナリツリーを表示する。
a(b(d,e),c(f(g,)))
- ツリーが(nil または
t(X,L,R)の用語として)いつものように与えられている場合、 この文字列表現を生成する Ruby 関数を書け。そして、この逆を行う関数を書け。 すなわち、通常の形でツリーを作成し、文字列表現を与える。最後に、両方の方向で使用することができる 単一の関数 tree_string(a,b) の二つの引数を組み合わせる。
- 差分配列とツリーの両方向の差分リストを変換し、関数 tree_dlist(a,b) を使用して 関数 tree_string(a,b) と同じ関数を書け。
簡単にするために、ノード内の情報は単一の文字であるとし、文字列にはスペースは含まない。
4.17 (**) バイナリツリーの行きがけ順と帰りがけ順
問題 4.16 の例のように、単一の小文字で識別されるノードとバイナリツリーについて検討する。
- 与えられたバイナリツリーの行きがけ順と帰りがけ順 をそれぞれ作成する関数
preorder(a,b) と inorder(a,b) を書け。。 結果は最小構成であるべきだ。例えば問題 4.16 の例の行きがけ順のための'abdecfg'。
- 問題 a から
preorder(a,b)を逆方向に利用できるようにせよ。 すなわち行きがけ順が与えられると、対応するツリーを構築する。ない場合は、必要な手配をせよ。
- バイナリツリーのノードの行きがけ順と帰りがけ順が与えられた場合、次のように明確にツリーが 決定する。関数
pre_in_tree(a,b,c)を書け。
- 問題 a から c を異なる配列で解け。解答を比較するために関数の実行時間を取得せよ。
同じ文字が複数のノードに表示された場合はどうなるか。`pre_in_tree("aba","baa")'を試せ。
4.18 (**) バイナリツリーのドットストリング記法
問題 4.16 の例のように、単一の小文字で識別されたノードと、再びバイナリツリーを検討する。 このようなツリーは、空のサブツリー(nil)は、ツリー探索中に遭遇されるドット(".")が挿入された そのノードの行きがけ順によって表すことができます。 例えば、問題 4.16 に示すツリーは次のように表現される: "abd..e..c.fg..." まず、構文(BNFや構文ダイアグラム)を確立しようとした時、両方向の変換を行い、関数 tree_dotstring(a,b)のように書く。差分配列を使用せよ。
