Разница между Tries и деревьями?

Я отдаленно помню, что попытки не сохраняют все данные за node, а только суффикс родительскому node.

В тех случаях, когда деревья хранят все данные, но только организуют основы основанные на префиксах.

Таким образом, попытки становятся меньше, что может, например, сжимать словари очень хорошо.

Так это действительно единственная разница?

Из реальных приложений я помню, что попытки быстрее в запросах диапазона? Существуют даже специальные поля solr/lucene trie для ускорения запросов диапазона. Но как это так?

Какова фактическая разница и каковы преимущества/недостатки попыток и деревьев?

Ответ 1

Дерево - это общая структура рекурсивных узлов. Существует много типов деревьев. Популярные: двоичное дерево и сбалансированное дерево. A trie - это своеобразное дерево, известное многими именами, включая дерево префикса, дерево цифрового поиска и дерево поиска (отсюда и название" Trie ').

Каждый вид дерева имеет другую цель, структуру и поведение. Например, двоичное дерево хранит коллекцию сопоставимых элементов (например, числа). Поэтому его можно использовать для хранения набора чисел или для индексации других данных, которые могут быть представлены числами (например, объекты, которые можно хэшировать). Его структура сортируется, поэтому ее можно быстро найти, чтобы найти один элемент. Другие древовидные структуры, такие как сбалансированное дерево, в принципе схожи.

A trie представляет последовательность в своей структуре. Это очень отличается тем, что хранит последовательности значений, а не отдельные одиночные значения. Каждый уровень рекурсии говорит: "Каково значение элемента я входного списка". Это отличается от двоичного дерева, которое сравнивает одно значение поиска с каждым значением node.

Ответ 2

A двоичное дерево или bst обычно используется для хранения числовых значений. Сложность времени в bst - O (log (n)) для вставки, удаления и поиска. Каждый node в двоичном дереве имеет не более 2 дочерних узлов.

Trie. Каждый node trie состоит из нескольких ветвей. Каждая ветвь представляет собой возможный характер ключей. Мы должны пометить последний node каждого ключа как лист node. Значение поля trie node будет использоваться для отличия node как листа node (есть другие области использования поля значений)

Чтобы узнать о попытках, обратитесь к этому руководству topcoder. https://www.topcoder.com/community/data-science/data-science-tutorials/using-tries/