Document

アルゴリズムとデータ
構造
第7回演習解答
2015/11/18実施
アルゴリズムとデータ構造2015
第7回演習解答(1/4)
[問１]節点数nの２分木の外点の数がn+1であることを証明せよ。
次の定理を使うと簡単。
この定理は覚えておく価値あり！
[定理] 節点数nの木の辺の数はn-1
(問1の解答) 外点の数をmとすると内点と外点を合わせた木の節点数はn+m
で辺の数はn+m－1である。全ての内点からはちょうど２本の子への辺が
出ており、外点からは子への辺が出ていないので辺の数は2nである。
よって
n+m－1=2n
従って m=n+1となり、外点の数がn+1であることが示された。
（定理の証明）n=1のとき、辺の数は0であるので定理は成り立つ。
n=k(k≧1)のとき定理が成り立つと仮定する。
n=k+1の任意の木Tの辺の数をmとする。
Tから葉の１つを取り除いた木T’は、節点数k、辺数m－1の木である。
木T’に対して定理が成り立つと仮定しているので
m-1=k-1
よって、m=k=n-1となり、n=k+1のときにも定理が成り立つことが示された。
2015/11/18実施
アルゴリズムとデータ構造2015
第7回演習解答(2/4)
（問１の直接的な解答）
「節点数nの２分木の外点の数がn+1である」
①
とおく。①が全ての自然数について成り立つことを数学的帰納法で証明する。
n=1のとき、外点の数は2であるので①は成り立つ。
n=k(k≧1)のとき①が成り立つと仮定する。
n=k+1の任意の木Tの外点の数をmとする。
木Tの葉を１つ除いた木をT’とすれば、下図より節点数k、外点数m－1の木である。
T’に対しては①が成り立つことが仮定されているので
m－1=k+1
よって、m=k+2=n+1となり、n=k+1のときにも①は成り立つ。
2015/11/18実施
アルゴリズムとデータ構造2015
第7回演習解答(3/4)
[問２] ２分探索木を使って整列をするアルゴリズムを考える。ただし、２分探索木の各節
点の右部分木にはその節点に格納されている要素より大きい要素が格納され、左部分
木にはその節点に格納されている要素より小さい要素が格納されるものとする。以下の
問いに答えよ。
木のなぞりは再帰アルゴリズムで簡単に実現可能
(a) 5,1,8,3,6,9,7,2をこの順
に格納するときにできる２分
探索木を図示せよ。
5
1
8
3
2
6
9
7
inorder(Node node) {
if(nodeに左の子が存在) inorder(nodeの左の子);
nodeに格納されている要素を出力
if(nodeに右の子が存在) inorder(nodeの右の子);
}
図：中順出力をするアルゴリズム
（最初はinorder(根節点)をcall）
(b) ２分探索木を使って全順序集合の要素を整列をするアルゴリズム(手順)を記述せ
よ。ただし、整列すべき要素は配列A[0],A[1],...,A[n-1]で与えられるものとし、結果も
同じ配列に入れるものとする。
Step 1 空の２分探索木に、A[0],A[1],…,A[n-1]を挿入する。
Step 2 Step 1で作成した２分探索木に対し、深さ優先探索による木のなぞり
を行い、中順でi番目（最初は０番目）の要素をA[i]に格納する。
2015/11/18実施
アルゴリズムとデータ構造2015
第7回演習解答(4/4)
(c)上記のアルゴリズムの平均時間計算量の漸近的上界を出来るだけ精度よく求めよ。た
だし、n個の要素をランダムな順番で格納した場合の節点の平均の深さはO(log n)であると
いう事実を使ってよい。
（Step 1の解析）
i番目の要素を格納するのにかかる時間は、i番目の要素が格納される
深さに比例する時間で抑えられる。節点の平均の深さはO(log n)であるから、
n要素の挿入では平均時間計算量はO(n log n)となる。
（Step 2の解析)
木のなぞりを行い中順出力するにはO(n)の時間で行える。
よって全体ではStep １が律速段階となり平均時間計算量は、O(n log n)となる。
(d)２分探索木を使って整列するアルゴリズムを少し変えて最悪時間計算量を減らすに
はどうしたらよいかを述べよ。
Step 1において、AVL木の挿入アルゴリズムを用いることによりStep 1の
最悪時間計算量をO(n log n)に抑える。
2015/11/18実施
アルゴリズムとデータ構造2015

Download Report