人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

応用情報の平成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

●質問者: Izkgkf0CPUsl85gi0dBq
●カテゴリ:政治・社会
○ 状態 :終了
└ 回答数 : 1/1件

▽最新の回答へ

1 ● 椶櫚

トレースの方法についてですが、実際に数値を当てはめてみて、その流れを追うだけです。せっかく図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


Izkgkf0CPUsl85gi0dBqさんのコメント
わざわざご丁寧にご解説いただきありがとうございます。 じっくり読ませていただきます
関連質問

●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ