Trie
ট্রাই
Key-গুলোর shared prefix character-এ character-এ ভাগ করে রাখা retrieval tree — lookup-এর সময় নির্ভর করে শুধু key-এর length-এর উপর, dictionary size n-এর উপর নয়।
also: prefix tree, digital tree, retrieval tree
cat, car, code এক trie-তে:
c ─┬─ a ─┬─ t (cat)
│ └─ r (car)
└─ o ─ d ─ e (code)Lookup cost O(L), L = key length — dictionary million word হলেও ৫-letter word ৫ ধাপেই মেলে। Prefix query free: subtree-ই “ca-” দিয়ে শুরু হওয়া সব word-এর উত্তর।
Trade-off: প্রতি node memory hash table-এর চেয়ে বেশি, কিন্তু prefix operation আর sorted iteration hash table দিতে পারে না। Autocomplete, spell-checker, IP routing (bitwise trie) — trie-র ঘাঁটি।