HOME»応用情報技術者試験掲示板»H27秋午後のプログラミング
投稿する

H27秋午後のプログラミング [1492]

 T.S.さん(No.1) 
https://www.ap-siken.com/kakomon/27_aki/pm03.html
空欄キの正答は「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ですから、「削除ノードの左の子ノード」の左の子ノードです。
2019.03.14 09:42
 T.S.さん(No.3) 
ご回答ありがとうございます。
関数のプログラムを読む際には、引数を置き換えて、考えるようにします。
2019.03.14 21:05

返信投稿用フォーム

スパム防止のためにスレッド作成日から30日経過したスレッドへの書込みはできません。
© 2010-2024 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop