Каждый из этих параметров имеет свои преимущества и недостатки.
Если вы храните дочерние узлы в массиве, то вы можете найти, какой дочерний узел чрезвычайно эффективно посещать, просто индексировав его в массив.Однако использование пространства на узел будет высоким: O (| Σ |), где Σ - это набор букв, из которых могут быть образованы ваши слова, даже если большинство из этих дочерних элементов равно нулю.
Если высохраните дочерние узлы в связанном списке, тогда время, необходимое для поиска дочернего элемента, будет O (| Σ |), поскольку вам может потребоваться отсканировать все узлы связанного списка, чтобы найти требуемый дочерний узел.С другой стороны, эффективность использования пространства будет довольно хорошей, потому что вы сохраняете только тех детей, которых используете.Вы можете также рассмотреть возможность использования массива фиксированного размера, который имеет еще лучшее использование пространства, но приводит к очень дорогим вставкам и удалениям.
Если вы храните дочерние узлы в хэш-таблице, то (ожидаемое) времянайти ребенка будет O (1), а использование памяти будет пропорционально (примерно) количеству детей, которые у вас есть.Интересно, что, поскольку вы заранее знаете, какие значения вы собираетесь хэшировать, вы можете рассмотреть возможность использования динамической совершенной хеш-таблицы для обеспечения поиска O (1) в худшем случае за счет некоторого предварительного вычисления.
Другой вариант - сохранить дочерние узлы в бинарном дереве поиска.Это приводит к структуре троичного дерева поиска .Этот выбор находится где-то между параметрами связанного списка и хеш-таблицы - использование пространства невелико, и вы можете эффективно выполнять запросы предшественника и преемника, но при поиске в BST стоимость поиска немного увеличивается.Если у вас есть статический три, где вставки никогда не происходят, вы можете рассмотреть возможность использования сбалансированных по весу деревьев в качестве BST в каждой точке;это дает отличное время выполнения для поиска (O (n + log k), где n - длина строки для поиска, а k - общее количество слов в трие).
Короче говоря, массивпоиск выполняется быстрее всего, но его использование в худшем случае - наихудшее.Массив статического размера имеет лучшее использование памяти, но дорогие вставки и удаления.Хеш-таблица имеет довольно быстрый поиск и хорошее использование памяти (в среднем).Деревья бинарного поиска находятся где-то посередине.Я бы предложил использовать здесь хеш-таблицу, хотя, если вы ставите премию на пространство и не заботитесь о времени поиска, связанный список может быть лучше.Кроме того, если ваш алфавит мал (например, вы создаете двоичный файл), служебные данные массива не будут слишком плохими, и вы можете захотеть использовать это.
Надеюсь, это поможет!