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
助け人さん
★AP ゴールドマイスター
(No.2)
削除するノードの左部分木の中で最大値のキーを持つノードが削除ノードの左の子ノードだった場合です。
図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
返信投稿用フォーム
スパム防止のためにスレッド作成日から30日経過したスレッドへの書込みはできません。