Task #274. Префиксное дерево

Разбор

Префиксное дерево (Trie) — структура данных, которая позволяет хранить ассоциативный массив, ключами которого являются строки. 

У каждого узла может быть несколько дочерних узлов, в то время как пути к различным дочерним узлам представляют разные символы. И строки, которые представляют дочерние узлы, будут исходной строкой, представленной самим узлом плюс символ на пути.

Одним из важных свойств этой структуры является то, что все потомки узла имеют общий префикс строки, связанной с этим узлом. Вот почему ее еще называют префиксным деревом.

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

Реализация префиксного дерева

Есть 2 наиболее популярных способов реализации префиксного дерева:

• используем символьный массив для хранения дочерних узлов. Например, если мы храним строки, ктр содержат только буквы от a до z, то мы можем объявить массив размером 26 в каждом узле для хранения его дочерних узлов. А для конкретного символа мы можем использовать код индекса (например, c - 'a') в качестве индекса, чтобы найти соответствующий дочерний узел в массиве.
• использовать хэш-таблицу для хранения узлов. Тут все просто, ключом хэш-таблицы будет символ, а значением доечерний узел.

Первый вариант чуть быстрее, но избыточен по памяти, т.к. не всегда нужны все 26 символов для конкретного узла. Второй вариант более оптимальный, т.к. экономит место и использует только ту память, ктр нужна для префискного дерева.

Реализация на C#

https://gist.github.com/unilecs/4114c15420559d963b721f918280bb35