ટ્રાય (પ્રીફિક્સ ટ્રી) શું છે અને તે ક્યારે ઉપયોગી છે?

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.

## તે શા માટે મહત્વપૂર્ણ છે

ટ્રાયઝ ઓટોકમ્પ્લીટ, સ્પેલ-ચેકર્સ, IP રૂટીંગ ટેબલ્સ અને શબ્દકોષ-આધારિત શોધને શક્તિ આપે છે જ્યાં **પ્રીફિક્સ** મેચિંગ મહત્વપૂર્ણ છે.

જ્યારે હેશ સેટ માત્ર "સચોટ મેચ"નો જવાબ આપે છે, ત્યારે trie વધુમાં "X થી શરૂ થતા કયા શબ્દો છે?" કાર્યક્ષમતાથી જવાબ આપે છે.