Как ссылаться на детей в дереве с миллионами узлов

Question

Я пытаюсь построить дерево, в котором у каждого узла может быть неопределенное количество дочерних узлов.Дерево должно иметь на практике более миллиона узлов.

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

Есть ли еще однаспособ сделать это?Я не могу просто использовать переменную для хранения ссылки на дочерние элементы, поскольку для каждого узла может быть неопределенное количество дочерних элементов.Таким образом, это не похоже на двоичное дерево, в котором я мог бы иметь 2 переменные, отслеживающие левого и правого дочерних элементов соответственно.

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

Спасибо!

Answer 1

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

Если вы не нуждаетесь в для поиска детей как карты, я бы использовал List<T> (инициализированный с соответствующей емкостью) вместо Dictionary<,> для детей. Похоже, что у вас может быть больше требований, чем вы объяснили, но это трудно сказать.

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

Я бы также предположил, что если вы думаете, что в конечном итоге будете использовать много памяти, убедитесь, что вы работаете на 64-битной машине, и убедитесь, что само ваше приложение установлено на 64-битную. (Это может быть просто тонкая оболочка над библиотекой классов, что хорошо, если для библиотеки классов установлен 64-разрядный или AnyCPU.)