заказывающие детей узла в Trie/натальной дерева

Question

Когда я смотрю ПЫТАЕТСЯ и Radix деревья, такие как http://en.wikipedia.org/wiki/Compact_prefix_tree и http://en.wikipedia.org/wiki/Trie, я не вижу определенную вещь на лексикографическом-упорядочением дочерних узлов.

так, в this синтаксического дерева, например (только рисунок прямо на странице) дети корня может лучше заказать как «A», «я», «т» слева направо.

Tries/radix trees предназначены для поиска - не для частого обновления. поэтому такой порядок заказов не стоит особо особо на редких обновлениях дерева, алгоритмически легко/просто и добавляет некоторые к скорости во время поиска/поиска стоимости.

что мне не хватает?

Я ищу аргументы против/против этого.

Answer 1

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

Например, не имеет никакого смысла лексикографически упорядочить детей буквы «q», потому что у нее так мало детей. Бинарный поиск на нескольких буквах, следующих за «q», будет медленнее, чем последовательный поиск. Намного больше смысла заказывать детей по частоте. «u» будет первым ребенком, и элемент, который выбран гораздо чаще, чем другие.

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

Вы можете построить такое trie и изучить узлы. Посмотрите, сколько у детей типичного узла есть, и посмотрите, что такое частоты.