trie (prefix tree) म्हणजे काय आणि ते केव्हा उपयोगी आहे?

Question

Accepted Answer

एक **trie** (prefix tree) हा एक tree आहे जेथे प्रत्येक **edge** एक character प्रतिनिधित्व करतो आणि **root पासूनचा प्रत्येक path** एक prefix spell करतो. ज्या शब्दांचे prefix समान आहे ते समान path शेअर करतात, ज्यामुळे 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) |

महत्वाचे म्हणजे, cost हे **word length L** वर अवलंबून असते, stored words च्या संख्यावर *नाही*.

## Trade-offs

- **Strengths:** fast prefix search; autocomplete; shared prefixes समान शब्दांसाठी space बचवतात.
- **Weaknesses:** प्रत्येक node साठी high memory overhead (प्रत्येक child map साठी); unrelated keys साठी hash set पेक्षा जास्त space वापरू शकते.

## महत्व

Tries autocomplete, spell-checkers, IP routing tables, आणि dictionary-based search चालवतात जेथे **prefix** matching महत्वाचे आहे.

जेव्हा hash set फक्त "exact match" उत्तर देते, तेव्हा trie अतिरिक्तपणे "कोणते शब्द X सह सुरू होतात?" हे कार्यक्षमतेने उत्तर देते.