<prompt> A trie inatamkwa kama try au mti wa kiambishi ni muundo wa data wa mti unaotumiwa kuhifadhi na kurejesha vitufe kwa njia ifaayo katika mkusanyiko wa data. Kuna matumizi mbalimbali ya muundo huu wa data, kama vile kukamilisha kiotomatiki na kukagua tahajia.Tekeleza darasa la Trie: Trie Huanzisha kitu cha trie. insert batiliNeno la mfuatano Huingiza mfuatano neno kwenye jaribio. Utafutaji wa booleanNeno la mfuatano Hurejesha kweli ikiwa mfuatano neno uko katika jaribio yaani, iliwekwa hapo awali, na sivyo vinginevyo. boolean startsWithKiambishi awali cha Kamba Hurejesha kweli ikiwa kuna mfuatano neno ulioingizwa hapo awali ambao una kiambishi awali kiambishi awali, na false vinginevyo.Mfano wa 1:Ingizo Jaribu , ingiza , tafuta , tafuta , anzaNa , ingiza , tafuta , apple , apple , programu , programu , programu , programu Patonull, null, kweli, uongo, kweli, null, kweliUfafanuziTrie trie Trie mpya ;trie.insert apple;trie.search apple; kurudi Kwelitrie.search programu; kurudi Uongotrie.startsWith programu; kurudi Kwelitrie.insert programu;trie.search programu; kurudi KweliVikwazo: 1 word.length, prefix.length 2000 neno na kiambishi awali zinajumuisha herufi ndogo za Kiingereza pekee. Angalau zaidi simu 3 104 kwa jumla zitapigwa kuingiza, tafuta na startsWith.  <response>: chatudarasa la TrieNode: def __init__binafsi: self.children nafsi.ni_mwisho_wa_neno Si kwelidarasa Trie: def __init__binafsi: self.root TrieNode def insertbinafsi, neno: str - Hakuna: nodi self.mizizi kwa c kwa neno: ikiwa c sio katika nodi.watoto: nodi.childrenc TrieNode nodi nodi.childrenc nodi.ni_mwisho_wa_neno Kweli def tafuta binafsi, neno: str - bool: nodi self.mizizi kwa c kwa neno: ikiwa c sio katika nodi.watoto: kurudi Uongo nodi nodi.childrenc nodi ya kurudi.ni_mwisho_wa_neno def startsWithself, kiambishi awali: str - bool: nodi self.mizizi kwa c katika kiambishi awali: ikiwa c sio katika nodi.watoto: kurudi Uongo nodi nodi.childrenc kurudi KwelimaelezoMuundo wa data ya Trie unatekelezwa kama mti, ambapo kila nodi ina ramani ya wahusika kwa nodi zao za watoto zinazolingana. Kila nodi pia ina alama ya isEndOfWord ili kuashiria kama neno lolote linaishia kwenye nodi hii.Chaguo za kukokotoa za ingiza hurudia kupitia kila herufi katika neno fulani, na kuongeza nodi mpya kwenye mti ikiwa hazipo, na hatimaye kuweka alama ya isEndOfWord kuwa kweli kwenye nodi ya mwisho.Chaguo za kukokotoa za tafuta hufuata vibambo kutoka kwenye mzizi wa Trie hadi nodi ya mwisho, na kurudisha sivyo ikiwa herufi yoyote haielekei kwenye nodi ya mtoto, vinginevyo inarejesha thamani ya alamisho ya isEndOfWord katika nodi ya mwisho.Chaguo za kukokotoa za startsWith ni sawa na search, lakini hurejesha kuwa kweli ikiwa kuna mfuatano wa herufi kwenye Trie, bila kujali kama neno linaisha katika nodi ya mwisho. 