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が同じ値になると思いましたので…。
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ですから、「削除ノードの左の子ノード」の左の子ノードです。
2019.03.14 09:42
T.S.さん  
(No.3)
ご回答ありがとうございます。
関数のプログラムを読む際には、引数を置き換えて、考えるようにします。
2019.03.14 21:05

返信投稿用フォーム

スパム防止のためにスレッド作成日から30日経過したスレッドへの書込みはできません。

その他のスレッド


Pagetop