TrieNode-Klasse: Einfügen und Suchen
Erstellen Sie einen TrieNode mit einem children-Dictionary und einem is_end-Flag, implementieren Sie insert und exact-search und analysieren Sie die Laufzeit O(m) pro Operation, wobei m die Wortlänge ist.
TrieNode-Klasse: Einfügen und Suchen ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 1 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was ist ein Trie?
Ein Trie (Präfixbaum) ist eine baumförmige Datenstruktur, in der jeder Knoten ein Zeichen repräsentiert. Wörter werden gespeichert, indem Zeichen von der Wurzel bis zu einem Blatt verkettet werden. Die Wurzel repräsentiert eine leere Zeichenkette. Jeder Pfad von der Wurzel zu einem is_end = True-Knoten ergibt ein gespeichertes Wort. Tries sind ideal für präfixbasierte Abfragen wie Autovervollständigung, Rechtschreibprüfung und IP-Routing und übertreffen Hash-Maps in diesen Anwendungsfällen.
Entwurf der TrieNode-Klasse
Eine TrieNode besitzt zwei Felder: children — ein Wörterbuch, das Zeichen auf untergeordnete TrieNode-Objekte abbildet — und is_end — einen booleschen Wert, der markiert, ob dieser Knoten das Ende eines gespeicherten Wortes ist. Die Verwendung eines Wörterbuchs (statt eines Arrays mit fester Länge 26) verallgemeinert die Struktur auf beliebige Zeichensätze und spart bei dünn besetzten Tries Speicher. Jeder Knoten im Trie repräsentiert genau eine Zeichenposition in den darunter gespeicherten Wörtern.
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)Einfügeoperation
Um ein Wort einzufügen, durchlaufen Sie den Trie von der Wurzel aus und erstellen für jedes Zeichen, das in den children des aktuellen Knotens noch nicht vorhanden ist, eine neue TrieNode. Nachdem alle Zeichen verarbeitet wurden, setzen Sie is_end = True am letzten Knoten. Das Einfügen von 'apple' und 'app' erzeugt die Kette a→p→p→l→e (is_end=True für 'apple'); der p an Position 3 wird für 'app' ebenfalls als is_end=True markiert.
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)Suchoperation
Um nach einem exakten Wort zu suchen, durchlaufen Sie den Trie und folgen jedem Zeichen. Fehlt ein Zeichen in den children des aktuellen Knotens, geben Sie False zurück. Wenn alle Zeichen gefunden wurden, geben Sie node.is_end zurück — True nur dann, wenn genau hier ein Wort endet (nicht lediglich ein Präfix). Diese Unterscheidung zwischen „Präfix ist vorhanden“ und „exaktes Wort ist vorhanden“ ist entscheidend und wird häufig geprüft.
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 (Präfixsuche)
Die Methode starts_with prüft, ob ein eingefügtes Wort mit dem angegebenen Präfix beginnt. Sie folgt demselben Durchlauf wie die Suche, gibt aber statt einer Prüfung von is_end True zurück, sobald alle Präfixzeichen erfolgreich verfolgt wurden — das bedeutet, dass der Präfixpfad im Trie existiert.
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)Zeit- und Speicherkomplexität
Jede Trie-Operation (insert, search, starts_with) benötigt O(m) Zeit, wobei m die Wortlänge ist — es werden höchstens m Knoten durchlaufen. Speicherbedarf: O(ALPHABET_SIZE × N × M), wobei N die Anzahl der Wörter und M die durchschnittliche Wortlänge ist. In der Praxis verringern gemeinsame Präfixe den Speicherbedarf erheblich. Ein auf einer Hash-Map basierendes children-Dictionary benötigt bei dünn besetzten Tries weniger Speicher als ein Array mit 26 festen Zeichenpositionen, verursacht dafür aber einen etwas höheren konstanten Overhead pro Nachschlagen.
Array statt Dict verwenden
Für ausschließlich kleingeschriebene englische Buchstaben verwenden Sie ein Array fester Größe children = [None] * 26 mit dem Index ord(c) - ord('a'). Dies ist schneller (O(1)-Nachschlagen von Kindern statt einer Hash-Map) und bietet ein vorhersehbares Speicherlayout. Verwenden Sie die Dict-Variante, wenn der Zeichensatz groß oder unbekannt ist (z. B. Unicode), und die Array-Variante bei wettbewerbsorientierten Aufgaben mit ausschließlich kleingeschriebenen Buchstaben.
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')) # FalseLöschoperation
Das Löschen aus einem Trie muss drei Fälle behandeln: (1) Wort nicht vorhanden — nichts tun; (2) Wort vorhanden, aber Präfix eines anderen Wortes — nur is_end zurücksetzen; (3) Wort vorhanden und kein Präfix — Knoten von unten nach oben löschen und anhalten, sobald ein Knoten weitere Kinder hat oder das Ende eines anderen Wortes ist. Das Löschen wird in Vorstellungsgesprächen selten geprüft, ist aber konzeptionell wissenswert.
Wörter mit einem Präfix zählen
Erweitern Sie jeden Knoten um ein count-Feld, das bei jedem Durchlauf während des Einfügens inkrementiert wird. Um Wörter mit einem bestimmten Präfix zu zählen, durchlaufen Sie den Trie bis zum Endknoten des Präfixes und geben dessen count zurück. Dadurch sind Autovervollständigungsabfragen in O(m) möglich, ohne alle Kinder zu durchlaufen — eine nützliche Erweiterung für Autovervollständigungssysteme aus der Praxis.
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')) # 3Trie- und Hash-Map-Vergleich
Eine Hash-Map kann eine exakte Suche durchschnittlich in O(m) durchführen, Präfixabfragen jedoch nicht effizient beantworten (dafür müssten alle Schlüssel durchsucht werden). Ein Trie beantwortet Präfixabfragen in O(p), wobei p die Präfixlänge ist, gruppiert Wörter auf natürliche Weise nach gemeinsamen Präfixen und benötigt kein Hashing. Verwenden Sie einen Trie bei häufigen Präfixabfragen, Autovervollständigung oder Rechtschreibprüfung. Verwenden Sie eine Hash-Map, wenn nur exakte Suchen erforderlich sind.
Tries in realen Systemen
Zu den Einsatzgebieten von Tries in der Praxis gehören: Autovervollständigung (Google-Suchvorschläge), Rechtschreibprüfungen (Finden ähnlichster übereinstimmender Wörter), IP-Routing (Longest-Prefix-Matching in Routern), T9-Prädiktiveingabe (Auflösen mehrdeutiger Zeichen) und DNS-Resolver (hierarchische Suche nach Domainnamen). In jedem dieser Fälle macht die Abwägung zwischen O(m) pro Operation und O(ALPHABET × nodes) Speicherbedarf den Trie zum richtigen Werkzeug für schnelle, präfixbasierte Suchen in großem Maßstab.
Schnelltest
Überprüfen Sie Ihr Verständnis der Konzepte von Data Structures & Algorithms — Coding Interview Prep aus dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: ein TrieNode ein children-Dictionary und einen booleschen Wert is_end besitzt, insert Zeichen für Zeichen durchläuft, bei Bedarf Knoten erstellt und am Ende is_end setzt und search is_end prüft, während starts_with nur überprüft, ob der Präfixpfad existiert. Als Nächstes fügen wir präfixbasierte Autovervollständigung hinzu und betrachten die Methode starts_with ausführlicher.
Häufig gestellte Fragen
Ist die Lektion „TrieNode-Klasse: Einfügen und Suchen“ kostenlos?
Ja — der vollständige Text von „TrieNode-Klasse: Einfügen und Suchen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „TrieNode-Klasse: Einfügen und Suchen“?
Erstellen Sie einen TrieNode mit einem children-Dictionary und einem is_end-Flag, implementieren Sie insert und exact-search und analysieren Sie die Laufzeit O(m) pro Operation, wobei m die Wortlänge… Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 1 von 4.
Wie lange dauert die Lektion „TrieNode-Klasse: Einfügen und Suchen“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- TrieNode-Klasse: Einfügen und Suchen
- Präfixsuche und Starts-With
- Wildcard- und Regex-Suche in einem Trie
- Word Search II: Trie und Backtracking auf einem Gitter