В інформатиці трійкове дерево пошуку — це тип префіксного дерева, де вузли розташовані таким чином, як в двійковому дереві пошуку, але мають щонайбільше троє дітей, замість двох (як у двійковому дереві пошуку). Як і інші префіксні дерева, трійкове дерево пошуку може бути використано як асоціативний масив з можливістю поступового пошуку рядків. Зазвичай трійкові дерева пошуку мають кращу просторову складність у порівнянні зі звичайними префіксними деревами, нехтуючи часовою складністю. Трійкові дерева пошуку переважно застосовують для написання алгоритмів перевірки орфографії та автодоповнення.
Кожен вузол трійкового дерева пошуку зберігає один символ, об'єкт (або вказівник на об'єкт, залежно від реалізації), і три вказівники (троє дітей), умовно названих equal kid, lo kid і hi kid, які також можуть називатися відповідно як середня дитина, мала дитина і велика дитина[1] . Вузол може також мати вказівник на батьківський вузол, а також позначку того, чи є вузол кінцем слова. Вказівник lo kid повинен вказувати на вузол, значення символу якого менше ніж поточний вузол . Вказівник hi kid повинен вказувати на вузол, символ якого більше ніж значення у поточному вузлі[2]. Equal kid вказує на наступного символ у слові. На малюнку нижче показано трійкове дерево пошуку, яке зберігає у собі такі рядки: «cute», «cup», «at», «as», «he», «us» та «i»:
c / | \ a u h | | | \ t t e u / / | / | s p e i s
Як і у випадку з іншими видами префіксних дерев, кожен вузол у трійковому дереві пошуку представляє префікс збережених рядків. Усі рядки в середньому піддереві вузла починаються з цього префікса.
Трійкове дерева пошуку використовуються для вирішення багатьох проблем, де потрібно зберегти велику кількість рядків і потім шукати чи діставати рядок у довільному порядку. Нижче наведено деякі найпоширеніші або найкорисніші з них:
French
Deutsch
