暗黙的なポインターを使用して、van Emde Boas レイアウトを使用して配列に格納される、キャッシュを無視するバイナリ ツリーを実装したいと思います。ツリー内のすべての項目は 32 ビット整数であり、ツリーはかなり大きくなるため、ポインターを格納すると、少なくとも 3 倍のデータが必要になります。
問題は、ノード インデックスが与えられた場合に、左右の子へのポインターを計算するための非反復的な方法を考えられないことです (ツリーを走査している間、あらゆる情報を追跡できます)。多くの論文や講演では、暗黙的なポインターを使用してそのようなツリーを参照していますが、ポインターを計算するアルゴリズムは見たことがありません。それを行う効率的な方法はありますか？