二分木の配列表現を深さ優先順で無駄なく行う方法

最近レイトレでBVHという空間分割手法を実装していたのですが, そこで 二分木を連続したメモリ領域上に深さ優先順かつ無駄なく表現するにはどうすれば良いのか という問題に遭遇しました。色々考えた結果、ノードが持つ情報と木の構築アルゴリズムにちょっとした工夫をするだけでうまくできたので、その方法について紹介したいと思います。なおここで紹介する方法は二分木だけではなく、 $n$ 分木にも応用することができると思います。

背景

二分木はよくある実装例だと以下のように親ノードから子ノードへのポインタを経由して表現することが多いです。

struct Node {
  Node* leftChild; // 左側の子ノードへのポインタ
  Node* rightChild; // 右側の子ノードへのポインタ
};

これとは別に配列で二分木を表現することも出来ます。よくあるのは親ノードのインデックスを $i$ とした時、左側の子ノードを $2i + 1$ 、右側の子ノードを $2i + 2$ の位置に格納する方法です。

この方法はシンプルですが、木が完全二分木でないと配列の全ての要素が使われずに無駄が出来てしまいます。例えば以下のような例です。

ノード数が多い場合には事前に用意する配列のサイズもどんどん大きくなっていって大変になります。

解決策

以下では 二分木を深さ優先順で配列に無駄なく格納する方法 について考えていきます。

まずメモリ領域の無駄をなくすにはノードをとりあえず作成順に配列に突っ込んでいくことで解決できます。例えばstd::vectorのpush_back()などを使ってノードを配列に突っ込んでいきます。

ただしこれだけでは右の子へのアクセスができません(一方で左の子は親ノードの次の要素になるので容易にアクセスできる)。例えば以下の図ではAの左の子であるBの位置はA作成時に確定しますが、右の子であるCの位置はA作成時には不明です。

右の子の位置は左の部分木を構築し終わった後に確定します。これをどうやってAにセットするかが問題ですが、木の構築の再帰呼び出しの前後 に注目することで以下のように解決できました。

まずノードを表す構造体に右の子ノードへのインデックスを追加します。

struct Node {
  T value; // ノードが持ってる何らかの値
  int rightChildOffset; // 右の子ノードへのインデックス
};

ここで左の子ノードへのインデックスは深さ優先順で格納する場合は先程の図のように親ノードの次の要素になるので省略できます。

続いて木の構築アルゴリズムを次のようにします。C++ライクな疑似コードで示します。ノードの配列はnodesという名前で与えられているとします。

// 木を再帰呼び出しで構築する
buildTree(...) {
  Node node;

  // 何らかの処理
  ...

  // まずはrightChildOffsetをセットしない状態でノードを配列に追加
  nodes.push_back(node);
  // 親ノードの位置を覚えておく
  const int parentOffset = nodes.size() - 1;

  // 再帰呼び出しによって左の部分木を構築
  buildTree(...)
  // この時点で右の子ノードの位置が確定

  // 親ノードに右の子ノードへのインデックスをセット
  nodes[parentOffset].rightChildOffset = nodes.size(); 

  // 再帰呼び出しによって右の部分木を構築
  buildTree(...)
}

このコードのポイントは以下の3点です。

親ノードを作ったらrightChildOffsetをセットせずにとりあえず配列に突っ込む
左の部分木を作成する前に親ノードの位置を覚えておく
左の部分木を構築し終わったら親ノードにアクセスしてrightChildOffsetをセット

再帰呼び出しの前後に注目することでいい感じに解決出来ました。再帰呼び出しは普段使うときは前後に処理挟んだりしないのですが、こういう使い方にも慣れると色んなことが出来そうですね。