バイナリツリー：署名から要素のパスを取得する

Question

イメージを分類するバイナリツリーがあるとします。各ノードは異なるバイナリテストです。イメージがツリーに供給されると、ツリーを通る一意のパスが生成されます。

パスは、ツリーの深さと同じ長さのバイナリワードとして記述されます。

たとえば、2段階バイナリツリーの場合、パスの例は（0,1）（（左、右）となり、左から2番目の葉に終わります）。

また、ツリーにフィードされている画像では、すべてのノードテストが実行可能であると仮定します。したがって、任意の画像に対して署名を定義することができます。この署名は、長さがノードの数であるバイナリ語です。

例えば、2段のバイナリツリーに対して、署名の例はs = {0,1,1}

s[i]は、i番目のノードの試験からバイナリ結果であろう。

私は、その署名から画像のパスを取得する方法を探しています。

これを実行する素朴なやり方は、適切な減少する閏ランス長で署名のインデックスからインデックスへジャンプすることです。

しかし、結果が得られるビット単位の計算ができるかどうかは疑問です（必要に応じて、シグネチャ内のインデックスを再編成できます）。

これは可能ですか？はいの場合、どうですか？

Answer 1

1段階では1回のテストがあります。

2段階では、1 + 2のテストがあります。

3段階では、1 + 2 + 4のテストがあります。

4段階では、1 + 2 + 4 + 8テストがあります。

5段階では、1 + 2 + 4 + 8 + 16 = 31のテストがあります。

パスを高速に計算する方法の1つは、最初のビットをテストし、次の4つのステージに対応する15ビットの対応するセットを抽出することです。わずか2 ** 15 = 32768の異なる選択肢しかないので、パスをテーブルで参照することができます。

擬似コード：

if (x&(1<<30)) 
    x >>= 15; 
path = lookup[x & 0x7fff]; 

ルックアップはあなたが事前計算することができます2 ** 15の長さの配列です。