Trie (ఉపసర్గ చెట్టు) అనేది చెట్టు, ఇక్కడ ప్రతి అంచు ఒక చరిత్రను సూచిస్తుంది మరియు రూట్ నుండి ప్రతి మార్గం ఒక ఉపసర్గను ఏర్పరుస్తుంది. ఉపసర్గను సంభాగించే పదాలు ఒకే మార్గాన్ని సంభాగించుకుంటాయి, ఇది ఉపసర్గ శోధనను చాలా వేగవంతంగా చేస్తుంది.
Insert "cat", "car", "dog":
root
/ \
c d
| |
a o
/ \ |
t* r* g* (* marks end-of-word)
class TrieNode:
def __init__(self):
self.children = {} # char -> TrieNode
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word): # O(L), L = word length
node = self.root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.is_end = True
def starts_with(self, prefix): # O(L)
node = self.root
for ch in prefix:
if ch not in node.children: return False
node = node.children[ch]
return True
| ఆపరేషన్ | సమయం |
|---|---|
| insert | O(L) |
| search | O(L) |
| prefix query | O(L) |
ముఖ్యంగా, వ్యయం పదం యొక్క పొడవు L పై ఆధారపడి ఉంటుంది, నిల్వ చేసిన పదాల సంఖ్య పై కాదు.
Trie ఆటోకంప్లీట్, స్పెల్-చెకర్లు, IP రూటింగ్ టేబిల్లు మరియు నిఘంటువ-ఆధారిత శోధనకు శక్తి నిస్సందేహంగా ఉంటుంది, ఇక్కడ ఉపసర్గ సరిపోలిక ముఖ్యమైనది.
హ్యాష్ సెట్ "సరిగ్గా సరిపోలిక"కు మాత్రమే సమాధానం ఇస్తుండగా, trie అదనంగా "X తో ఏ పదాలు ప్రారంభమవుతాయి?" కు సమర్థవంతంగా సమాధానం ఇస్తుంది.