どんなアルゴリズムなのか？
2分探索木を使ったアルゴリズム
- 木に含まれるすべてのノードがキー値をもっている
- Nの左側の部分木にあるすべてのノードのキー値は、Nのキー値よりも小さい
- Nの右側の部分木にあるすべてのノードのキー値は、Nのキー値よりも大きい
構造体Nodeの説明
要素の説明
- key キー値
- left 左側の子ノードへの参照
- right 右側の子ノードへの参照
構造体Nodeを新たに生成
p ← newNode(k)
- kは生成するノードのキー値、初期値となる。
- left、rightを参照するノードはNULLで初期化される。
- 生成されたpは"."を用いてkeyやleftなどにアクセスできる。
ノードの探索
1.根を参照する変数はt
参照対象の2分探索木の根を参照する変数をtとする
2.空のノードを調べる
2−1 根のノードが空あれば終了
tが空のノードであれば探索失敗と判断して探索を終了する。
2-2 根のノードに値があればkと比較する
tが空のノードでなければ、tのキー値t.keyとkを比較する
比べて大きければ右に小さければ左に等しければ終了
探索の関数は見つかったノードを返し、挿入の関数は木の根を返す
関数searchを用いてノードの総数がn個の2分探索木を探索する時、探索に掛かる最悪の場合の時間計算量（以下、最悪時間計算量というのはO(<ア>)
あ:N 合ってましたが当てずっぽです。
プログラムの再起呼び出し処理を除くと、関数searchのステップ数はnの大小によって変わりませんの。したがって関数searchが一回のみ呼び出され、かつ再帰呼び出しをしなかった場合の最悪計算量はO(1)です。
ちょっと分かりません。
最悪時間計算量とは、そのアルゴリズムにおいて所要時間が最大の場合の計算量のことを言います。本文中で「ノードの総数がn個の2分探索木を探索するとき」とあるので
2分探索木のノードの数に依存する。さらに追加分の葉を合わせてるとO(n+1)になる。
しかしオーダ記法では定数項を無視するのでnが入る。
全ての葉の深さが等しい完全な2分探索機であれば、最悪時間計算量はO(<イ>)となる
n個のノードからなる完全２分木の高さは2^p = n + 1をみたすp、すなわち底を２とするn+1の対数になるので(log(n+1)+1)
深さ分の処理回数だから対数を使って深さを求めれば答えが出るのか。
(log(n+1)+1)
回転操作を利用した並行2分探索期の構成
条件Bal：すべてのノードについて左右の部分木の高さの差が１以上
W：Balを満たす2分探索木
W’：insert関数を使われたWのこと
W'の高さの差が２になるのでBalを満たさなくなる。
その時に図７、８の関数で図５、６の関数を使いBalを満たすようにする
手順
(1)
Tの左側の部分木の高さがTの右側の部分木の高さより２大きい場合
Tを根とする部分木に対して右回転を行う。
ただし、Tの左側の子ノードUについて、Uの右側の部分木の方がUの左側の部分木よりも高い場合は、先にUを根とする部分木にして左回転を行う。
(2)
Tの右側の部分木の高さがTの左側の部分木の高さより２大きい場合
Tを根とする部分木に対して左回転を行う。
ただし、Tの右側の子ノードVについて、Vの左側の部分木の方がVの右側の部分木よりも高い場合は、先にVを根とする部分木に対して右回転を行う。
function balance(t)
h1 <- height(t.left) - height(t.right) # Tの左側の部分木の高さがTの右側の部分木の高さを計算している
if(<ウ>) # h1の結果次第で処理が変わる。
h2 <- <エ>
if(h２が０より大きい）
t.left <- rotateL(t.left) # ノードTの左右の子要素を左回転させる
endif
t <- rotateR(t) # 右回転を行う
elseif(<オ>)
h3 <- <カ>
if(h３が０より大きい）
t.right <- rotateR(t.right) # ノードTの左右の子要素を右回転させる
endif
t <- rotateL(t)
endif
return t
endfunction
h１とは（ウ）
ifとelseifの条件分岐は上の（１）、（２）に分けることがよむことで理解できる。
最初の右回転を行う条件はTの左側の部分木の高さがTの右側の部分木の高さより２大きい場合だ。
ノードTの左右の部分木（子）の深さを調べ比べている。
上の処理がh1 <- height(t.left) - height(t.right)で表されている。
h1は、左右の部分木（子）の高さの差を表している。 左が大きければ正、右が大きければ負、等しければ０ということになる。
Tの左側の部分木の高さがTの右側の部分木の高さをh１で表せるためh1が２より大きければ良いので
h1は２と等しいが答えだと思う。
h2とは（エ）
h2は一つの処理のもう一つの条件分岐の条件に使われる変数だ。
その条件というのはTの左側の子ノードUについて、Uの右側の部分木の方がUの左側の部分木よりも高い場合、h２が０より大きいだ。
結果は右が大きければ正、左が大きければ負、等しければ０だ。
h2はノードTの部分木（子、左）のそのまた部分木（右、左）の高さの差を表す。
Tの左の子の右はt.left.right、左はt.left.left
h2はheight(t.left.right)-height(t.left.left)
オ、カ
Tの右側の部分木の高さがTの左側の部分木の高さより２大きい場合なので
オ:h1は-2と等しい
Tの右側の子ノードVについて、Vの左側の部分木の方がVの右側の部分木よりも高い場合なので
カ:height(t.right.left)-height(t.right.right)
キ
条件Balを満たすノードの総数がn個の2分探索木に対して関数insertBを実行した場合、挿入に掛かる最悪時間計算量はO(<キ>)となる。
function insertB(t, k)
if(tがNULLと等しい）
t <- new Node(k) # 根がNULLならばノードを生成
elseif(t.keyがkより大きい)
t.left <- insertB(t.left, k)# t.key(根)
elseif(t.keyがkより小さい）
t.right <- insertB(t.right, k)
endif
t <- balance(t)
return t
endfunction
時間計算量とは
アルゴリズムの実行時間を表す尺度で、正確にはこれを時間計算量といいます
n個の2分探索期の挿入の処理に掛かる時間を求める。
N
図１の2分探索木の根を参照する変数をrとしたとき、次の処理を行うことで生成される2分探索木は図１に倣って表現すること。
insertB(insertB(r,4),8)
トレースをやると正確にできる
左回転させる関数
fundtion rotateL(t)
a <- t.right # ノードTの右の子
b <- a.left # ノードTの左の子
a.left <- t # ノードaにノードTを左の子へ
t.right <- b # bをtの右の子へ
return a
endfunction
ノードを代入するときはそのノードの子まで代入されることを忘れないようにしよう。
イライラした。
条件Balを満たすノードの総数がn個の２分探索木に対して関数insertBを実行した場合、挿入にかかる最悪時間計算量はO(<キ>)となる。
全てのノードについて左右の部分木の高さの差が１以下という条件（以下、条件Balという）
log(n)だと思った。
それは一番多く処理をするのは一番深いノードだからだ。
感想
簡単なんだろうけど難しかった。