Binärbäume: Ermitteln des Pfads eines Elements aus seiner Signatur

Question

Angenommen, Sie haben einen Binärbaum, der Bilder klassifiziert. Jeder Knoten ist ein anderer binärer Test. Wenn ein Bild dem Baum zugeführt wird, wird ein eindeutiger Pfad durch den Baum erzeugt.

ist ein Pfad als Binärwort beschrieben, die so lang wie die Tiefe des Baumes ist.

Zum Beispiel für einen 2-stufigen Binärbaum, wobei ein Beispiel Pfad wäre (0,1) ((links, rechts), wodurch in dem zweiten Blatt des Baumes endend von links).

Wir gehen auch davon aus, dass für jedes Bild auf dem Baum zugeführt wird, werden alle Knotentests ausführbar sind. So können wir für jedes Bild eine Signatur definieren: Diese Signatur ist ein Binärwort, dessen Länge die Anzahl der Knoten ist.

Zum Beispiel für einen 2-stufigen Binärbaum, wäre ein Beispiel für Unterschrift seines s = {0,1,1}

s[i] das binäre Ergebnis aus dem Test des i-ten Knoten ist.

Ich bin auf der Suche nach einer Möglichkeit, den Pfad eines Bildes aus seiner Signatur zu erhalten.

A naive Art und Weise tun von Index zu Index der Unterschrift mit den entsprechenden abnehmenden Sprung Länge springen würde.

Allerdings frage ich mich, ob es eine bitweise Berechnung sein könnte, die das Ergebnis liefern könnte (Der Indizes in der Signatur neu organisiert werden kann, falls erforderlich).

Ist das möglich? Wenn ja, wie?

Answer 1

Mit 1 Stufe gibt es 1 Test.

Mit 2 Stufen gibt es 1 + 2 Tests.

Mit 3 Stufen gibt es 1 + 2 + 4 Tests.

Mit 4 Stufen gibt es 1 + 2 + 4 + 8 Tests.

Mit 5 Stufen gibt es 1 + 2 + 4 + 8 + 16 = 31 Tests.

Ein Ansatz zur Berechnung des Pfades schneller wird das erste Bit zu testen und dann den entsprechenden Satz von 15bits zu extrahieren, die auf die nächsten 4 Stufen zuzuordnen. Es gibt nur 2 ** 15 = 32768 verschiedene Auswahlmöglichkeiten, so dass der Pfad in einer Tabelle nachgeschlagen werden kann.

Pseudocode:

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

Lookup ist ein 2 ** 15 Länge Array, das Sie vorberechnen können.