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

Префіксне дерево (англ. 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 (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 0-201-89685-0.
  6. ↑ Brass, Peter (8 вересня 2008). Advanced Data Structures. UK: Cambridge University Press. doi:10.1017/CBO9780511800191. ISBN 978-0521880374.
  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.

Література

Див. також

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


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

Read other articles:

Lareh Koto Piliang

Lareh Koto Piliang adalah salah satu sistem adat Minangkabau yang bertumpu kepada sistem aristokratis. Sistem adat ini dibuat oleh Datuk Ketumanggungan, dan berlaku di hampir seluruh wilayah budaya Minangkabau, terutama Luhak Tanah Datar, Luhak Limapuluh, dan Pesisir Selatan. Ciri-ciri Dalam pengambilan keputusan berdasarkan arahan pimpinan (penghulu/raja). Titiak dari ateh, turun dari tanggo. Tabujua lalu tabalintang patah, kato surang gadang sagalo iyo, ikan gadang dalam lauik, ikan ketek m...

 

Professional Footballers' Association

PFAProfessional Footballers' AssociationDidirikan1907Anggota4000NegaraInggris dan Wales, Britania RayaAfiliasiTUC, GFTU, FIFProTokoh pentingGordon Taylor, ketua eksekutifSitus resmiwww.thepfa.com Professional Footballers' Association disingkat PFA (Indonesia: Asosiasi Pemain Sepak Bola Profesionalcode: id is deprecated ) adalah serikat pekerja bagi para pemain sepak bola profesional di Inggris dan Wales. Organisasi ini adalah serikat pekerja olahraga profesional tertua di dunia, memiliki 4.0...

 

Daftar Bupati Sidoarjo

Bupati SidoarjoLambang Kabupaten SidoarjoPetahanaK.H. Ahmad Muhdlor Ali, S.I.Psejak 26 Februari 2021Masa jabatan5 tahunDapat dipilih kembali satu kaliDibentuk1933Pejabat pertamaSoejadiSitus websidoarjokab.go.id Berikut ini adalah Daftar Bupati Sidoarjo sejak masa awal kemerdekaan Indonesia:[1] No Bupati Mulai menjabat Akhir menjabat Prd. Ket. Wakil Bupati 1 Soejadi 1933 1949 1 Tidak ada 2 R. Suriadi Kertosuprojo 1950 1958 2 3 H.A. Chudori Amir 1958 1959 3 4 R.H. Samadikoen 1959 1...

EP 07 Tower

Artikel ini membahas mengenai bangunan, struktur, infrastruktur, atau kawasan terencana yang sedang dibangun atau akan segera selesai. Informasi di halaman ini bisa berubah setiap saat (tidak jarang perubahan yang besar) seiring dengan penyelesaiannya. One Park AvenueInformasi umumStatusProposalLokasiDubai, Uni Emirat ArabTinggiAtap600 meter (1,969 ft)[1]Data teknisJumlah lantai125[1]Luas lantai350,000 m2 (3,767,000 sq ft)[2]Desain dan konstruksiArsitekAdrian Smith + G...

 

Poitiers

Poitiers PoetàePrefektur dan KomunePusat bersejarah Poitiers dengan Gereja Saint-Radegund, Katedral Poitiers dan Istana Poitiers Lambang kebesaranPoitiers Lokasi di Region Nouvelle-Aquitaine Poitiers Koordinat: 46°35′N 0°20′E / 46.58°N 0.34°E / 46.58; 0.34Koordinat: 46°35′N 0°20′E / 46.58°N 0.34°E / 46.58; 0.34NegaraPrancisRegionNouvelle-AquitaineDepartemenVienneArondisemenPoitiersKantonPoitiers-1, 2, 3, 4 and 5AntarkomuneDU Gra...

 

Howard Hughes

Howard HughesLahirHoward Robard Hughes, Jr.(1905-12-24)24 Desember 1905Houston, Texas, Amerika SerikatMeninggal5 April 1976(1976-04-05) (umur 70)Houston, Texas, Amerika SerikatPekerjaanPimpinan Hughes Aircraft, Industrialis, Penerbang, Insinyur, Produser dan Sutradara FilmSuami/istriElla Rice ​(m. 1925⁠–⁠1929)​ Terry Moore ​(m. 1949⁠–⁠1976)​ (dugaan) Jean Peters ​(m. 19...

Everette B. Howard

American politician Everette Burgess HowardMember of the U.S. House of Representativesfrom Oklahoma's 1st districtIn officeMarch 4, 1919 – March 3, 1921Preceded byThomas Alberter ChandlerSucceeded byThomas Alberter ChandlerIn officeMarch 4, 1923 – March 3, 1925Preceded byThomas Alberter ChandlerSucceeded bySamuel J. MontgomeryIn officeMarch 4, 1927 – March 3, 1929Preceded bySamuel J. MontgomerySucceeded byCharles O'Connor Personal detailsBornSeptem...

 

2018 World of Westgate 200

2018 World of Westgate 200 Race details Race 18 of 23 of the 2018 NASCAR Camping World Truck SeriesDate September 14, 2018Official name World of Westgate 200Location North Las Vegas, Nevada, Las Vegas Motor SpeedwayCourse Permanent racing facility1.5 mi (2.41 km)Distance 144 laps, 216 mi (347.618 km)Scheduled Distance 134 laps, 201 mi (323.477 km)Average speed 101.647 miles per hour (163.585 km/h)Pole positionDriver Noah Gragson Kyle Busch MotorsportsTime 30.331Most laps ledDriver Grant ...

 

Mathilde yang Suci

Santa MathildeRatuLahir895Engern, Kerajaan Sachsen (masa kini Utara sungai Rhine, JermanMeninggal14 Maret 968Quedlinburg, distrik Harz, JermanDihormati diGereja Katolik RomaTempat ziarahBiara QuedlinburgPesta14 Maret Santa Mathilde (atau Matilda) (sek. 895 – 14 Maret 968) merupakan istri Raja Heinrich I dari Jerman, penguasa Sachsen pertama dari Ottonian (atau Wangsa Liudolfing), dengan demikian Permaisuri Sachsen dari tahun 912 dan Ratu Jerman dari tahun 919 sampai 936. Putra sulung mereka...

约翰斯顿环礁

此條目可参照英語維基百科相應條目来扩充。 (2021年5月6日)若您熟悉来源语言和主题，请协助参考外语维基百科扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记{{Translated page}}标签。 约翰斯顿环礁Kalama Atoll 美國本土外小島嶼 Johnston Atoll 旗幟颂歌：《星條旗》The Star-Spangled Banner約翰斯頓環礁�...

 

Kiều Thuận

Dua Belas Panglima perang Kiều Thuận (Hán tự: 矯順, ?–?) merupakan seorang panglima perang dari Vietnam selama era Dua Belas Panglima Perang. Thuận adalah cucu dari Kiều Công Tiễn. Ia juga merupakan adik laki-laki dari panglima perang lain, Kiều Công Hãn.[1] Dia memegang Hồi Hồ (Distrik Cẩm Khe modern, Provinsi Phú Thọ), dan yang menyebut dirinya sendiri Kiều Lệnh Công (矯令公).[2][3] Referensi ^ Taylor, Keith Weller (1991). ...

 

County Fremont, Wyoming

Gedung pengadilan county di Lander Lokasi di Wyoming County Fremont adalah sebuah county di negara bagian Wyoming, Amerika Serikat.[1] Pada sensus Amerika Serikat tahun 2020, jumlah penduduknya adalah 39.234 jiwa, menjadikannya county terpadat kelima di Wyoming. Pusat pemerintahannya adalah Lander.[2] County Fremont dibentuk pada tanggal 5 Maret 1884, oleh badan legislatif Wilayah Wyoming.[3] County ini dibentuk dengan tanah yang diserahkan oleh County Sweetwater. Pada...

Anouvong

Last monarch of the Kingdom of Vientiane This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Anouvong – news · newspapers · books · scholar · JSTOR (March 2018) (Learn how and when to remove this message) For the district, see Anouvong district. Chao Anouvongເຈົ້າອານຸວົງສ໌เจ้า...

 

Rocketdyne J-2

Artikel ini perlu diwikifikasi agar memenuhi standar kualitas Wikipedia. Anda dapat memberikan bantuan berupa penambahan pranala dalam, atau dengan merapikan tata letak dari artikel ini. Untuk keterangan lebih lanjut, klik [tampil] di bagian kanan. Mengganti markah HTML dengan markah wiki bila dimungkinkan. Tambahkan pranala wiki. Bila dirasa perlu, buatlah pautan ke artikel wiki lainnya dengan cara menambahkan [[ dan ]] pada kata yang bersangkutan (lihat WP:LINK untuk keterangan lebih lanjut...

 

Law and economics

Application of economic theory to analysis of legal systems Part of a series onLaw Foundations and Philosophy Definition Philosophy History Legal theory Jurisprudence Judicial interpretation Positive law Law and economics Sociology of law Methodological background Normative Prescriptive Legal debate Legal and judicial opinions vte Part of a series onEconomics History Outline Index Branches and classifications Applied Econometrics Heterodox International Micro / Macro Mainstream Mathematical M...

Kulen

Not to be confused with Kullen or Culen. This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Kulen – news · newspapers · books · scholar · JSTOR (July 2010) (Learn how and when to remove this message) KulenSlices of kulenAlternative namesKulinTypesausageCourseAppetizerRegion or stateBaranja, Bačka, Slavonia, Sy...

 

McGaughey and Davies v USS Ltd

McGaughey and Davies v USS Ltd and DirectorsCourtCourt of AppealDecidedMay 2022Citations[2023] EWCA Civ 873, [2022] EWHC 1233 (Ch)Court membershipJudge sittingAsplin LJKeywordsClimate litigation, derivative claim, Foss v Harbottle, Discrimination McGaughey and Davies v Universities Superannuation Scheme Ltd and Directors [2023] EWCA Civ 873 is a UK company law, climate litigation, and pension law case, seeking permission for a derivative claim to enforce duties of the directors of the UK univ...

 

2012 United States House of Representatives election in Wyoming

2012 United States House of Representatives election in Wyoming's at-large district ← 2010 November 6, 2012 2014 →   Nominee Cynthia Lummis Chris Henrichsen Party Republican Democratic Popular vote 166,452 57,573 Percentage 68.89% 23.83% County results Lummis:      50-60%      60-70%      70-80%      80-90% Henrichsen:      40–50% U.S....

Hòa Hảo

Buddhist sect founded in 1939 Part of a series onHòa Hảo Origins Đạo Bửu Sơn Kỳ Hương Vietnamese Buddhism Khmer Buddhism Amidism Confucianism White Lotus Hinduism Doctrine Nationalism Anti-communism Anti-urbanism Communitarianism Anti-imperialism Anti-Western sentiment Teetotalism Homeland Mekong Delta: Đồng Tháp An Giang Bến Tre Vĩnh Long Kiên Giang Cần Thơ Prominent figures Huỳnh Phú Sổ Huỳnh Công Bộ Huyền Thị Kim Biên Ba Cụt Lam Thanh Nguyen Nguyen ...

 

Strokestown Park

18th-century house in County Roscommon, Ireland This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Strokestown Park – news · newspapers · books · scholar · JSTOR (December 2010) (Learn how and when to remove this message) Strokestown ParkStrokestown Park House in 2011General informationArchitectural stylePallad...