Trie (Prefix Tree)

অক্ষরের একটি tree, যা "কোনো শব্দ কি এই অক্ষর দিয়ে শুরু হয়?" প্রশ্নের উত্তর খুব দ্রুত দেয়।

মূল ধারণা (ফোনের auto-complete)

আপনি "ca" লিখলে ফোন যখন "cat", "car" আর "cart" suggest করে, তখন পুরো ডিকশনারি scan না করেই "ca" দিয়ে শুরু হওয়া প্রতিটি শব্দ খুঁজে বের করতে হয়। Trie শব্দগুলোকে একটিমাত্র root থেকে অক্ষরের path হিসেবে রাখে। যেসব শব্দের শুরু একই, তারা path-এর শুরুটা ভাগ করে নেয়।

খেয়াল করুন: car, cart-এর prefix। দুটোই word হতে পারে, তাই "word end" আলাদা একটা mark, "কোনো children নেই" এর সমান নয়।

Run করে দেখুন

নিজে চেষ্টা করুন

সাধারণ ভুল

Complexity, সহজ ভাষায়: insert, search আর prefix check, সবকটিতে শব্দের প্রতিটি অক্ষরের জন্য একটি করে ধাপ লাগে, কতগুলো word store করা আছে তাতে কিছু যায় আসে না (L অক্ষরের word-এর জন্য O(L))। বিনিময়ে memory লাগে: store করা প্রতিটি অক্ষরের জন্য সর্বোচ্চ একটি node।