অক্ষরের একটি tree, যা "কোনো শব্দ কি এই অক্ষর দিয়ে শুরু হয়?" প্রশ্নের উত্তর খুব দ্রুত দেয়।
মূল ধারণা (ফোনের auto-complete)
আপনি "ca" লিখলে ফোন যখন "cat", "car" আর "cart" suggest করে, তখন পুরো ডিকশনারি scan না করেই "ca" দিয়ে শুরু হওয়া প্রতিটি শব্দ খুঁজে বের করতে হয়। Trie শব্দগুলোকে একটিমাত্র root থেকে অক্ষরের path হিসেবে রাখে। যেসব শব্দের শুরু একই, তারা path-এর শুরুটা ভাগ করে নেয়।
Insert: নিচের দিকে হাঁটুন, প্রতি ধাপে একটি অক্ষর। সেই অক্ষরের edge না থাকলে বানান। শেষ node-কে "এখানে একটি word শেষ" হিসেবে mark করুন (double circle দিয়ে আঁকা)।
Search: শব্দটির অক্ষর ধরে নামুন। edge না থাকলে শব্দটি নেই। পৌঁছাতে পারলেও শব্দটি আছে শুধু তখনই, যখন শেষ node-টি word end হিসেবে mark করা।
StartsWith prefix: একই পথ, কিন্তু পৌঁছাতে পারলেই যথেষ্ট।
খেয়াল করুন: car, cart-এর prefix। দুটোই word হতে পারে, তাই "word end" আলাদা একটা mark, "কোনো children নেই" এর সমান নয়।
Run করে দেখুন
নিজে চেষ্টা করুন
cat, car, cart insert করুন। আপনার লেখা 10টি অক্ষরের তুলনায় tree-তে কয়টি node হলো? এই সাশ্রয়টাই trie-র মূল সুবিধা।
search ca run করুন, তারপর prefix ca। উত্তর আলাদা কেন?
do আর dog থাকা অবস্থায় search dot run করুন। হাঁটা কোথায় থামে?
apple, zebra-র মতো একেবারে আলাদা দুটি word insert করুন। তারা কি কিছু ভাগ করে?
সাধারণ ভুল
word-end flag ভুলে যাওয়া। এটা না থাকলে "cat" রাখার পর Search("ca") ভুলভাবে yes বলত।
children map initialize না করা। Go-তে nil map-এ লিখলে panic হয়, তাই প্রতিটি নতুন node-এর জন্য map[rune]*Trie{} বানান।
Search আর StartsWith গুলিয়ে ফেলা। Search-এ end flag লাগে; StartsWith-এ লাগে না।
Memory। প্রতিটি node-এ একটি map থাকে। শুধু lowercase অক্ষরের জন্য [26]*Trie array দ্রুততর এবং প্রায়ই ছোট হয়।
Complexity, সহজ ভাষায়: insert, search আর prefix check, সবকটিতে শব্দের প্রতিটি অক্ষরের জন্য একটি করে ধাপ লাগে, কতগুলো word store করা আছে তাতে কিছু যায় আসে না (L অক্ষরের word-এর জন্য O(L))। বিনিময়ে memory লাগে: store করা প্রতিটি অক্ষরের জন্য সর্বোচ্চ একটি node।