Упорядочение дочерних узлов в дереве trie / radix

Question

Когда я просматриваю Трисы и радикальные деревья, такие как http://en.wikipedia.org/wiki/Compact_prefix_tree и http://en.wikipedia.org/wiki/Trie, я не вижу конкретной информации о лексикографическом упорядочении дети узла.

так, например, в этом примере (единственная фигура справа на странице) дочерние элементы корня можно лучше расположить слева направо как "A", "i", "t".

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

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

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

Answer 1

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

Например, нет никакого смысла лексикографически упорядочивать детей буквы "q", потому что у нее так мало детей. Двоичный поиск по нескольким буквам, которые следуют за "q", будет медленнее, чем последовательный поиск. Гораздо разумнее заказывать детей по частоте. 'u' будет первым потомком, и этот элемент будет выбран гораздо чаще, чем любой другой.

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

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