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)

削除するノードの左部分木の中で最大値のキーを持つノードが削除ノードの左の子ノードだった場合です。

図4から抜粋
@  p.left ← extractMaxNode(p.left)
A  r ← extractedNode

図5から抜粋
B  if(p.rightとnullが等しい)
C      extractedNode ← p
D      p ← p.left
E  return p

Aのrは、Cにより「削除ノードの左の子ノード」です。

@の右(代入元)のp.leftは、rと同じく「削除ノードの左の子ノード」ですが、左(代入先)のp.leftは、Dにより(p.left).leftですから、「削除ノードの左の子ノード」の左の子ノードです。

2019.03.14 09:42
T.S.さん(No.3)

ご回答ありがとうございます。
関数のプログラムを読む際には、引数を置き換えて、考えるようにします。

2019.03.14 21:05

【返信投稿用フォーム】

お名前(10文字以内)

顔アイコン


本文(2000文字以内)

記事削除用パスワード(8文字以内)

プレビュー

※宣伝や迷惑行為を防止するため当サイトとIPAサイト以外のURLを含む記事の投稿は禁止されています。

投稿記事削除用フォーム

投稿No. パスワード 
© 2010-2019 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop