В чём разница между Trie и Tree?

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

Дерево (Tree)

Дерево — это структура данных, состоящая из элементов, называемых узлами (nodes), соединённых рёбрами (edges).

Каждый узел содержит значение и список ссылок на дочерние узлы. Первый узел дерева называется корнем (root). Если визуализировать, дерево напоминает перевёрнутое дерево: корень вверху, листья (узлы без детей) — внизу.

Деревья — иерархические, нелинейные структуры данных.

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

Пример простого бинарного дерева на Python, где у каждого узла не более двух детей:

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
root = Node(1)
root.left = Node(2)
root.right = Node(3)

Здесь у нас есть дерево с корневым узлом, хранящим значение 1. У корня два потомка: левый — со значением 2, правый — со значением 3.

Trie

Trie (три, префиксное дерево) — это разновидность дерева, предназначенная для работы с последовательностями, обычно строками. В trie каждый узел (кроме корня) соответствует символу или строке, а каждый путь вниз по дереву может представлять слово или префикс.

Ключевая особенность trie — быстрый поиск данных. Проверка наличия слова или префикса в наборе данных занимает O(M), где M — длина слова.

Пример простой реализации trie на Python:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end_of_string = False
 
class Trie:
    def __init__(self):
        self.root = TrieNode()
 
    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.end_of_string = True

В этом примере каждый узел trie содержит словарь children для хранения ссылок на дочерние узлы. Флаг end_of_string помогает определить, образует ли текущая последовательность символов корректное слово.

Trie / Tree

Несмотря на общие свойства (обе — деревообразные структуры), trie и tree предназначены для разных задач.

Хранение данных: Обычное дерево может хранить любые типы данных — числа, строки, объекты, а trie используется для хранения последовательностей, например, строк или массивов.

Значение узла: В дереве каждый узел содержит значение. В trie сами узлы значения не хранят — значение задаётся путём от корня к узлу.

Эффективность: Trie очень эффективны для поиска слова или префикса в словаре. Деревья же универсальнее и эффективны для широкого спектра операций: поиска, вставки, удаления любых значений.

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

Время поиска: В trie поиск слова занимает O(M), где M — длина слова. В сбалансированном бинарном дереве — O(log N), где N — количество элементов.