Префіксне дерево

Префіксне дерево (англ. trie, або англ. prefix tree) — структура даних, дерево, в якому шлях від кореня до листа визначає рядок. Рядки з однаковими префіксами мають спільний шлях від кореня довжиною цього префікса[1].

Префіксне дерево дозволяє зберігати асоціативний масив, ключами якого є рядки. На відміну від бінарних дерев, в листі дерева не зберігається ключ. Значення ключа можна набути прогляданням всіх батьківських вузлів, кожний з яких зберігає один або кілька символів алфавіту. Корінь дерева пов'язаний з порожнім рядком. Таким чином, нащадки вузла мають загальний префікс, звідки і відбулася назва даного абстрактного типу даних. Значення, пов'язані з ключем, зазвичай не пов'язані з кожним вузлом, а тільки з листям і, можливо, деякими внутрішніми вузлами.

Історія, етимологія

Вперше концепцію префіксного дерева використав Аксель Туе в 1912 році для представлення множини, в якій кожен елемент є рядком[2][3]. В інформатиці вперше префіксні дерева описав Рене де ла Бриндаіс в 1959 році[4][5][6]. Також в 1960 році незалежно цю концепцію описав Едвард Фредкін[7], який запропонував використовувати слово trie. Вимовляти треба було [ˈtriː] (так само як і англійське слово дерево «tree»). Однак, інші автори пропонують вимовляти це [ˈtraɪ] (так само як і англійське слово «try») для того, щоб відрізніти від «tree»[8][9][5].

Операції

Префіксні дерева підтримують тіж самі операції, котрі можна знайти в асоціативному масиві — це операції додавання пари, а також пошуку та видалення пари за ключем:

  • вставити (ключ, значення)
  • шукати (ключ)
  • вилучити (ключ)

Примітки
  1. Arnab Bhattacharya (2015). 3.7 Tries. Fundamentals of Database Indexing and Searching. CRC Press. с. 52. ISBN 978-1-4665-8255-2.
  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.
  3. 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.
  4. de la Briandais, René (1959). File searching using variable length keys Proc. Western J. Computer Conf. с. 295–298. Архів оригіналу за 11 лютого 2020. Cited by Brass and by Knuth.
  5. 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.
  6. Brass, Peter (8 вересня 2008). Advanced Data Structures. UK: Cambridge University Press. ISBN 978-0521880374. doi:10.1017/CBO9780511800191.
  7. Edward Fredkin (1960). Trie Memory. Communications of the ACM 3 (9): 490–499. doi:10.1145/367390.367400.
  8. Black, Paul E. (16 листопада 2009). trie. Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. Архів оригіналу за 29 квітня 2011.
  9. Franklin Mark Liang (1983). Word Hy-phen-a-tion By Com-put-er. Stanford University. Архів оригіналу за 11 листопада 2005. Процитовано 28 березня 2010. Проігноровано невідомий параметр |degree= (довідка)

Література
  • Sartaj Sahni (2005). 28. Tries. У Dinesh P. Mehta, Sartaj Sahni. Handbook of Data Structures and Applications. Chapman & Hall/CRC. ISBN 1-58488-435-5.

Див. також
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.