Ternary search tree
-
Описание ternary search tree
- Ternary search tree (TST) — это тип префиксного дерева, где узлы имеют до трех детей.
- TST более эффективны по пространству, чем стандартные префиксные деревья, но медленнее.
- TST используются для проверки правописания и автозавершения.
-
Структура данных
- Каждый узел хранит символ, объект и указатели на трех детей.
- Указатели на детей: equal kid, lo kid, hi kid.
- Указатель на родителя и индикатор конца слова.
-
Операции
- Вставка: рекурсивная или итеративная процедура.
- Поиск: проверка корня и рекурсивные вызовы на детей.
- Удаление: поиск и удаление пути от среднего ребенка до конца.
-
Время работы
- Время работы зависит от входных данных.
- TST работают лучше с похожими строками и короткими строками.
- Время работы аналогично двоичным деревьям, но может быть линейным в худшем случае.
-
Сравнение с другими структурами данных
- TST медленнее, чем другие префиксные деревья, но эффективнее для больших данных.
- Hash maps используют больше памяти, но могут быть медленнее.
- DAFSA могут быть более эффективными для хранения словарных слов.
-
Применение
- Хранение и поиск большого количества строк.
- Автозаполнение и проверка правописания.
- Near-neighbor поиск.
- Альтернатива хеш-таблицам.