একটি trie (প্রিফিক্স ট্রি) হল একটি ট্রি যেখানে প্রতিটি edge একটি অক্ষর প্রতিনিধিত্ব করে এবং মূল থেকে প্রতিটি পথ একটি প্রিফিক্স গঠন করে। যে শব্দগুলি একটি প্রিফিক্স শেয়ার করে তারা একই পথ শেয়ার করে, যা প্রিফিক্স সার্চকে অত্যন্ত দ্রুত করে তোলে।
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 এর উপর নির্ভর করে, সংরক্ষিত শব্দের সংখ্যার উপর নয়।
Tries অটোকমপ্লিট, বানান-চেকার, IP রাউটিং টেবিল এবং ডিকশনারি-ভিত্তিক সার্চকে শক্তি দেয় যেখানে প্রিফিক্স ম্যাচিং গুরুত্বপূর্ণ।
যখন একটি hash set শুধুমাত্র "সঠিক ম্যাচ?" উত্তর দেয়, একটি trie অতিরিক্তভাবে দক্ষতার সাথে "কোন শব্দগুলি X দিয়ে শুরু হয়?" উত্তর দেয়।