二分探索木・ヒープの可視化ツール

正解：A. 子は a[9] と a[10]、親は a[1]

根を a[0] とする場合、a[i] の子は a[2i+1] と a[2i+2]、親は a[(i−1)÷2 の切り捨て] です。i = 4 なら子は a[9] と a[10]、親は a[(4−1)÷2] = a[1] です。根を a[1] とする場合は子が a[2i] と a[2i+1]、親が a[i÷2] になるので、どちらの決め方かを確かめることが大切です。このように、ヒープは完全二分木なのでポインタを使わずに配列で表せ、添字の計算だけで親子をたどれます。

正解：C. 50, 30, 45, 10, 20, 35, 40

45は a[6] に置かれ、親は a[(6−1)÷2] = a[2] = 40 です。45 > 40 なので交換して a[2] に移ります。次の親 a[0] = 50 は45より大きいので、ここで止まり、50, 30, 45, 10, 20, 35, 40 になります。交換は木の高さの分しか起こらないので追加は O(log n) で、最大値の取り出しも同じく O(log n) です。この性質から、二分ヒープは優先度付きキューの実装によく使われます。

正解：A. 昇順(小さい順)に並ぶ

二分探索木では、どの節についても、左の部分木の値はすべてその節より小さく、右の部分木の値はすべて大きくなっています。そのため、左の部分木、節、右の部分木の順にたどると、小さい値から順に訪れることになり、結果は昇順になります。根から近い順に並ぶのは、段ごとに左から訪れる幅優先(レベル順)のたどり方です。挿入した順は木の形には残りますが、たどり方の順序とは一致しません。

正解：B. 20, 40, 30, 60, 80, 70, 50

根は50で、左の子は30(その子が20と40)、右の子は70(その子が60と80)になります。後行順では、左の部分木の 20, 40, 30、右の部分木の 60, 80, 70 を訪れてから、最後に根の50を訪れます。50, 30, 20, 40, 70, 60, 80 は節を先に訪れる先行順(行きがけ順)、20, 30, 40, … は中間順(通りがけ順)の結果です。後行順は、子を先に処理する必要がある木の削除や、式の木から後置記法を作るときに使われます。

正解：C. 1,000

昇順に挿入すると、新しい値は毎回それまでの最大値の右の子になるので、木は右にだけ伸びた1本の列(高さ999)になります。1000はいちばん下にあるので、1, 2, …, 1000 の1,000個の節と比べることになり、連結リストを先頭からたどるのと同じ O(n) です。つり合いのとれた木なら段の数は約 log₂ 1000 ≈ 10 なので、AVL木や赤黒木のように挿入や削除のたびに形を整える平衡二分探索木を使えば、最悪でも O(log n) を保てます。