Дерево - это общая структура рекурсивных узлов. Есть много видов деревьев. Популярные из них: двоичное дерево и сбалансированное дерево . Trie - это разновидность дерева, известного под многими именами, включая дерево префиксов, дерево цифрового поиска и дерево поиска (отсюда и название «trie»).
Каждый вид дерева имеет свое назначение, структуру и поведение. Например, двоичное дерево хранит коллекцию сопоставимых элементов (например, чисел). Поэтому его можно использовать для хранения набора чисел или для индексации других данных, которые могут быть представлены числами (например, объекты, которые можно хэшировать). Его структура отсортирована, поэтому его можно быстро найти, чтобы найти один элемент. Другие древовидные структуры, такие как сбалансированное дерево, в принципе похожи.
A trie представляет последовательность в своей структуре. Он сильно отличается тем, что хранит последовательности значений, а не отдельные значения. Каждый уровень рекурсии говорит: «Какова ценность элемента I списка ввода». Это отличается от двоичного дерева, которое сравнивает одно искомое значение с каждым узлом.