TrieNode-klassen: Indsættelse og søgning
Opret en TrieNode med en children-dict og et is_end-flag, implementér insert og exact-search, og analysér en køretid på O(m) pr. operation, hvor m er ordlængden.
TrieNode-klassen: Indsættelse og søgning er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 1 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad er en trie?
En trie (præfikstræ) er en trælignende datastruktur, hvor hver knude repræsenterer et tegn. Ord gemmes ved at kæde tegn sammen fra rod til blad. Roden repræsenterer en tom streng. Hver sti fra roden til en is_end = True-knude staver et gemt ord. Tries er ideelle til præfiksbaserede forespørgsler som autofuldførelse, stavekontrol og IP-routing og klarer disse anvendelser bedre end hashtabeller.
Design af TrieNode-klassen
En TrieNode har to felter: children — en ordbog, der knytter tegn til underordnede TrieNode'er — og is_end — en boolsk værdi, der markerer, om denne knude er slutningen på et gemt ord. Ved at bruge en ordbog i stedet for et array med 26 faste tegn bliver løsningen anvendelig til alle tegnsæt, og du sparer hukommelse i sparsomme tries. Hver knude i trien repræsenterer præcis én tegnposition i ordene under den.
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)Indsættelsesoperation
Hvis du vil indsætte et ord, skal du gennemløbe trien fra roden og oprette en ny TrieNode for hvert tegn, der endnu ikke findes blandt den aktuelle knudes children. Når alle tegn er behandlet, skal du sætte is_end = True på den sidste knude. Hvis du indsætter 'apple' og 'app', oprettes kæden a→p→p→l→e (is_end=True for 'apple'), og p'et på position 3 markeres også med is_end=True for '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)Søgeoperation
Hvis du vil søge efter et nøjagtigt ord, skal du gennemløbe trien ved at følge hvert tegn. Hvis et tegn mangler blandt den aktuelle knudes children, skal du returnere False. Hvis alle tegn findes, skal du returnere node.is_end — True kun hvis et ord slutter præcis her, ikke bare et præfiks. Denne forskel mellem »præfiks findes« og »det nøjagtige ord findes« er afgørende og afprøves ofte.
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')) # FalseBegynder med (præfikssøgning)
Metoden starts_with undersøger, om et indsat ord har det angivne præfiks. Den følger samme gennemløb som search, men i stedet for at kontrollere is_end returnerer den True, så snart alle præfikstegn er fulgt korrekt — det betyder, at præfiksstien findes i trien.
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)Tids- og pladskompleksitet
Hver trieoperation (insert, search, starts_with) tager O(m) tid, hvor m er ordlængden — du gennemløber højst m knuder. Pladsforbruget er O(ALPHABET_SIZE × N × M), hvor N er antallet af ord, og M er den gennemsnitlige ordlængde. I praksis reducerer fælles præfikser pladsforbruget betydeligt. En children-ordbog baseret på en hashtabel bruger mindre plads end et array med 26 faste tegn i sparsomme tries, men har et lidt større konstant overhead pr. opslag.
Brug af et array i stedet for Dict
Hvis du kun arbejder med små engelske bogstaver, kan du bruge et array med fast størrelse: children = [None] * 26 med indekset ord(c) - ord('a'). Det er hurtigere (O(1)-opslag af en underordnet knude mod opslag i en hashtabel) og har et forudsigeligt hukommelseslayout. Brug dict-versionen, når tegnsættet er stort eller ukendt, f.eks. Unicode, og array-versionen til opgaver fra programmeringskonkurrencer, der kun bruger små bogstaver.
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')) # FalseSletteoperation
Sletning fra en trie skal håndtere tre tilfælde: (1) Ordet findes ikke — gør ingenting. (2) Ordet findes, men er et præfiks for et andet ord — nulstil kun is_end. (3) Ordet findes og er ikke et præfiks — slet knuder nedefra og op, og stop, når en knude har andre underordnede knuder eller markerer slutningen på et andet ord. Sletning afprøves sjældent ved jobsamtaler, men det er godt at kende princippet.
Optælling af ord med et præfiks
Udvid hver knude med et count-felt, der øges ved hver gennemgang under en indsættelse. Hvis du vil tælle ord med et bestemt præfiks, skal du gennemløbe trien til præfiks-slutknuden og returnere dens count. Det giver O(m)-forespørgsler om autofuldførelse uden at gennemløbe alle underordnede knuder — en nyttig udvidelse til autofuldførelsessystemer i virkelige løsninger.
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')) # 3Sammenligning af trie og hashtabel
En hashtabel kan slå et nøjagtigt ord op på O(m) tid i gennemsnit, men kan ikke besvare præfiksforespørgsler effektivt, fordi det kræver en gennemgang af alle nøgler. En trie besvarer præfiksforespørgsler på O(p), hvor p er præfikslængden, grupperer naturligt ord efter fælles præfikser og kræver ikke hashberegning. Brug en trie ved hyppige præfiksforespørgsler, autofuldførelse og stavekontrol. Brug en hashtabel, når der kun er behov for eksakte opslag.
Tries i virkelige systemer
Tries bruges blandt andet til: autofuldførelse (Googles søgeforslag), stavekontroller (at finde ord med den bedste overensstemmelse), IP-routing (matchning af længste præfiks i routere), T9-prediktiv tekst (entydiggørelse af tegn) og DNS-resolvere (hierarkisk opslag af domænenavne). I hvert tilfælde gør trien's O(m) pr. operation og pladsforbruget på O(ALPHABET × antallet af knuder) den til det rigtige værktøj til hurtige, præfiksbevidste opslag i stor skala.
Hurtigt tjek
Afprøv din forståelse af begreberne fra lektionen Data Structures & Algorithms — Coding Interview Prep.
Opsummering af lektionen
I denne lektion lærte du: En TrieNode har en children-dict og en boolsk is_end-værdi, insert gennemløber tegn for tegn, opretter knuder efter behov og sætter is_end til sidst, og search kontrollerer is_end, mens starts_with kun kontrollerer, om præfiksstien findes. Næste gang tilføjer vi præfiksbaseret autofuldførelse og går mere i dybden med metoden starts_with.
Lær Forberedelse til kodeinterviews med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “TrieNode-klassen: Indsættelse og søgning” gratis?
Ja — hele teksten til “TrieNode-klassen: Indsættelse og søgning” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “TrieNode-klassen: Indsættelse og søgning”?
Opret en TrieNode med en children-dict og et is_end-flag, implementér insert og exact-search, og analysér en køretid på O(m) pr. operation, hvor m er ordlængden. Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 1 af 4.
Hvor lang tid tager lektionen “TrieNode-klassen: Indsættelse og søgning”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- TrieNode-klassen: Indsættelse og søgning
- Præfikssøgning og Starts-With
- Wildcard- og regex-søgning i et trie
- Word Search II: Trie + backtracking på et gitter