Префіксне дерево
Префіксне дерево (англ. trie, або англ. prefix tree) — структура даних, дерево, в якому шлях від кореня до листа визначає рядок. Рядки з однаковими префіксами мають спільний шлях від кореня довжиною цього префікса[1].
Префіксне дерево дозволяє зберігати асоціативний масив, ключами якого є рядки. На відміну від бінарних дерев, в листі дерева не зберігається ключ. Значення ключа можна набути прогляданням всіх батьківських вузлів, кожний з яких зберігає один або кілька символів алфавіту. Корінь дерева пов'язаний з порожнім рядком. Таким чином, нащадки вузла мають загальний префікс, звідки і відбулася назва даного абстрактного типу даних. Значення, пов'язані з ключем, зазвичай не пов'язані з кожним вузлом, а тільки з листям і, можливо, деякими внутрішніми вузлами.
Історія, етимологія[ред. | ред. код]
Вперше концепцію префіксного дерева використав Аксель Туе в 1912 році для представлення множини, в якій кожен елемент є рядком[2][3]. В інформатиці вперше префіксні дерева описав Рене де ла Бриндаіс в 1959 році[4][5][6]. Також в 1960 році незалежно цю концепцію описав Едвард Фредкін[7], який запропонував використовувати слово trie. Вимовляти треба було [ˈtriː] (так само як і англійське слово дерево «tree»). Однак, інші автори пропонують вимовляти це [ˈtraɪ] (так само як і англійське слово «try») для того, щоб відрізніти від «tree»[8][9][5].
Операції[ред. | ред. код]
Префіксні дерева підтримують тіж самі операції, котрі можна знайти в асоціативному масиві — це операції додавання пари, а також пошуку та видалення пари за ключем:
- вставити (ключ, значення)
- шукати (ключ)
- вилучити (ключ)
Примітки[ред. | ред. код]
- ↑ Arnab Bhattacharya (2015). 3.7 Tries. Fundamentals of Database Indexing and Searching. CRC Press. с. 52. ISBN 978-1-4665-8255-2.
- ↑ Thue, Axel (1912). Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Skrifter udgivne af Videnskabs-Selskabet i Christiania. 1912 (1): 1—67. Cited by Knuth.
- ↑ Knuth, Donald (1997). 6.3: Digital Searching. The Art of Computer Programming Volume 3: Sorting and Searching (вид. 2nd). Addison-Wesley. с. 492. ISBN 0-201-89685-0.
- ↑ de la Briandais, René (1959). File searching using variable length keys (PDF). Proc. Western J. Computer Conf. с. 295—298. Архів оригіналу (PDF) за 11 лютого 2020. Cited by Brass and by Knuth.
- ↑ а б Knuth, Donald (1997). 6.3: Digital Searching. The Art of Computer Programming Volume 3: Sorting and Searching (вид. 2nd). Addison-Wesley. с. 492. ISBN 0-201-89685-0.
- ↑ Brass, Peter (8 вересня 2008). Advanced Data Structures. UK: Cambridge University Press. doi:10.1017/CBO9780511800191. ISBN 978-0521880374.
- ↑ Edward Fredkin (1960). Trie Memory. Communications of the ACM. 3 (9): 490—499. doi:10.1145/367390.367400.
- ↑ Black, Paul E. (16 листопада 2009). trie. Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. Архів оригіналу за 29 квітня 2011.
- ↑ Franklin Mark Liang (1983). Word Hy-phen-a-tion By Com-put-er (PDF) (Дипломна робота Doctor of Philosophy). Stanford University. Архів (PDF) оригіналу за 11 листопада 2005. Процитовано 28 березня 2010.
Література[ред. | ред. код]
- Sartaj Sahni (2005). 28. Tries. У Dinesh P. Mehta, Sartaj Sahni (ред.). Handbook of Data Structures and Applications. Chapman & Hall/CRC. ISBN 1-58488-435-5.
Див. також[ред. | ред. код]
 |
Вікісховище має мультимедійні дані за темою: Префіксне дерево |
|
Це незавершена стаття про структури даних. Ви можете допомогти проєкту, виправивши або дописавши її. |
| |||||||||||||||||
| ||||||||||||||||||||