Каковы другие возможные варианты использования структуры данных Trie, отличной от T9/Spell checker dictionaries?

Question

Я пытаюсь понять структуру данных Trie & Я понял, что они используются в Spell checkers/Auto, предлагая или исправляя варианты написания и т. Д., Особенно используемые в контексте языковых словарей. Интересно, существуют ли другие возможные варианты использования для структуры данных Trie (как есть или в любой дополненной форме).

Спасибо за продвижение.

PS: Это не проблема домашней работы & Я здесь, чтобы лучше понять возможные возможности для структуры данных Trie и все.

Answer 1

Испытания являются интегральными в системах маршрутизации.

Большинство маршрутизаторов хранят IP-адрес в виде синтаксического дерева (Patricia Trees), которые хорошо подходят для поисков и т.д.

Пытается являются полезными в качестве справочной структуры, в которой вы имеете дело со строками (из байт/бит и т.д.) ,

Суффикс деревья, по существу, пытается и имеют широкое применение связанных строк, как подстроку проверки, находя повторяющиеся подстроки, палиндром найти и т.д.

Вот несколько алгоритмических головоломок для вас попробовать.

• Учитывая двоичную матрицу nxn (нулей и единиц), устраните повторяющиеся строки.

• Приведенные n чисел, найдем два числа x, y среди таких, что x XOR y (исключительный OR) является максимальным среди всех возможностей n^2.