Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
| Ця стаття не містить . (7 січня 2021) |
В інформатиці трійкове дерево пошуку — це тип префіксного дерева, де вузли розташовані таким чином, як в двійковому дереві пошуку, але мають щонайбільше троє дітей, замість двох (як у двійковому дереві пошуку). Як і інші префіксні дерева, трійкове дерево пошуку може бути використано як асоціативний масив з можливістю поступового пошуку рядків. Зазвичай трійкові дерева пошуку мають кращу просторову складність у порівнянні зі звичайними префіксними деревами, нехтуючи часовою складністю. Трійкові дерева пошуку переважно застосовують для написання алгоритмів перевірки орфографії та автодоповнення.
| Трійкове дерево пошуку (ТДП) | ||
|---|---|---|
| Тип | дерево | |
| Обчислювальна складність у записі великого О | ||
| Середня | Найгірша | |
| Простір | ||
| Пошук | O(log n) | O(n) |
| Вставляння | O(log n) | O(n) |
| Видалення | O(log n) | O(n) |
Опис
Кожен вузол трійкового дерева пошуку зберігає один символ, об'єкт (або вказівник на об'єкт, залежно від реалізації), і три вказівники (троє дітей), умовно названих equal kid, lo kid і hi kid, які також можуть називатися відповідно як середня дитина, мала дитина і велика дитина . Вузол може також мати вказівник на батьківський вузол, а також позначку того, чи є вузол кінцем слова. Вказівник lo kid повинен вказувати на вузол, значення символу якого менше ніж поточний вузол . Вказівник hi kid повинен вказувати на вузол, символ якого більше ніж значення у поточному вузлі. Equal kid вказує на наступного символ у слові. На малюнку нижче показано трійкове дерево пошуку, яке зберігає у собі такі рядки: «cute», «cup», «at», «as», «he», «us» та «i»:
c / | \ a u h | | | \ t t e u / / | / | s p e i s
Як і у випадку з іншими видами префіксних дерев, кожен вузол у трійковому дереві пошуку представляє префікс збережених рядків. Усі рядки в середньому піддереві вузла починаються з цього префікса.
Застосування
Трійкове дерева пошуку використовуються для вирішення багатьох проблем, де потрібно зберегти велику кількість рядків і потім шукати чи діставати рядок у довільному порядку. Нижче наведено деякі найпоширеніші або найкорисніші з них:
- Якщо вже використовується префіксне дерево, але потрібно забезпечити менше споживання пам'яті.
- Для реалізації автодоповнення.
- Для перевірки орфографії.
- Замість хеш-таблиці.
Див. також
Примітки
- Bentley, Jon; Sedgewick, Bob. . Dr. Dobb's. Архів оригіналу за 10 лютого 2022. Процитовано 8 січня 2022.
- . Архів оригіналу за 7 лютого 2015. Процитовано 8 січня 2022.
- Flint, Wally (16 лютого 2001). . InfoWorld (англ.). Архів оригіналу за 8 січня 2022. Процитовано 8 січня 2022.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Ne plutati z Dvijkove derevo Cya stattya ne mistit posilan na dzherela Vi mozhete dopomogti polipshiti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Material bez dzherel mozhe buti piddano sumnivu ta vilucheno 7 sichnya 2021 V informatici trijkove derevo poshuku ce tip prefiksnogo dereva de vuzli roztashovani takim chinom yak v dvijkovomu derevi poshuku ale mayut shonajbilshe troye ditej zamist dvoh yak u dvijkovomu derevi poshuku Yak i inshi prefiksni dereva trijkove derevo poshuku mozhe buti vikoristano yak asociativnij masiv z mozhlivistyu postupovogo poshuku ryadkiv Zazvichaj trijkovi dereva poshuku mayut krashu prostorovu skladnist u porivnyanni zi zvichajnimi prefiksnimi derevami nehtuyuchi chasovoyu skladnistyu Trijkovi dereva poshuku perevazhno zastosovuyut dlya napisannya algoritmiv perevirki orfografiyi ta avtodopovnennya Trijkove derevo poshuku TDP Tip derevo Obchislyuvalna skladnist u zapisi velikogo O Serednya Najgirsha Prostir Poshuk O log n O n Vstavlyannya O log n O n Vidalennya O log n O n OpisKozhen vuzol trijkovogo dereva poshuku zberigaye odin simvol ob yekt abo vkazivnik na ob yekt zalezhno vid realizaciyi i tri vkazivniki troye ditej umovno nazvanih equal kid lo kid i hi kid yaki takozh mozhut nazivatisya vidpovidno yak serednya ditina mala ditina i velika ditina Vuzol mozhe takozh mati vkazivnik na batkivskij vuzol a takozh poznachku togo chi ye vuzol kincem slova Vkazivnik lo kid povinen vkazuvati na vuzol znachennya simvolu yakogo menshe nizh potochnij vuzol Vkazivnik hi kid povinen vkazuvati na vuzol simvol yakogo bilshe nizh znachennya u potochnomu vuzli Equal kid vkazuye na nastupnogo simvol u slovi Na malyunku nizhche pokazano trijkove derevo poshuku yake zberigaye u sobi taki ryadki cute cup at as he us ta i c a u h t t e u s p e i s Yak i u vipadku z inshimi vidami prefiksnih derev kozhen vuzol u trijkovomu derevi poshuku predstavlyaye prefiks zberezhenih ryadkiv Usi ryadki v serednomu pidderevi vuzla pochinayutsya z cogo prefiksa ZastosuvannyaTrijkove dereva poshuku vikoristovuyutsya dlya virishennya bagatoh problem de potribno zberegti veliku kilkist ryadkiv i potim shukati chi distavati ryadok u dovilnomu poryadku Nizhche navedeno deyaki najposhirenishi abo najkorisnishi z nih Yaksho vzhe vikoristovuyetsya prefiksne derevo ale potribno zabezpechiti menshe spozhivannya pam yati Dlya realizaciyi avtodopovnennya Dlya perevirki orfografiyi Zamist hesh tablici Div takozhPrefiksne derevo Trijkove derevo Dvijkove derevo poshuku Nekoreneve dvijkove derevo Gesh tablicya AvtodopovnennyaPrimitkiBentley Jon Sedgewick Bob Dr Dobb s Arhiv originalu za 10 lyutogo 2022 Procitovano 8 sichnya 2022 Arhiv originalu za 7 lyutogo 2015 Procitovano 8 sichnya 2022 Flint Wally 16 lyutogo 2001 InfoWorld angl Arhiv originalu za 8 sichnya 2022 Procitovano 8 sichnya 2022