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

Question

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

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

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

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

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

Answer 1

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

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

Answer 2

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

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

Answer 3

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

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

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

Answer 4

Существует простой способ, если вы хотите сохранить свое дерево в массиве. Вместо того чтобы каждый узел имел указатели на свои левые и правые дочерние элементы, дочерние элементы узла 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.