DSA Interview Prep · leksjon

TrieNode-klassen: Sett inn og søk

Bygg en TrieNode med children-dictionary og is_end-flagget, implementer insert og eksakt søk, og analyser O(m)-tid per operasjon, der m er ordlengden.

Leksjon 1 av 413 trinn

TrieNode-klassen: Sett inn og søk er en gratis leksjon i DSA Interview Prep på CoddyKit. Dette er leksjon 1 av 4. Du kan lese valgfritt 3 leksjoner fra denne læringsstien gratis i sin helhet – deretter låser CoddyKit PRO opp alle leksjoner, samt praktisk øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i DSA Interview Prep, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i DSA Interview Prep inneholder totalt 4 leksjoner.

Hva er en Trie?

En Trie (prefikstre) er en treformet datastruktur der hver node representerer et tegn. Ord lagres ved å lenke sammen tegn fra rot til blad. Roten representerer en tom streng. Hver sti fra roten til en is_end = True-node utgjør et lagret ord. Tries egner seg spesielt godt til prefiksspørringer som autofullføring, stavekontroll og IP-ruting, og gir bedre ytelse enn hash maps i disse bruksområdene.

Utforming av TrieNode-klassen

En TrieNode har to felt: children — et dictionary som knytter tegn til underordnede noder av typen TrieNode — og is_end — en boolsk verdi som markerer om denne noden er slutten på et lagret ord. Bruk av et dictionary (i stedet for en array med fast størrelse på 26 tegn) gjør løsningen generell for alle tegnsett og sparer minne i glisne tries. Hver node i Trien representerer nøyaktig én tegnposisjon 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)

Innsettingsoperasjon

For å sette inn et ord går du gjennom Trien fra roten og oppretter en ny TrieNode for hvert tegn som ikke allerede finnes blant den gjeldende nodens children. Når alle tegnene er behandlet, settes is_end = True på den siste noden. Når 'apple' og 'app' settes inn, opprettes kjeden a→p→p→l→e (is_end=True for 'apple'), og p-en i posisjon 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økeoperasjon

For å søke etter et eksakt ord går du gjennom Trien ved å følge hvert tegn. Hvis et tegn mangler blant den gjeldende nodens children, returner False. Hvis alle tegnene blir funnet, returner node.is_end — True bare hvis et ord slutter nøyaktig her, ikke bare et prefiks. Dette skillet mellom at et prefiks finnes og at et eksakt ord finnes, er avgjørende og testes 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'))  # False

Starts-With (prefikssøk)

Metoden starts_with sjekker om et innlagt ord har det angitte prefikset. Den følger samme gjennomgang som search, men i stedet for å sjekke is_end returnerer den True så snart alle prefikstegnene er fulgt — det betyr at prefiksstien finnes 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 plasskompleksitet

Hver Trie-operasjon (insert, search, starts_with) tar O(m)-tid, der m er ordlengden — vi går gjennom høyst m noder. Plass: O(ALPHABET_SIZE × N × M), der N er antallet ord og M er den gjennomsnittlige ordlengden. I praksis reduserer delte prefikser plassbruken betydelig. Et dictionary for children basert på hash map bruker mindre plass enn en array med fast størrelse på 26 tegn for glisne tries, men har noe større konstant overhead ved hvert oppslag.

Bruk av array i stedet for dict

For bare engelske små bokstaver kan du bruke en array med fast størrelse: children = [None] * 26, med indeksen ord(c) - ord('a'). Dette er raskere (O(1)-oppslag av barnenode sammenlignet med hash map) og gir et forutsigbart minneoppsett. Bruk dictionary-versjonen når tegnsettet er stort eller ukjent (for eksempel Unicode), og array-versjonen i konkurranseoppgaver som bare bruker små bokstaver.

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'))  # False

Sletteoperasjon

Sletting fra en Trie må håndtere tre tilfeller: (1) ordet finnes ikke — ikke gjør noe; (2) ordet finnes, men er et prefiks for et annet ord — fjern bare is_end; (3) ordet finnes og er ikke et prefiks — slett noder nedenfra og opp, og stopp når en node har andre barn eller er slutten på et annet ord. Sletting testes sjelden i intervjuer, men det er nyttig å kjenne konseptet.

Telle ord med et prefiks

Utvid hver node med et count-felt som økes hver gang en innsetting passerer gjennom noden. For å telle ord med et gitt prefiks går du til prefiksets siste node og returnerer verdien i count. Dette muliggjør autofullføringsspørringer på O(m)-tid uten å gå gjennom alle barna — en nyttig utvidelse for praktiske autofullføringssystemer.

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'))  # 3

Sammenligning av Trie og hash map

Et hash map kan gjøre eksakt oppslag i gjennomsnittlig O(m)-tid, men kan ikke besvare prefiksspørringer effektivt (det krever skanning av alle nøkler). En Trie besvarer prefiksspørringer på O(p)-tid, der p er prefikslengden, grupperer naturlig ord etter delte prefikser og trenger ikke hashing. Bruk en Trie når det er mange prefiksspørringer, for eksempel ved autofullføring og stavekontroll. Bruk et hash map når det bare er behov for eksakte oppslag.

Tries i virkelige systemer

Tries brukes blant annet i virkelige systemer til autofullføring (Googles søkeforslag), stavekontroller (finne ord som ligner mest), IP-ruting (matching av lengste prefiks i rutere), prediktiv T9-tekst (tolking av tegn) og DNS-resolvere (hierarkisk oppslag av domenenavn). I hvert tilfelle gjør avveiningen mellom O(m) per operasjon og O(ALPHABET × nodes) plass Trien til riktig verktøy for raske oppslag med prefiksstøtte i stor skala.

Kunnskapssjekk

Test forståelsen av konseptene Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.

Besvar den i den interaktive leksjonen

Oppsummering av leksjonen

I denne leksjonen lærte du: en TrieNode har et children-dictionary og en is_end-boolsk verdi, insert går gjennom tegn for tegn, oppretter noder etter behov og setter is_end til slutt, og search sjekker is_end, mens starts_with bare sjekker om prefiksstien finnes. Neste gang legger vi til prefiksbasert autofullføring og går mer i dybden på metoden starts_with.

Gratis å komme i gang

Lær deg Python med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs: 30
Leksjoner: 120

Start læringen gratis Se hele kurset

Ofte stilte spørsmål

Er leksjonen «TrieNode-klassen: Sett inn og søk» gratis?

Ja – du kan lese valgfritt 3 av leksjonene i læringsstien DSA Interview Prep, inkludert «TrieNode-klassen: Sett inn og søk», gratis i sin helhet her på nettet. Deretter låser CoddyKit PRO opp alle leksjoner, samt interaktiv øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Kurset i DSA Interview Prep inneholder totalt 4 leksjoner.

Hva lærer jeg i «TrieNode-klassen: Sett inn og søk»?

Bygg en TrieNode med children-dictionary og is_end-flagget, implementer insert og eksakt søk, og analyser O(m)-tid per operasjon, der m er ordlengden. Du øver på DSA Interview Prep med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med DSA Interview Prep?

Ingen tidligere erfaring er nødvendig. DSA Interview Prep på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 1 av 4.

Hvor lang tid tar leksjonen «TrieNode-klassen: Sett inn og søk»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne DSA Interview Prep-leksjonen?

Ja. Alle DSA Interview Prep-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

TrieNode-klassen: Sett inn og søk
Prefikssøk og Starts-With
Søk med jokertegn og regulære uttrykk i et trie
Word Search II: Trie og tilbakesporing i rutenett

← Tilbake til DSA Interview Prep