TrieNode-luokka: lisäys ja haku
Rakentakaa TrieNode, jossa on children-sanakirja ja is_end-lippu, toteuttakaa insert ja exact-search sekä analysoikaa operaation O(m)-aika, jossa m on sanan pituus.
TrieNode-luokka: lisäys ja haku on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 1/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mikä Trie on?
Trie eli etuliitepuu on puumainen tietorakenne, jossa jokainen solmu edustaa yhtä merkkiä. Sanat tallennetaan ketjuttamalla merkit juuresta lehteen. Juuri edustaa tyhjää merkkijonoa. Jokainen polku juuresta is_end = True -solmuun muodostaa tallennetun sanan. Triet sopivat erityisen hyvin etuliitteisiin perustuviin kyselyihin, kuten automaattiseen täydennykseen, oikeinkirjoituksen tarkistukseen ja IP-reititykseen, ja ovat näissä käyttötapauksissa hajautustauluja tehokkaampia.
TrieNode-luokan suunnittelu
TrieNode-solmulla on kaksi kenttää: children — sanakirja, joka yhdistää merkit lapsina oleviin TrieNode-solmuihin — ja is_end — totuusarvo, joka ilmaisee, päättyykö tallennettu sana tähän solmuun. Sanakirjan käyttäminen kiinteäkokoisen 26 merkin taulukon sijaan yleistää rakenteen mille tahansa merkistöjoukolle ja säästää muistia harvoissa trie-rakenteissa. Jokainen trien solmu vastaa täsmälleen yhtä merkkipaikkaa sen alapuolella olevissa sanoissa.
class TrieNode:
def __init__(self):
self.children = {} # char -> TrieNode
self.is_end = False # True if a word ends here
class Trie:
def __init__(self):
self.root = TrieNode()
def __repr__(self):
return f'Trie(root with {len(self.root.children)} children)'
t = Trie()
print(t) # Trie(root with 0 children)Lisäysoperaatio
Lisätessänne sanan kulkekaa juuresta alkaen eteenpäin ja luokaa jokaiselle merkille uusi TrieNode, jos merkkiä ei vielä ole nykyisen solmun children-sanakirjassa. Kun kaikki merkit on käsitelty, asettakaa viimeisen solmun arvoksi is_end = True. Kun lisätään 'apple' ja 'app', muodostuu ketju a→p→p→l→e (is_end=True sanalle 'apple'), ja myös kohdassa 3 oleva p merkitään arvolla is_end=True sanalle 'app'.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
t = Trie()
t.insert('apple')
t.insert('app')
print('Inserted apple and app')
print('app is_end:', t.root.children['a'].children['p'].children['p'].is_end)Hakuoperaatio
Tarkkaa sanaa haettaessa kulkekaa tries-rakenteessa jokaisen merkin mukaisesti. Jos jokin merkki puuttuu nykyisen solmun children-sanakirjasta, palauttakaa False. Jos kaikki merkit löytyvät, palauttakaa node.is_end — arvo True vain silloin, kun sana päättyy täsmälleen tähän solmuun eikä kyseessä ole pelkkä etuliite. Ero sen välillä, onko etuliite olemassa ja onko tarkka sana olemassa, on olennainen, ja sitä kysytään usein tehtävissä.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def search(self, word):
node = self.root
for c in word:
if c not in node.children:
return False
node = node.children[c]
return node.is_end # must be a complete word
t = Trie()
t.insert('apple')
print(t.search('apple')) # True
print(t.search('app')) # False (app not inserted)
print(t.search('orange')) # FalseStarts-With (etuliitehaku)
starts_with-metodi tarkistaa, alkaako jokin lisätty sana annetulla etuliitteellä. Se kulkee saman polun kuin search, mutta is_end-arvon tarkistamisen sijaan palauttaa True heti, kun kaikkia etuliitteen merkkejä on voitu seurata onnistuneesti. Tämä tarkoittaa, että etuliitettä vastaava polku on tries-rakenteessa olemassa.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def search(self, word):
node = self.root
for c in word:
if c not in node.children: return False
node = node.children[c]
return node.is_end
def starts_with(self, prefix):
node = self.root
for c in prefix:
if c not in node.children: return False
node = node.children[c]
return True # prefix path exists
t = Trie()
t.insert('apple')
print(t.starts_with('app')) # True
print(t.starts_with('ape')) # False
print(t.search('app')) # False (not inserted)Aika- ja tilavaativuus
Jokaisen trie-operaation (insert, search, starts_with) aikavaativuus on O(m), missä m on sanan pituus: kuljemme enintään m solmun läpi. Tilavaativuus on O(ALPHABET_SIZE × N × M), missä N on sanojen määrä ja M niiden keskimääräinen pituus. Käytännössä yhteiset etuliitteet pienentävät tilankulutusta huomattavasti. Hajautustauluun perustuva children-sanakirja käyttää harvoissa trie-rakenteissa vähemmän tilaa kuin kiinteäkokoisten 26 merkin taulukko, mutta yksittäisen haun vakioaikakustannus on hieman suurempi.
Taulukon käyttäminen sanakirjan sijaan
Jos käytössä ovat vain englannin pienet kirjaimet, käyttäkää kiinteäkokoista taulukkoa children = [None] * 26 ja indeksiä ord(c) - ord('a'). Tämä on nopeampi (lapsisolmun haku on O(1) hajautustauluun verrattuna) ja sen muistirakenne on ennakoitava. Käyttäkää sanakirjaversiota, kun merkistö on suuri tai tuntematon, esimerkiksi Unicode-merkistöä käsiteltäessä, ja taulukkoversiota kilpailuohjelmoinnin tehtävissä, joissa esiintyy vain pieniä kirjaimia.
class TrieNodeArray:
def __init__(self):
self.children = [None] * 26
self.is_end = False
class TrieArray:
def __init__(self):
self.root = TrieNodeArray()
def insert(self, word):
node = self.root
for c in word:
idx = ord(c) - ord('a')
if node.children[idx] is None:
node.children[idx] = TrieNodeArray()
node = node.children[idx]
node.is_end = True
def search(self, word):
node = self.root
for c in word:
idx = ord(c) - ord('a')
if node.children[idx] is None: return False
node = node.children[idx]
return node.is_end
t = TrieArray()
t.insert('cat')
print(t.search('cat')) # True
print(t.search('car')) # FalsePoisto-operaatio
Sanan poistossa tries-rakenteesta on käsiteltävä kolme tapausta: (1) sanaa ei ole — älkää tehkö mitään; (2) sana on olemassa, mutta se on toisen sanan etuliite — poistakaa vain is_end-merkintä; (3) sana on olemassa eikä ole etuliite — poistakaa solmuja alhaalta ylöspäin ja lopettakaa, kun solmulla on muita lapsia tai se on toisen sanan loppu. Poistoa kysytään työhaastatteluissa harvoin, mutta sen periaate on hyvä tuntea.
Etuliitteen sisältävien sanojen laskeminen
Laajentakaa jokaista solmua count-kentällä, jota kasvatetaan jokaisen insert-operaation aikana solmun läpi kuljettaessa. Kun haluatte laskea tietyn etuliitteen sisältävät sanat, kulkekaa etuliitteen päätesolmuun ja palauttakaa sen count-arvo. Näin automaattisen täydennyksen kysely voidaan suorittaa ajassa O(m) ilman kaikkien lapsien läpikäyntiä. Tämä on hyödyllinen laajennus todellisiin automaattisen täydennyksen järjestelmiin.
class TrieNodeCount:
def __init__(self):
self.children = {}
self.is_end = False
self.count = 0 # words passing through this node
class TrieCount:
def __init__(self):
self.root = TrieNodeCount()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNodeCount()
node = node.children[c]
node.count += 1 # increment on each level
node.is_end = True
def count_with_prefix(self, prefix):
node = self.root
for c in prefix:
if c not in node.children: return 0
node = node.children[c]
return node.count
t = TrieCount()
for w in ['apple','app','application','apply']:
t.insert(w)
print(t.count_with_prefix('app')) # 4
print(t.count_with_prefix('appl')) # 3Trien ja hajautustaulujen vertailu
Hajautustaulu voi suorittaa tarkan haun keskimäärin ajassa O(m), mutta se ei pysty vastaamaan etuliitekyselyihin tehokkaasti, koska kaikki avaimet pitäisi käydä läpi. Trie vastaa etuliitekyselyihin ajassa O(p), missä p on etuliitteen pituus, ryhmittelee sanat luonnollisesti yhteisten etuliitteiden mukaan eikä tarvitse hajautusta. Käyttäkää trietä, kun etuliitekyselyitä tehdään usein tai tarvitaan automaattista täydennystä ja oikeinkirjoituksen tarkistusta. Käyttäkää hajautustaulua, kun tarvitaan vain tarkkoja hakuja.
Tries-rakenteet todellisissa järjestelmissä
Trien todellisia käyttökohteita ovat esimerkiksi automaattinen täydennys (Google-haun ehdotukset), oikeinkirjoituksen tarkistimet (lähimpien vastaavien sanojen löytäminen), IP-reititys (pisimmän etuliitteen täsmäytys reitittimissä), T9-ennakoiva tekstinsyöttö (merkkien erottelu) ja DNS-resolverit (hierarkkinen toimialuenimien haku). Kussakin tapauksessa trien O(m)-aikavaativuus operaatiota kohden ja O(ALPHABET × nodes) -tilavaativuus tekevät niistä sopivan työkalun nopeisiin ja etuliitteet huomioiviin hakuihin suuressa mittakaavassa.
Pikatesti
Testatkaa ymmärrystänne tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -käsitteistä.
Oppitunnin kertaus
Tässä oppitunnissa opitte, että TrieNode sisältää children-sanakirjan ja is_end-totuusarvon, insert kulkee merkit yksitellen läpi, luo tarvittavat solmut ja asettaa is_end-arvon lopussa ja search tarkistaa is_end-arvon, kun taas starts_with tarkistaa vain, onko etuliitettä vastaava polku olemassa. Seuraavaksi lisäämme etuliitteisiin perustuvan automaattisen täydennyksen ja perehdymme starts_with-metodiin tarkemmin.
Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 90
- Oppitunnit
- 360
Usein kysytyt kysymykset
Onko oppitunti ”TrieNode-luokka: lisäys ja haku” ilmainen?
Kyllä – oppitunnin ”TrieNode-luokka: lisäys ja haku” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”TrieNode-luokka: lisäys ja haku”?
Rakentakaa TrieNode, jossa on children-sanakirja ja is_end-lippu, toteuttakaa insert ja exact-search sekä analysoikaa operaation O(m)-aika, jossa m on sanan pituus. Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 1/4.
Kuinka kauan ”TrieNode-luokka: lisäys ja haku”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?
Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- TrieNode-luokka: lisäys ja haku
- Etuliitehaku ja Starts-With
- Jokerimerkit ja säännöllisten lausekkeiden haku tries-rakenteessa
- Word Search II: trie ja backtracking ruudukossa