Возможный дубликат:
Где найти стандартную реализацию карты на основе Trie в Java?
Я хочу использовать Trie в Java, есть ли реализация, которую я могу использовать? (Я пробовал искать один, но я его не нашел).
Есть ли Trie в Java?
Ответ 1
В основных библиотеках Java нет структуры данных trie.
Это может быть связано с тем, что попытки обычно создаются для хранения символьных строк, тогда как структуры данных Java более общие, обычно содержащие любой Object (определяющий равенство и хэш-операцию), хотя иногда они ограничены объектами Comparable определяя порядок). Нет никакой общей абстракции для "последовательности символов", хотя CharSequence подходит для символьных строк, и я полагаю, вы могли бы что-то сделать с Iterable для других типов символов.
Здесь еще один момент, который следует учитывать: при попытке реализовать обычное trie в Java вы быстро сталкиваетесь с тем, что Java поддерживает Unicode. Чтобы иметь какую-либо эффективность пространства, вы должны ограничить строки в своем trie некоторым подмножеством символов или отказаться от обычного подхода к хранению дочерних узлов в массиве, индексированном символом. Это может быть другой причиной, по которой попытки не считаются общедоступными для включения в основную библиотеку, и что-то, что нужно учитывать, если вы реализуете свои собственные или используете стороннюю библиотеку.