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

Question

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

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

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

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

Спасибо!

Answer 1

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

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

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

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