応用情報技術者 試験情報＆徹底解説

平成27年秋期 午後問3(2分探索木)についての質問なのですが、

①図2のsearch関数について、プログラム中にはp.key,p.left,p.rightとあるため、pはNode型の構造体と思われるのですが、6行目には「return p」と記載されており、構造体そのものを返却するというように取れます。(「探索が成功した場合は見つかったノードへの『参照』を返し」と矛盾しているように思います)
これは、newを使って「生成した構造体への参照が戻り値となる」のことでしょうか？

②「2分探索木からのノードの削除」について、以下は図4のremoveNode関数で対応できますか？
・図1の2分探索木に、アの「11」を追加した後、仮に「16」を追加した後の2分探索木で、「25」を削除する場合

上記2点について、どなたかご回答頂ければ幸いです。
宜しくお願い致します。

①について
pは構造体への参照ですね。ノードpの構成要素にアクセス（参照）するにはp.key,p.left,p.rightとしなくてはならないので。上手く説明できないので構造体について調べてみてください。
>これは、newを使って「生成した構造体への参照が戻り値となる」のことでしょうか？
pはすでに生成された構造体の実体なので、newは関係ありません。
②について
>図1の2分探索木に、アの「11」を追加した後、
この状態が図1ということでいいですかね？（ノードのキー値は重複しないものとしているので）
>仮に「16」を追加した後の2分探索木で、「25」を削除する場合
「16」は「20」の左子ノードになります。削除する「25」の左部分木で最大なのは「20」なので、「25」の位置に「20」が、その左子ノードが「16」となります。

Chihiro様
ご回答ありがとうございます。

①について、「pは構造体への参照」というのは理解できました。
(後になって気が付いたのですが、「変数pが参照するノードをノードpという」と記載されていました…)
「pはすでに生成された構造体の実体」とのことですが、問題文やプログラムに根拠となる箇所はございますでしょうか？

②について、
>図1の2分探索木に、アの「11」を追加した後、
>>この状態が図1ということでいいですかね？（ノードのキー値は重複しないものとしているので）
はい。その認識で問題ございません。

ご回答についてですが、①が解決次第、私の方でも確認してみます。
(図1の2分探索木と[2分探索木からのノードの削除]に記載の内容を確認しましたが、(3-1)(3-2)は説明文とプログラムから理解できたのですが、(3-3)は①が解決しないと分からなさそうです…)

不明点がございましたら連絡するかもしれませんが、よろしくお願い致します。

この投稿は投稿者により削除されました。(2022.03.06 19:15)

訂正します。
>「pはすでに生成された構造体の実体」とのことですが、問題文やプログラムに根拠となる箇所はございますでしょうか？
二分探索木の中にすでに実体として存在するノードへの参照を返す（なければnullを返す）ので、新たに生成した実体への参照を返すというわけではありません。根拠があるというよりは、問題中に実体を新たに生成していると思われる箇所が存在しないのです。

Chihiro様

ご回答ありがとうございます。
返信遅くなり申し訳ございません。
(当方社会人なので、学習の時間が少なく、返信が遅れてしまいました…)

①について、私の方でトレースしてみました。
確認ですが、新しくノードを生成する(「p←new Node(k)」の行を実行する)際には、呼び出し前はnullであった構造体への参照を、メモリ上のどこかに生成された新たな構造体への実体を参照することにより、ノードの挿入を実現しているという認識なのですが、正しいでしょうか？

②についてもトレースしてみたのですが、extractMaxNode関数を呼び出す際にpの値が更新されるためなのか、図4でextractMaxNode関数を呼び出している行のトレースがうまくできませんでした…。

大変恐れ入りますが、本行以降の処理内容についてご教授頂ければ幸いです。
よろしくお願い致します。

>新しくノードを生成する(「p←new Node(k)」の行を実行する)際には、呼び出し前はnullであった構造体への参照を、メモリ上のどこかに生成された新たな構造体への実体を参照することにより、ノードの挿入を実現しているという認識なのですが、正しいでしょうか？
関数addNodeのことでしたら、それで合っています。
トレースについては次の投稿で説明します。

以下、15や25などの数字は、その数をキー値にもつノードへの参照とします。
例  p←25  の25はキー値が25のノードへの参照
・キー値が25のノードの削除
removeNode(25,15)
p≠nullかつk>p.key(25>15)より
p.right←removeNode(25,25)…①
・removeNode(25,25)
p≠nullかつk=p.keyよりelse
左右部分木ともに存在するためelse
p.left←extractMaxNode(p.left=20)…②
・extractMaxNode(20)
p.right(20の右部分木）=nullなので、extractNode←20,p←p.left=16
return p(=16)で②に戻る

p.left←extractMaxNode(20)=16（returnで返却されたp）
r←extractedNode=20（前の投稿のextractNodeは誤記です）
r.left←p.left=16
r.right←p.right(25の右子ノード)=30
p←r
return p(=20) で①に戻る
p.right←removeNode(25,25)=20（returnで返却されたp）//15の右子ノードになる
return p
endfunction

Chihiro様

①については解決できました。
②についてですが、申し訳ございませんが、No.9の2～5行目にコメントを付けていただけますでしょうか？

実際に2分探索木を書いてみて確認する方が良さそうでしょうか…

返信が遅れました。No.9の投稿についてもう少しコメントで掘り下げます。

//removeNode(25,25)の処理の続き
p.left←extractMaxNode(20)=16 //extractMaxNode(20)=returnで返却されたp=16
r←extractedNode=20 //extractMaxNode(20)の処理でextractedNode←20とした
r.left←p.left=16 //2行上の処理 p.left←extractMaxNode(20)=16より
r.right←p.right=30 //ここでのpは25(removeNode(25,25)の引数p)、25の右子ノードは30
p←r //p:左子ノード16、右子ノード30である値20のノード
return p(=20) //removeNode(25,15)の続きに戻る

//removeNode(25,15)の処理の続き
p.right←removeNode(25,25)=20 //ここでのpは15(removeNode(25,15)の引数p)
return p //p:右子ノード20である値15のノード(左子ノードは8のまま変わらず)

Chihiro様
コメントの追記ありがとうございます。
こちらも気付くのが遅くなり大変申し訳ございません。

頂いたコメント通りにトレースし、何とか期待通りの二分探索木にはなったのですが、
本質的な理解には至っておりません…

そこで、2点お聞きしたいのですが、
[1]キを「p←r」と正しく解答するには、どのようなプロセスで考えていけばよいか。
[2]プログラムの途中でトレースが難しいと感じた場合は、その設問/大問は捨てるべきか。
(問題の内容から脱線した内容で恐縮です。Chihiro様としてのご意見をお聞きできれば幸いです)

以上、よろしくお願い致します。

スレ立てから丸1週間経過すると新規の投稿があってもトップの新着に上がってこない？仕様があるのか、それが原因で気づくのが遅れました。申し訳ありません。

[1]キの前3行でrの設定を行っていますが、それ以外でrについて何か処理を行っている箇所が見当たりません。このままではrは利用されることがないので、キでrに関する何かしらの処理を行うんだなと見当がつきます。rは差し替える用のノードであり、プログラムの最後に return p とあるので、p←rとすればノードの差し替えができるとわかります。
[2]プログラミングに限りませんが、問題を一見して理解できないような大問は（たとえ設問は簡単であったとしても）捨てますし、難しい、時間のかかりそうな設問は飛ばします。別に満点をとらなければいけない試験ではないので。

chihiro様
ご回答ありがとうございます。
[1]こういう考え方があったのですね。
まだ使用されていない値と関数の戻り値をヒントに答えを導き出すのは良い方法かもしれないです。
ご回答ありがとうございました。
[2]プログラミングについては国語力があまり必要ではない(?)ので、本番ではプログラミングを選択する予定ですが、やはり、問題が自分と相性が良いかを見極める必要があるのですね…
参考にさせていただきます。

最初の質問である②については、(スレッドが古いのでそろそろ終了させようと考えているので)残念ながら本スレッド内では本質的な理解に至らせることはできませんでしたが、丁寧に回答していただいたchihiro様には感謝申し上げます。
私は4/16の試験を受験する予定ですが、この試験が受からなかった場合、どこかのタイミングでリベンジしようと考えています。
ご回答ありがとうございました!

PS:今までchihiro様のことを「Chihiro様」とCを大文字にして呼んでしまっていました。
大変失礼致しました。