Какая структура данных node используется для trie

Ответ 1

Каждый из этих вариантов имеет свои преимущества и недостатки.

Если вы храните дочерние узлы в массиве, вы можете найти, какой ребенок посещать чрезвычайно эффективно, просто индексируя его в массив. Однако использование пространства за node будет высоким: O (| & Sigma; |), где & Sigma; это набор букв, из которых могут быть сформированы ваши слова, даже если большинство этих детей являются нулевыми.

Если вы храните дочерние узлы в связанном списке, тогда время, необходимое для поиска дочернего элемента, будет O (| & Sigma; |), так как вам может потребоваться сканировать все узлы связанного списка, чтобы найти ребенка, которого вы хотите. С другой стороны, эффективность пространства будет неплохой, потому что вы храните только тех детей, которые вы используете. Вы также можете рассмотреть возможность использования массива фиксированного размера, который имеет еще большее пространство, но приводит к очень дорогостоящим вставкам и удалениям.

Если вы храните дочерние узлы в хеш-таблице, тогда (ожидаемое) время для поиска ребенка будет O (1), а использование памяти будет пропорционально (примерно) числу детей, которые у вас есть. Интересно, что, поскольку вы заранее знаете, какие ценности вы собираетесь хешировать, вы можете использовать динамическую идеальную хеш-таблицу, случай O (1), за счет некоторой предвычисления.

Другой вариант - сохранить дочерние узлы в двоичном дереве поиска. Это приводит к структуре данных trernary search tree. Этот выбор находится где-то между параметрами связанного списка и хеш-таблицы - использование пространства низкое, и вы можете эффективно выполнять запросы предшественника и преемника, но есть небольшое увеличение стоимости выполнения поиска из-за стоимости поиска в BST. Если у вас есть статическое trie, где вставки никогда не происходят, вы можете использовать сбалансированные по весу деревья в качестве BST в каждой точке; это дает отличное время выполнения для поиска (O (n + log k), где n - длина строки для поиска, а k - общее количество слов в trie).

Короче говоря, поиск массивов самый быстрый, но его использование в худшем случае хуже. Массив статического размера имеет наилучшее использование памяти, но дорогостоящие вставки и удаления. Хэш-таблица имеет довольно быстрый поиск и хорошее использование памяти (в среднем). Деревья двоичного поиска находятся где-то посередине. Я бы предложил использовать хеш-таблицу здесь, хотя, если вы поместили премию в космос и не заботитесь о времени поиска, связанный список может быть лучше. Кроме того, если ваш алфавит невелик (скажем, вы делаете двоичное trie), накладные расходы массива не будут слишком плохими, и вы можете использовать их.

Надеюсь, это поможет!

Ответ 2

Если вы пытаетесь построить trie только для алфавитов, я бы предложил использовать массив, а затем использовать partia tree (space optimized trie). http://en.wikipedia.org/wiki/Radix_tree

Это позволит вам быстро находить массив с массивом и не тратить слишком много места, если коэффициент ветвления определенного node низкий.