Iterative Tiefentiefe erste Suche mit begrenztem Speicher

Question

Dies ist ein Nachfolger zu Find first null in binary tree with limited memory.

Wikipedia sagt, dass iterative-Vertiefungtiefe erste Suche den kürzesten Weg finden wird. Ich möchte eine Implementierung, die im Speicher auf k Knoten beschränkt ist und auf den Baum die wenigsten Male zugreifen.

Zum Beispiel, wenn mein Binärbaum ist:

  0 
    1    2 
3 4  5  6 
7 8 9 10 11 12 13 14 

Und ich bin bis 5 Knoten Speicher als mein Suchauftrag begrenzt ist:

mem[0] = read node 0 
mem[1] = read node 1 
mem[2] = read node 2 
mem[3] = read node 3 
mem[4] = read node 4 //Now my memory is full. I continue... 
mem[3] = read node 5 //overwrite where I stored node 3 
mem[4] = read node 6 //overwrite where I stored node 4 

Nun, wenn meine nächste Lese ist 7, ich muss 3 neu lesen. Aber wenn ich mein nächstes Lesen bis 14 mache, dann muss ich 3 noch nicht neu lesen. Wenn die Lösung bei 14 ist, wird dies meinen Algorithmus ein bisschen schneller machen!

Ich suche nach einer allgemeinen Lösung; etwas, das für Speicher beliebiger Größe und Anzahl der Verzweigungen pro Knoten funktioniert.

Answer 1

Wenn Ihre Knoten mit ihren Eltern verknüpft sind und die untergeordneten Elemente eines Knotens immer in der gleichen Reihenfolge aufgelistet werden, können Sie Ihre Schritte verfolgen, ohne sie speichern zu müssen.