trie (prefix tree) کیا ہے اور یہ کب مفید ہے؟

Question

Accepted Answer

ایک **trie** (prefix tree) ایک درخت ہے جہاں ہر **edge** ایک حرف کو ظاہر کرتا ہے اور ہر **path root سے** ایک prefix کو ہجی کرتا ہے۔ الفاظ جو ایک prefix کو شیئر کرتے ہیں وہ ایک جیسا path شیئر کرتے ہیں، جس سے prefix تلاش بہت تیز ہو جاتی ہے۔

## ڈھانچہ

```text
Insert "cat", "car", "dog":
        root
       /    \
      c      d
      |      |
      a      o
     / \     |
    t*  r*   g*       (* marks end-of-word)
```

## Code

```python
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
```

## Complexity

| Operation | Time |
|---|---|
| insert | O(L) |
| search | O(L) |
| prefix query | O(L) |

بہت اہم بات یہ ہے کہ cost **لفظ کی لمبائی L** پر منحصر ہے، محفوظ لفظوں کی تعداد پر نہیں۔

## Trade-offs

- **طاقتیں:** تیز prefix search؛ autocomplete؛ مشترکہ prefixes سے ملتے جلتے الفاظ میں جگہ بچتی ہے۔
- **کمزوریاں:** ہر node میں میموری کا بہت زیادہ overhead (ہر child کے لیے ایک map)؛ غیر متعلقہ keys کے لیے hash set سے زیادہ جگہ استعمال کر سکتے ہیں۔

## اہمیت

Tries autocomplete، spell-checkers، IP routing tables، اور dictionary پر مبنی تلاش میں استعمال ہوتے ہیں جہاں **prefix** matching اہم ہو۔

جہاں hash set صرف "exact match" کا جواب دیتا ہے، وہاں trie اضافی طور پر "کون سے لفظ X سے شروع ہوتے ہیں؟" کا جواب مؤثر طریقے سے دے سکتا ہے۔