令和5年秋期試験 午後問3(プログラミング)についての投稿を受け付けるスレッドです。

エオが分からなくなって t.left.rightみたいに構造体繋げてしまいました…

それだめなん？そうしたわ...

おちたかもさん、いや、同じことしました笑笑
他に記載方法あったんですかね(問題も見返す気にならない、)    あれだけ回答スペースあったので合ってそうだなと思って進めました

オーダの計算分からなくて違う問題に変えてしまった...  あの3問結局答えなんなんですか？

オーダーわからなかったから、知ってるのてきとーに書いた
log2n,n,log2nにした気がする

俺もheight関数の中で構造体繋げた

この投稿は投稿者により削除されました。(2023.10.08 16:00)

皆さんが同じような回答されてて安心しました

計算量は N logN N^2にしました
確か定数は取り除くみたいなルールがあったはずなので…

オーダは
n, logn, logn

基本情報技術者試験24年秋問3ではオーダlog2nとしているのですがどっちなんでしょうか。

どっちでも良かった気がします

ア N
イ logN
ウ h1が2に等しい
エ height（t.left.right）-height（t.left.left）
オ h1が-2に等しい
カ height（t.right.left）-height（t.left.right）
木 5,3,6,1,4,9,8の順？
キ logN

みたいな感じでした
去年やらかしてるのに懲りずに選んで後悔してます  耐えてるといいな...

カの2項目右右

lognだと自然対数になる気がするからlog2nじゃないかな

logのオーダーどっちでもいいマジですか！
終わってから気づいて悔やんでたのですが

すんません、オーダーn,log2n,log2nにしてました

零点さんとキ以外全部一緒でした。logは底まで書きましたが

今回は0点回避してそうで少しほっとしました
ありがとうございます

2より大きい、-2より小さい  って書いちゃいました...

問題文の高さより2大きいって表したとき>こういうことになるふうに感じたんですけど以上とかの書き方が普通じゃないんですか？

最後、幅優先で5,3,8,1,4,6,9ですか？
         5
        3 8
      1 4 6 9

kさんと同じ答えになりました
丁寧にコードをトレースした結果、高さの低い二分探索木ができてそりゃそうかという気持ちに

            ５
    ３            ６
１      ４              ９
                  ８       

になりました。

「キ」の解答はlog(2)Nなの？？
最後の行でbalance(t)してるから結局Nのままかと思っちゃった...

時間計算量の書き方がわからなくて、最初はnと書いていたのにn×searchとか関数名をかけちゃいました……

ウとエについてですが
    ウ: h1が1よりも大きい
    エ: h2が-1よりも小さい
は正解でしょうか、、、

ワタシの回答は
ウ：h1が2以上
エ：h1が-2以下
だったので、激ナエトルさんの解答でもいいと思いますね。

最後の問題log2n＋2と書きました
balanceでUとTの回転の判定に2回いるのかなと思って…

[回転操作を利用した平衡2分探索木の構成](1)(2)を読む感じ、以上以下じゃなくて=だと思うんですけどどうなんでしょうね

確認したけど、イコールでしたわ。

ア n
イ log2 n
ウ h1が1より大きい
エ height(u.right)-height(u.left) ※u=t.left
オ h1が-1より小さい
カ height(u.right)-height(u.left) ※u=t.right
木     5
      3   6
    1 4 8 9
キ log2 n


こんな感じにしました、、、

n
logn
h1＝2
略
h1＝-2
略
略
logn

計算量の問題なんですけど、nをNで記載したんですけどダメですかね。

h1≧2
h1≦-2
という風に記述しちゃったんですが点貰えますかね？

底は2って書かないとダメだろうか
応用情報過去問でも午前ではlognの時があったし表記揺れてて不安やなぁ

ウ:h1が2
オ:h1が-2
これって点もらえますかね？

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

最後の問題
logn^2にしちゃいました...

底については計算量は定数倍を考慮しないはずなのでなんでもいいと思うのですが…

オーダー大文字にしちゃいました…

ウとオってイコール記号使っちゃうと誤答ですかね

前提条件にある通り、Balを満たす探索木にノードを挿入した場合、左右の高さの差の絶対値は2より大きくなることはないので、ウおよびオはh1と2が等しい、h1と-2が等しいがそれぞれ正解だと思います。

logの底については数学的に考えれば底は2であると書くべきですが、過去問の解答では省略しても良さそうなので、どちらでも正解だと思ってます。。

エとカ、零点さんと同じで以下にしました！
uはプログラム上で定義されていないのでtを元に書くので合ってますかね…？(tは引数で渡しているから使える認識)

エ height（t.left.right）-height（t.left.left）
カ height（t.right.left）-height（t.left.right）

カの2つ目の項はright.rightでは？

>あいうさん
おっしゃる通り、right.rightですね！

定数倍は考慮しないので底の値は書かなくても問題はないと思っています
底が2だろうがeだろうが定数倍の違いでしかないので
書くなら勿論2一択ですが

2に等しいじゃなくて以上以下でも問題なく動きますよね？
正解にしてくれないかなあ

図5のプログラ厶を見ると
a.left.leftのような書き方をしても良いと
暗に言っているので
繋げちゃいましたね

図を書く問題
完全平衡二分木にはならなかったです
問題文にも完全ではなくとも比較的左右均等という文言があったので特に違和感もなくそれで回答してしまいました
書くの面倒なんですがレーザさんのと多分同じです

自分も以上以下にしてしまった、、  間違いとは言えませんよね、、

木を書く問題なんですが、キー値4をinsertした段階で右回転して
ルートが3になってるんですが、なぜ皆さん5になられてるんでしょうか?
もしかして私根本的な部分理解できてなかったか？

h1は1より大きい、-1より小さいって書いちゃったなあ 多分プログラム的には問題なく動くんだろうけど2以上-2以下って書かないと×にされそう

＞完全二分さん
4をinsertした時、6の左側の部分木のルートが3から5に変わるはずです！

1.
ア:n  イ:log2n(※2は底)
2.
(1)
ウ:h1が2以上
エ:height(t.left.right)-height(t.left.left)
オ:h1が-2以下
カ:height(t.right.left)-height(t.right.right)
(2)
        ５
      ／  ＼
    ３      ６
  ／  ＼      ＼
１      ４      ９
              ／
            ８        
(3)log2n(※2は底)

2.(2)が綺麗な二分木になってる方、なんで上記の木にならないかまで分かる方いたら教えてください…

その場合6を根とする部分木の左右の高さの差が2なのでまだバランス出来ますね
バランスを適用すれば皆さんの回答のようになると思います

自分はこうなったんですが同じ人いませんか…
 
5
36
1○49
で8は9の左下です

今やり直したらみなさんと同じようになりました
あーもったいないミス…

insertB(r,4)の部分
まず挿入ですが、再帰的に⑥→③→⑤と辿って⑤の左下に④が付きます。
次に再帰を抜けるときに、帰りがけ順で木のバランスをしていきます。
・④の左右の部分木は無いので何もしない
・⑤の左部分木は④、右は無しで、高さの差1なので何もしない
・③の左部分木は①、右は⑤④で、高さの差－1なので何もしない
・⑥の左部分木は③①⑤④、右は⑨で、高さの差2なので右回転します
ただし、⑥の左の子③について、③の右部分木(⑤④)の方が左部分木(①)よりも高いので、
先に③を根とする左回転をします。その結果が
            ⑥
          ／  ＼
        ⑤      ⑨
      ／
    ③ 
  ／  ＼
①      ④
これで⑥を根とする右回転ができて、その結果が
        ⑤
      ／  ＼
    ③      ⑥
  ／  ＼      ＼
①      ④      ⑨

insertB(～,8)の部分
⑤→⑥→⑨と辿って⑨の左下に⑧が付きます。
・⑧の左右の部分木は無いので何もしない
・⑨の左部分木は⑧、右は無しで、高さの差1なので何もしない
・⑥の左部分木は無し、右は⑨⑧で、高さの差－2なので左回転します
ただし、⑥の右の子⑨について、⑨の左部分木(⑧)の方が右部分木(無し)よりも高いので、
先に⑨を根とする右回転をします。その結果が
        ⑤
      ／  ＼
    ③      ⑥
  ／  ＼      ＼
①      ④      ⑧
                  ＼

⑨
これで⑥を根とする左回転ができて、その結果が
        ⑤
      ／  ＼
    ③      ⑧
  ／  ＼  ／  ＼
①    ④ ⑥    ⑨
・⑤の左右の部分木は高さが等しいので何もしない
多分こうだと思います！

8の挿入後、
6の木をバランスさせるのを忘れてました。なので、
no.22のkさんのであってると思います。

こしょうさんの通りだと思います。

>こしょうさん(No.60)
>・⑥の左部分木は無し、右は⑨⑧で、高さの差－2なので左回転します
なるほど。⑤の木だけ見てました…。
確かに、⑥の木を見るとその後の処理が必要なわけですね。ありがとうございます！

最後、最悪計算量の木は任意の葉でないノードについて左側の部分木の高さが1大きい感じになる気がするので仮に定数倍を考慮するとフィボナッチ数からlogの底は2ではなくおよそ黄金数になります

最初の設問の「イ」の解答、自分は「log2n」と書きました。
でもTACの解答例は「logn」…。
自分が使った参考書には2分探索木は「log2n」、どれが正しいんですかね？

オーダー記法の中には定数倍は考慮しないというルールがあるらしいです。
O(log2n)
log2n＝logn/log2だから  定数倍の1/log2は消え去ったのだろう要するにどっちでもいいってこった

競プロやってたら迷うことも無く定数は消します。
僕の意見では式が間違ってる訳では無いので正解か部分点くらいはもらえると思いますが…どうでしょうね

1.
ア:n  イ:logn
2.
(1)
ウ:h1が2と等しい  ※差が2になるとあるので等しいとしました
エ:height(t.left.right)-height(t.left.left)
オ:h1が-2と等しい ※ウと同じく)
カ:height(t.right.left)-height(t.right.right)
(2)
         ５
      ／    ＼
    ３        ８
  ／  ＼    ／  ＼
１      ４ ６    ９

(3)nlogn  
(insertBの最後にbalance(t)を実行しています。再起呼び出し(lognで辿ったノードの数だけ処理を行っているのでこれかなと…。少し説明の自信が無いですが…。)

解答速報、TACだとlogN 大原だとlog2Nになってますね。

>>シェイクさん
私も2.(3)は nlogn にしました（シェイクさんと同じ理由です）
検索でなく並べ替えになるから普通は次元が上がる気がしますが大手がlognだったので私も自信ないです･･･

こんばんは。

2.(3)について考えてみました。

まず、rotateR(t)の計算回数は
代入4回、左か右Nodeの参照4回、return文1回
で、データの数nに関係なく定数回なので、単に  C  回  とします。

rotateL(t)についても、  C  回

次に、balance(t)の計算回数は、実行されない行も含めても
代入7回、if文の比較4回、減算3回、rotate関数が4回  ＝  4C  回
（height関数は計算無視してよいと書いてある）
などで、この場合も、データの数nに関係なく多めに見積もってもある定数B以下の
計算回数で済むので、  B 回以下の計算量  とします。

このように考えると、insertBの計算回数は、内部のinsertB関数を除いた部分は
代入が定数回、balance関数が1回などで、
やはり、データの数nに関係なくある定数  K回以下  の計算回数ですむと思います。

最後に、insertB関数の呼び出し回数ですが、根から葉へたどる回数すなわち木の高さとなると思います。
完全2分木なら  木の高さをdとすると
n=1+2+2^2+...+2^(d-1)=1*(2^d-1)/(2-1)=2^d-1(等比数列の和の公式)
なので、2^d=n+1より d=log_2(n+1)
今回のように条件Balを満たす木では、木の高さは、最悪でも
log_2(n+1)+1
程度だと思います。

insertB関数1回で、K回以下の計算量としたので、全体の計算量は多めに見積もっても
K(log_2(n+1)+1)
=K{log_2{(n)*(1+1/n)}+1}
=Klog_2(n)+Klog_2(1+1/n)+K
nを十分大きくとると第1項以外は無視でき Klog_2(n)となるので、Kを省略して、
O(log_2n)またはO(logn)
だと思います。

balance(t)関数が追加されて計算回数は増えていますが、定数倍されるだけならオーダ記法上は変わらないと思います。for文やwhile文のような繰り返し部分があった場合は話は変わると思います。

>>レーザさん
ようやく納得できました。
私はbalance(t)がnによるオーダーを持つと勘違いしたまま、insertBの再帰に入り込む気になっちゃってました。
スッキリです、ありがとうございます

t.left.rightのところ、(t.left).rightって書き方してしまったのですが、このカッコついてたらダメですかね、、