Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Префіксне дерево англ trie або англ prefix tree структура даних дерево в якому шлях від кореня до листа визначає рядок Р

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

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

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

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

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

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

Операції

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

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

Примітки

  1. Arnab Bhattacharya (2015). 3.7 Tries. Fundamentals of Database Indexing and Searching. CRC Press. с. 52. ISBN .
  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 .
  4. de la Briandais, René (1959). (PDF). Proc. Western J. Computer Conf. с. 295—298. Архів оригіналу (PDF) за 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 .
  6. Brass, Peter (8 вересня 2008). Advanced Data Structures. UK: Cambridge University Press. doi:10.1017/CBO9780511800191. ISBN .
  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 (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 .

Див. також

Вікісховище має мультимедійні дані за темою: Префіксне дерево


image Це незавершена стаття про структури даних.
Ви можете проєкту, виправивши або дописавши її.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Prefiksne derevo angl trie abo angl prefix tree struktura danih derevo v yakomu shlyah vid korenya do lista viznachaye ryadok Ryadki z odnakovimi prefiksami mayut spilnij shlyah vid korenya dovzhinoyu cogo prefiksa Prefiksne derevo dozvolyaye zberigati asociativnij masiv klyuchami yakogo ye ryadki Na vidminu vid binarnih derev v listi dereva ne zberigayetsya klyuch Znachennya klyucha mozhna nabuti proglyadannyam vsih batkivskih vuzliv kozhnij z yakih zberigaye odin abo kilka simvoliv alfavitu Korin dereva pov yazanij z porozhnim ryadkom Takim chinom nashadki vuzla mayut zagalnij prefiks zvidki i vidbulasya nazva danogo abstraktnogo tipu danih Znachennya pov yazani z klyuchem zazvichaj ne pov yazani z kozhnim vuzlom a tilki z listyam i mozhlivo deyakimi vnutrishnimi vuzlami Istoriya etimologiyaVpershe koncepciyu prefiksnogo dereva vikoristav Aksel Tue v 1912 roci dlya predstavlennya mnozhini v yakij kozhen element ye ryadkom V informatici vpershe prefiksni dereva opisav Rene de la Brindais v 1959 roci Takozh v 1960 roci nezalezhno cyu koncepciyu opisav Edvard Fredkin yakij zaproponuvav vikoristovuvati slovo trie Vimovlyati treba bulo ˈ t r iː tak samo yak i anglijske slovo derevo tree Odnak inshi avtori proponuyut vimovlyati ce ˈ t r aɪ tak samo yak i anglijske slovo try dlya togo shob vidrizniti vid tree OperaciyiPrefiksni dereva pidtrimuyut tizh sami operaciyi kotri mozhna znajti v asociativnomu masivi ce operaciyi dodavannya pari a takozh poshuku ta vidalennya pari za klyuchem vstaviti klyuch znachennya shukati klyuch viluchiti klyuch PrimitkiArnab Bhattacharya 2015 3 7 Tries Fundamentals of Database Indexing and Searching CRC Press s 52 ISBN 978 1 4665 8255 2 Thue Axel 1912 Uber 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 vid 2nd Addison Wesley s 492 ISBN 0 201 89685 0 de la Briandais Rene 1959 PDF Proc Western J Computer Conf s 295 298 Arhiv originalu PDF za 11 lyutogo 2020 Cited by Brass and by Knuth Knuth Donald 1997 6 3 Digital Searching The Art of Computer Programming Volume 3 Sorting and Searching vid 2nd Addison Wesley s 492 ISBN 0 201 89685 0 Brass Peter 8 veresnya 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 listopada 2009 trie Dictionary of Algorithms and Data Structures National Institute of Standards and Technology originalu za 29 kvitnya 2011 Franklin Mark Liang 1983 Word Hy phen a tion By Com put er PDF Diplomna robota Doctor of Philosophy Stanford University PDF originalu za 11 listopada 2005 Procitovano 28 bereznya 2010 LiteraturaSartaj Sahni 2005 28 Tries U Dinesh P Mehta Sartaj Sahni red Handbook of Data Structures and Applications Chapman amp Hall CRC ISBN 1 58488 435 5 Div takozhVikishovishe maye multimedijni dani za temoyu Prefiksne derevo Algoritm Aho Korasik Sufiksne derevo Ce nezavershena stattya pro strukturi danih Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi

Дата публікації:
Топ