Это продолжение до Найти первый ноль в двоичном дереве с ограниченной памятью .
Википедия говорит, что при глубине итеративного углубления первый поиск найдет кратчайший путь. Я хотел бы реализацию, которая ограничена в памяти 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, это сделает мой алгоритм немного быстрее!
Я ищу общее решение; что-то, что будет работать для памяти любого размера и количества ветвей на узел.