Должен ли я хранить родительский указатель в узле дерева / графика?

Question

Я разрабатываю древовидную / графическую структуру данных. Это должно быть больше похоже на ориентированный ациклический граф. Одним из требований является поиск пути от корня до определенного узла, что означает, что когда пользователь выбирает узел, путь от корня будет выделен.

Итак, вопрос в том, хранить ли родительский указатель в каждом узле? Или более общий вопрос будет, когда я должен хранить родительский указатель в каждом узле? Каковы преимущества и недостатки?

Заранее спасибо!

пс. указатель родителя == указатель на родительский узел.

Answer 1

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

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

Ваш "путь выделения изкорневое требование может сделать родительские указатели полезными, хотя для этого есть и другие способы.Как правило, следует избегать размещения избыточной информации в структурах данных, пока не будет доказано, что они необходимы по соображениям производительности.

Answer 2

Чтобы развить ответ Кристофера Джонсона: «вам нужно только сохранить указатель на того родителя, который вам нужен».

Помните, что для многих алгоритмов, которые пересекают дерево / граф, во время обхода выпутешествие от родителя к ребенку, так что у вас есть указатель родителя под рукой.Вы можете использовать этот родительский указатель (например, передав его в рекурсивную функцию) вместо того, чтобы оплачивать затраты на его сохранение в своей структуре.

Еще один момент: для общих графиков этот вопрос такой же, как и «следует хранитьвнутренние ребра (в дополнение к внешним ребрам) в моих узлах? "Если вы посмотрите на библиотеку надстрочных графов , вы найдете библиотеку шаблонов, которая дает вам этот выбор во время компиляции.

Answer 3

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

Гораздо проще что-то добавить, чем удалить, когда код используется ...

Но все же полезно иметь в виду несколько потенциальных расширений при проектировании структур данных ...

Answer 4

Затраты на хранение родительского указателя зависят от того, как часто вы обновляете дерево / график и сколько узлов в нем. Затраты на хранение родительского указателя для некоторых алгоритмов зависят от того, как часто они запускаются. Я не могу сказать вам, как часто вы обновляете карту или как часто вам нужен родительский указатель, но я бы советовал реализовать оба варианта и запустить профилировщик или принять какое-то логическое решение, основанное на том, какие операции занимают больше времени. 1001 *