Трійкове дерево пошуку

Не плутати з Двійкове дерево.
Трійкове дерево пошуку (ТДП)
Тип дерево
Обчислювальна складність
у записі великого О
Середня Найгірша
Простір
Пошук O(log n) O(n)
Вставляння O(log n) O(n)
Видалення O(log n) O(n)

В інформатиці трійкове дерево пошуку — це тип префіксного дерева, де вузли розташовані таким чином, як в двійковому дереві пошуку, але мають щонайбільше троє дітей, замість двох (як у двійковому дереві пошуку). Як і інші префіксні дерева, трійкове дерево пошуку може бути використано як асоціативний масив з можливістю поступового пошуку рядків. Зазвичай трійкові дерева пошуку мають кращу просторову складність у порівнянні зі звичайними префіксними деревами, нехтуючи часовою складністю. Трійкові дерева пошуку переважно застосовують для написання алгоритмів перевірки орфографії та автодоповнення.

Опис

Кожен вузол трійкового дерева пошуку зберігає один символ, об'єкт (або вказівник на об'єкт, залежно від реалізації), і три вказівники (троє дітей), умовно названих 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

Як і у випадку з іншими видами префіксних дерев, кожен вузол у трійковому дереві пошуку представляє префікс збережених рядків. Усі рядки в середньому піддереві вузла починаються з цього префікса.

Застосування

Трійкове дерева пошуку використовуються для вирішення багатьох проблем, де потрібно зберегти велику кількість рядків і потім шукати чи діставати рядок у довільному порядку. Нижче наведено деякі найпоширеніші або найкорисніші з них:

Див. також

Примітки

  1. ↑ а б Bentley, Jon; Sedgewick, Bob. Ternary Search Trees. Dr. Dobb's. Архів оригіналу за 10 лютого 2022. Процитовано 8 січня 2022.
  2. ↑ а б Efficient auto-complete with a ternary search tree. Архів оригіналу за 7 лютого 2015. Процитовано 8 січня 2022.
  3. ↑ а б Flint, Wally (16 лютого 2001). Plant your data in a ternary search tree. InfoWorld (англ.). Архів оригіналу за 8 січня 2022. Процитовано 8 січня 2022.