2分木が配列に格納できるというのは有名だ。 たとえば以下の完全二分木のノード番号をそのまま配列のインデックスにする。 すると$x$番目の要素の子要素はそれぞれ$2x+1, 2x+2$番目と、計算で木をたどることができる。 親要素も$\lfloor(x-1)/2\rfloor$でアクセスできる。 ポインタで要素の関係を表したりせずに、ただ要素の順番だけで木構造が扱えるのだ。 なんかシンプルにかしこくて、自分はこのデータ構造が大好きだ。
ところで、これは2分木に限った話ではない。 2分木と比べると一気に使用頻度が落ちるが、3分木、4分木、5分木、たぶん何分木でも配列で表すことができる。 しかし意外にも「N分木 配列」とかでググってもそれについての話が出てこない（たぶんググり方が悪い）。
自分も今の所使いみちがわからないが、いつか完全N分木をシリアライズしたくなる可能性もあるだろう。 そんなときいちいち考え直さなくてもいいように、ここに配列を使ったN分木の表現法について書いておく。
2分木
2分木についてはググればいっぱい出てくるが、 ハードディスクと共に宇宙に放り出されて情報源がこれしかない人もいるだろう。 まずは2分木の場合についておさらいしておく。
上の画像のように上から下、左から右へ番号をふっていくと、 インデックスが$x$のノードについて以下の情報が得られる。
- 左の子ノード：$2x + 1$番目
- 右の子ノード：$2x + 2$番目
- 親ノード：$\lfloor(x-1)/2\rfloor$番目
親ノードの計算で切り捨てが出てくるが、整数演算なら端数は勝手に切り捨てられる。
実際のコードは(x-1)/2で大丈夫。
3分木
2分木以外の例も試してみる。 まずは同じようにノードに番号をふって、観察してみる。
2分木のときと同じことが言えるとわかるだろう。
- 左の子ノード：$3x + 1$番目
- 中の子ノード：$3x + 2$番目
- 右の子ノード：$3x + 3$番目
- 親ノード：$\lfloor(x-1)/3\rfloor$番目
もっと大きな例
4分木、5分木も一応確認してみる。 だいぶ大きくなってきた。
どうも法則性があるのは確実なようだ。
結論
$N$分木のノードに番号をふった時、$x$番目のノードについて以下のことが言えるはず。
- $i$番目の子ノード$(1 \leq i \leq N )$：$Nx + i$番目
- 親ノード：$\lfloor(x-1)/N\rfloor$番目
上のように図にして確認すればすぐわかることではあるが、 こうしてあらかじめ書いておけば必要な時ぱっと使えて便利。 証明は……どうすればいいのか分からない。 ちゃんとグラフ理論を勉強すれば証明できるようになるだろうか。