ट्राई (प्रीफिक्स ट्री) क्या है और यह कब उपयोगी है?

Question

Accepted Answer

एक **trie** (प्रीफिक्स ट्री) एक पेड़ है जहां प्रत्येक **edge** एक अक्षर का प्रतिनिधित्व करता है और प्रत्येक **रूट से पथ** एक प्रीफिक्स बनाता है। जो शब्द प्रीफिक्स साझा करते हैं वे एक ही पथ साझा करते हैं, जिससे प्रीफिक्स लुकअप अत्यंत तेज़ हो जाते हैं।

## Structure

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

Crucially, cost depends on the **word length L**, *not* the number of stored words.

## Trade-offs

- **Strengths:** fast prefix search; autocomplete; shared prefixes save space for similar words.
- **Weaknesses:** high memory overhead per node (a child map for each); can use more space than a hash set for unrelated keys.

## यह महत्वपूर्ण क्यों है

Tries ऑटोकंप्लीट, स्पेल-चेकर्स, IP रूटिंग टेबल्स, और शब्दकोश-आधारित खोज को शक्ति देते हैं जहां **प्रीफिक्स** मिलान महत्वपूर्ण है।

जब hash set केवल "सटीक मिलान" का उत्तर देता है, तो trie अतिरिक्त रूप से "X से शुरू होने वाले कौन से शब्द हैं?" कुशलतापूर्वक का उत्तर देता है।