Это вопрос задания, на который я затрудняюсь сформулировать ответ.
«Предположим, что дерево может иметь до k дочерних узлов на узел. Пусть v будет средним числом дочерних элементов на узел. Для каких значений v более эффективно (с точки зрения используемого пространства) хранить дочерние узлы в связанный список против хранения в массиве? Почему?"
Я верю, что могу ответить на вопрос "почему?" более или менее на простом английском языке - будет более эффективно использовать связанный список, потому что вместо того, чтобы иметь кучу пустых узлов (т.е. пустых индексов в массиве, если ваше среднее значение ниже максимального), занимая память, вы только выделяете пространство для узла в связанном списке, когда вы фактически вводите значение.
Таким образом, если у вас есть в среднем 6 дочерних элементов, когда ваш максимум равен 200, массив будет создавать пространство для всех 200 дочерних элементов каждого узла при создании дерева, но связанный список будет выделять пространство только для узлов по мере необходимости. Таким образом, со связанным списком используемое пространство будет приблизительно (?) средним; с массивом используемый интервал будет максимальным.
... Я не вижу, когда было бы более эффективно использовать массив. Это вопрос с подвохом? Должен ли я учитывать тот факт, что массив должен иметь ограничение на общее количество узлов при его создании?
