# Trie — डेटा स्ट्रक्चर और एल्गोरिदम

Source: https://www.geekswithgeeks.com/hi/dsa/trie

> Prefix tree: प्रति वर्ण एक node, साझा prefix के साथ।

## पथ के रूप में शब्द

हर शब्द root से एक पथ है, प्रति वर्ण एक edge। `cat` और `car` `c-a` पथ साझा करते हैं फिर अलग होते हैं। Lookup, insert, और prefix जाँच `O(L)` हैं जहाँ `L` शब्द की लंबाई — संग्रहीत शब्दों की संख्या से स्वतंत्र।

## Insert और search

Node केवल child वर्णों का map और end-of-word flag है।

```python
class Trie:
    def __init__(self):
        self.root = {}
    def insert(self, word):
        node = self.root
        for c in word:
            node = node.setdefault(c, {})
        node['$'] = True          # word ends here
    def search(self, word):
        node = self.root
        for c in word:
            if c not in node: return False
            node = node[c]
        return '$' in node
```

## फ़ोन संपर्क

'Jo' टाइप करें और फ़ोन तुरंत John, Joanna, Joseph तक सीमित हो जाता है। यह नामों की trie में दो edge नीचे चला।

## यह कहाँ छिपा है

Autocomplete, spell-check, IP routing table, और word-search / prefix समस्याएँ। ट्रेड-ऑफ: प्रति वर्ण भारी पॉइंटर overhead।