Profondeur itérative approfondissement première recherche avec mémoire limitée

Question

Ceci est une suite à Find first null in binary tree with limited memory. Wikipedia dit que la première recherche de profondeur itérative-approfondissement trouvera le chemin le plus court. Je voudrais une implémentation qui soit limitée en mémoire à k nœuds et qui accède à l'arbre le moins de fois possible.

Par exemple, si mon arbre binaire est:

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

Et je suis limitée à 5 noeuds de mémoire que mon ordre de recherche est:

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 

Maintenant, si mon prochain lecture est à 7, j'ai besoin de relire 3. Mais si je fais ma prochaine lecture à 14, alors je n'ai pas besoin de relire 3 pour le moment. Si la solution est à 14, cela rendra mon algorithme un peu plus rapide!

Je suis à la recherche d'une solution générale; quelque chose qui fonctionnera pour n'importe quelle taille de mémoire et nombre de branches par noeud.

Answer 1

Si vos nœuds sont liés à leurs parents et que les enfants d'un nœud seront toujours énumérés dans le même ordre, vous pouvez suivre vos étapes sans avoir à les sauvegarder.