Найти первый нуль в двоичном дереве с ограниченной памятью

У меня есть двоичное дерево, в котором каждый узел может иметь значение.

Я хочу найти узел в дереве, который имеет значение null и находится ближе всего к корню. Если есть два узла на одинаковом расстоянии от корня, подойдет любой. Мне нужно минимизировать количество доступов для чтения к двоичному дереву. Предположим, что рабочая память ограничена всего k узлами.

DFS на глубину k является исчерпывающим, но не найдет ближайший узел, если я сначала не пройдусь по всему дереву. BFS найдет ближайший, но это может привести к сбою, потому что DFS может найти более глубокие нули с той же памятью.

Я хотел бы иметь наименьшее количество доступов для чтения к дереву и найти ближайший нулевой узел.

(В конце концов мне нужно будет реализовать это и в n-путевых деревьях, поэтому общее решение было бы хорошим. Нет доступа для записи к дереву, только чтение.)


breadth-first-search binary-tree depth-first-search
person Eyal    schedule 28.06.2009    source источник
comment
Я предполагаю, что ближайший нулевой узел важнее, чем наименьшее количество чтений?   -  person Richard Watson    schedule 28.06.2009
comment
Не могли бы вы уточнить, как BFS может выйти из строя?   -  person    schedule 28.06.2009
comment
Ричард: Если внутри глубины k есть нулевой узел, я хочу вывести тот, который ближе всего к корню. Если нет, то я терплю неудачу. Паштет: использование памяти BFS увеличивается в геометрической прогрессии. С k памятью я могу добраться до k глубины с DFS, но BFS не может пойти так глубоко. Таким образом, может быть решение, которое можно найти с помощью DFS, но не BFS.   -  person Eyal    schedule 28.06.2009
comment
является ли ваше бинарное дерево полным бинарным деревом?   -  person J-16 SDiZ    schedule 29.06.2009
comment
Для всех практических целей он бесконечен по глубине, а нулевые узлы являются листьями.   -  person Eyal    schedule 29.06.2009

Ответы (4)


arrow_upward
2
arrow_downward

Вы можете ознакомиться с итеративным углублением поиска в глубину. Он автоматически найдет ближайший узел, но сможет достичь той же глубины, что и DFS. Однако он будет использовать больше доступов для чтения.

Вы также можете начать с BFS, и если вы не найдете нуль с разрешенной памятью, запустите DFS.

person Geerad    schedule 28.06.2009
comment
Интересно, есть ли хороший заказ на оптимизацию IDDFS? Например, если у меня в памяти 4 узла, а дерево бинарное, после чтения узлов 0,1,2,3 я могу прочитать узлы 4,5,6, не начиная заново, потому что я уже прочитал 0,1,2. Теперь, если у меня в памяти 0,1,2,6, я могу прочитать 7 без необходимости перечитывать 0,2 и т.д. Придется рисовать, чтобы было понятно... - person Eyal; 28.06.2009
comment
Я не уверен, правильно ли я вас понял, но вам придется использовать память, чтобы отслеживать тот факт, что вы читаете эти узлы, поэтому вы в конечном итоге не лучше, чем BFS. - person Geerad; 29.06.2009
comment
@Geerad: IDDFS нужна меньшая память, чем BFS - вам не нужна явная очередь для DFS. - person J-16 SDiZ; 29.06.2009

arrow_upward
2
arrow_downward

Я бы реализовал DFS с простой обрезкой дерева. Таким образом, утверждение о том, что вам нужно запускать все дерево, неверно.

Например, если вы нашли нулевое значение на высоте h, вы можете пропустить узлы, находящиеся в том же или более глубокое положение.

person Nick Dandoulakis    schedule 28.06.2009

arrow_upward
1
arrow_downward

Если вы не можете изменить структуру данных, вам придется читать каждый узел в ширину.

Если вы можете изменить структуру данных, то каждый узел может записывать относительную глубину первого нулевого дочернего узла. (Каждый из своих дочерних эквивалентных значений).

Тогда вы знаете, какую строку в дереве искать при поиске самого раннего нуля.

person Douglas Leeder    schedule 28.06.2009

arrow_upward
0
arrow_downward

Есть простой способ, если вы хотите сохранить свое дерево в массиве. Вместо того, чтобы каждый узел имел указатели на своих левых и правых дочерних элементов, дочерние элементы узла n равны 2n + 1 и 2n + 2 в массиве. (И родителем узла n является (n-1)/2, если n != 0.)

Node tree[] = { 0, //root
1, // root's left child
2, // root's right child
3, // 1's left child
4, // 1's right child
5, // 2's left child
6, // 2's right child
...,
};

Простая линейная итерация по массиву эквивалентна BFS, но с требованиями к пространству O (1).

Это может быть легко распространено на n-арные деревья. например, в троичном дереве левый дочерний элемент — 3n+1, центральный — 3n+2, правый — 3n+3, а родитель — (n-1)/3, если n !=0.

person Geerad    schedule 29.06.2009