Трійкове дерево пошуку
Ця стаття не містить посилань на джерела. (7 січня 2021) |
В інформатиці трійкове дерево пошуку — це тип префіксного дерева, де вузли розташовані таким чином, як в двійковому дереві пошуку, але мають щонайбільше троє дітей, замість двох (як у двійковому дереві пошуку). Як і інші префіксні дерева, трійкове дерево пошуку може бути використано як асоціативний масив з можливістю поступового пошуку рядків. Зазвичай трійкові дерева пошуку мають кращу просторову складність у порівнянні зі звичайними префіксними деревами, нехтуючи часовою складністю. Трійкові дерева пошуку переважно застосовують для написання алгоритмів перевірки орфографії та автодоповнення.
| Трійкове дерево пошуку (ТДП) | ||
|---|---|---|
| Тип | дерево | |
| Обчислювальна складність у записі великого О | ||
| Середня | Найгірша | |
| Простір | ||
| Пошук | 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].
- Для реалізації автодоповнення[2].
- Для перевірки орфографії[3].
- Замість хеш-таблиці[3].
Див. також
ред.Примітки
ред.- ↑ а б Bentley, Jon; Sedgewick, Bob. Ternary Search Trees. Dr. Dobb's. Архів оригіналу за 10 лютого 2022. Процитовано 8 січня 2022.
- ↑ а б Efficient auto-complete with a ternary search tree. Архів оригіналу за 7 лютого 2015. Процитовано 8 січня 2022.
- ↑ а б Flint, Wally (16 лютого 2001). Plant your data in a ternary search tree. InfoWorld (англ.). Архів оригіналу за 8 січня 2022. Процитовано 8 січня 2022.