応用情報の平成27年度秋期問3のキがわかりません

どうやってトレースしていけばいいのでしょうか?
特に
p.left ← extractMaxNode(p.left)
r ← extractedNode
r.left ← p.left
r.right ← p.right

がわかりません 教えてください。
ちなみに問題文はこちらにあります。
http://korejoap.info/2016/01/AP27AutumnAfternoonQ3-4.html

回答の条件
  • 1人5回まで
  • 13歳以上
  • 登録:2016/11/22 16:47:28
  • 終了:2016/11/29 16:50:03

回答(1件)

id:jwrekitan No.1

椶櫚回答回数201ベストアンサー獲得回数732016/11/23 06:49:14

トレースの方法についてですが、実際に数値を当てはめてみて、その流れを追うだけです。せっかく図1というものがあるのですからそれを利用しましょう。

例として、8を削除する場合、

function removeNode(k, p) // 受け取る引数は、k=8, p=15(8を削除するための指示)
# p=15なので、p.left=8, p.right=25です。

p.left ← removeNode(k, p.left) // 受け渡す引数は、k=8, p.left=8 ①

function removeNode(k, p) // 受け取る引数は、k=8, p=8
# p=8なので、p.left=2, p.right=10

p.left ← extractMaxNode(p.left) // 受け渡す引数は、p.left=2 ②

と、本来ならここからextractMaxNodeのループに入るようなのですが、図1の構造の場合、8を消してそこに左下の2を持ってくるだけで終了となります。

function extractMaxNode(p) // 受け取る引数はp=2
# p=2なので、p.left=null, p.right=null

extractedNode ← p // extractedNode=2
p ← p.left // p=null
return p // ②に戻ります。返す値はnull

p.left ← extractMaxNode(p.left) // 8のleftはnullで上書きされました ②
r ← extractedNode // r=2
r.left ← p.left // r.left=null(extractMaxNodeの戻り値と一緒)
r.right ← p.right // r.right=10
[ キ ] // ブラックボックスな処理
return p // ①に戻ります。返す値はp

p.left ← removeNode(k, p.left) // ①
# p=15です。つまり、p.left=2になれば処理を終了してもいいという事ですね?
# 模範解答が http://www.ap-siken.com/kakomon/27_aki/pm03.html にあって、
# [ キ ]は p ← r が正解のようです。
# (が、 p ← extractedNode と仮に回答しても減点はされないはず)

行った動作を最後にまとめると、8の左側にある数字のうち一番大きな数字である2を8が元あった位置に挿げ替え、こうして8の削除を達成したという事です。

--------------------------------------------------------

extractMaxNodeでループさせる例として、15を削除する場合、

function removeNode(k, p) // 受け取る引数は、k=15, p=15(15を削除するための指示)
# p=15なので、p.left=8, p.right=25です。

p.left ← extractMaxNode(p.left) // 受け渡す引数は、p.left=8 ①

いきなり条件が合致したので、さっそくループ開始です。

function extractMaxNode(p) // 受け取る引数はp=8
# p=8なので、p.left=2, p.right=10

p.right ← extractMaxNode(p.right) // 受け渡す引数は、p.right=10 ②

function extractMaxNode(p) // 受け取る引数はp=10
# p=10なので、p.left=9, p.right=12

p.right ← extractMaxNode(p.right) // 受け渡す引数は、p.right=12 ③

function extractMaxNode(p) // 受け取る引数はp=12
# p=12なので、p.left=[ ア ], p.right=null

extractedNode ← p // extractedNode=12
p ← p.left // p=[ ア ]
return p // ③に戻ります。返す値は[ ア ]

p.right ← extractMaxNode(p.right) // 10のrightは[ ア ]で上書きされました ③
return p // ②に戻ります。返す値は10

p.right ← extractMaxNode(p.right) // 8のrightは10で上書きされました ②
# といっても、元々10が入っていたところに同じ数字で上書きしただけです
return p // ①に戻ります。返す値は8

p.left ← extractMaxNode(p.left) // 15のleftは8で上書きされました ①
# 実はこれも同じ数字で上書きしただけという

r ← extractedNode // r=12
r.left ← p.left // r.left=8(extractMaxNodeの戻り値と一緒)
r.right ← p.right // r.right=25
p ← r // [ キ ] // pそのものが15から12に上書きされました
return p // ①に戻ります。返す値は12


行った動作を最後にまとめると、15の左側にある数字のうち一番大きな数字である12を15が元あった位置に挿げ替え、こうして15の削除を達成したという事です。その際、12が元あった位置は12のleftにあった[ ア ]に置き換えています。

図1の15を12にし、12を[ ア ]に置き換えて考えてみましょう。

> ・Nの左部分木にある全てのノードのキー値は、Nのキー値よりも小さい。
> ・Nの右部分木にある全てのノードのキー値は、Nのキー値よりも大きい。

という構造条件はきちんと維持されている事がわかります。あとはその下にある設問4の動画を見れば何をしているのかが理解できるのではないかと。

--------------------------------------------------------

この辺の事は私も学んではいないのですが、たぶん2分探索木というのはこういう動作なのだという事で、概念そのものを丸暗記してしまった方がいいのかもしれません。つまりこの問題の意味するところというのは、応用情報技術者ならばこの程度の事は基礎知識として知っていて当然である、という事なんだと思います(PERTなんかと一緒で)。

wikipedia:二分探索木#削除

(二分探索木の性質上、探索ノードには右の子は無い)


メリットとデメリット
http://ufcpp.net/study/algorithm/col_tree.html

id:Izkgkf0CPUsl85gi0dBq

わざわざご丁寧にご解説いただきありがとうございます。
じっくり読ませていただきます

2016/11/23 11:10:31

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません