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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

Історія, етимологія[ред. | ред. код]

Вперше концепцію префіксного дерева використав Аксель Туе в 1912 році для представлення множини, в якій кожен елемент є рядком[2][3]. В інформатиці вперше префіксні дерева описав Рене де ла Бриндаіс в 1959 році[4][5][6]. Також в 1960 році незалежно цю концепцію описав Едвард Фредкін[7], який запропонував використовувати слово trie. Вимовляти треба було [ˈtr] (так само як і англійське слово дерево «tree»). Однак, інші автори пропонують вимовляти це [ˈtr] (так само як і англійське слово «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. 

Див. також[ред. | ред. код]