HOME»応用情報技術者試験掲示板»H27秋午後のプログラミング
投稿する
[1492] H27秋午後のプログラミング
T.S.さん(No.1)
https://www.ap-siken.com/kakomon/27_aki/pm03.htmlの
空欄キの正答は「p←r」となっていますが、
もし、削除するノードの左部分木の中で最大値のキーを持つノードが
削除ノードの左の子ノードだった場合、図4によると、p.leftとrが
同じノードになってしまうのでしょうか？
extractMaxNode(p.left)とextractedNodeが同じ値になると思いましたので…。
空欄キの正答は「p←r」となっていますが、
もし、削除するノードの左部分木の中で最大値のキーを持つノードが
削除ノードの左の子ノードだった場合、図4によると、p.leftとrが
同じノードになってしまうのでしょうか？
extractMaxNode(p.left)とextractedNodeが同じ値になると思いましたので…。
2019.03.13 23:05
助け人さん(No.2)
★AP ゴールドマイスター
削除するノードの左部分木の中で最大値のキーを持つノードが削除ノードの左の子ノードだった場合です。
図4から抜粋
① p.left ← extractMaxNode(p.left)
② r ← extractedNode
図5から抜粋
③ if(p.rightとnullが等しい)
④ extractedNode ← p
⑤ p ← p.left
⑥ return p
②のrは、④により「削除ノードの左の子ノード」です。
①の右(代入元)のp.leftは、rと同じく「削除ノードの左の子ノード」ですが、左(代入先)のp.leftは、⑤により(p.left).leftですから、「削除ノードの左の子ノード」の左の子ノードです。
図4から抜粋
① p.left ← extractMaxNode(p.left)
② r ← extractedNode
図5から抜粋
③ if(p.rightとnullが等しい)
④ extractedNode ← p
⑤ p ← p.left
⑥ return p
②のrは、④により「削除ノードの左の子ノード」です。
①の右(代入元)のp.leftは、rと同じく「削除ノードの左の子ノード」ですが、左(代入先)のp.leftは、⑤により(p.left).leftですから、「削除ノードの左の子ノード」の左の子ノードです。
2019.03.14 09:42
T.S.さん(No.3)
ご回答ありがとうございます。
関数のプログラムを読む際には、引数を置き換えて、考えるようにします。
関数のプログラムを読む際には、引数を置き換えて、考えるようにします。
2019.03.14 21:05