एक trie (prefix tree) के हो र यो कहिले उपयोगी छ?

Question

Accepted Answer

एक **trie** (prefix tree) एक रुख हो जहाँ प्रत्येक **edge** एक अक्षर प्रतिनिधित्व गर्छ र प्रत्येक **root बाट को पथ** एक prefix को वर्णन गर्छ। एक अग्रभाग साझा गर्ने शब्दहरूले एक ही पथ साझा गर्छन्, जसले prefix lookups अत्यन्त छिटो बनाउँछ।

## संरचना

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

महत्त्वपूर्ण कुरा यो हो कि लागत **शब्द लम्बाई L** मा निर्भर गर्छ, संग्रहीत शब्दहरूको संख्यामा होइन।

## Trade-offs

- **शक्तिशाली पक्षहरू:** छिटो prefix खोज; autocomplete; साझा prefixes समान शब्दहरूको लागि स्थान बचाउँछ।
- **कमजोरी पक्षहरू:** प्रत्येक नोडमा उच्च मेमोरी ओभरहेड (प्रत्येकको लागि एक child map); असम्बन्धित कुञ्जीहरूको लागि hash set भन्दा बढी स्थान प्रयोग गर्न सक्छ।

## यो किन महत्त्वपूर्ण छ

Tries ले autocomplete, spell-checkers, IP routing tables, र dictionary-based search को शक्ति दिन्छ जहाँ **prefix** matching मायने राख्छ।

जब एक hash set केवल "exact match" को जवाफ दिन्छ, एक trie अतिरिक्त रूपमा "कुन शब्दहरू X संग सुरु हुन्छन्?" लाई प्रभावकारी रूपमा जवाफ दिन्छ।