これは、 Find first null in binary tree with limited memoryのフォローアップです。
ウィキペディアによると、深さ優先検索を繰り返し行うと、最短経路が見つかるとのことです。メモリ内で k ノードに制限され、ツリーへのアクセス回数が最も少ない実装が必要です。
たとえば、私のバイナリ ツリーが次の場合:
0
1 2
3 4 5 6
7 8 9 10 11 12 13 14
また、検索順序よりもメモリの 5 ノードに制限されています。
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
次の読み取りが 7 の場合、3 を再読み取りする必要があります。しかし、次の読み取りが 14 の場合、まだ 3 を再読み取りする必要はありません。解が 14 の場合、アルゴリズムは少し速くなります!
一般的な解決策を探しています。任意のサイズのメモリとノードあたりのブランチ数で機能するもの。