ਇੱਕ trie (prefix tree) ਕਿਆ ਹੈ ਅਤੇ ਇਹ ਕਦੋਂ ਉਪਯੋਗੀ ਹੈ?

Question

Accepted Answer

ਇੱਕ **trie** (prefix tree) ਇੱਕ ਰੁੱਖ ਹੈ ਜਿਥੇ ਹਰੇਕ **edge** ਇੱਕ ਅੱਖਰ ਨੂੰ ਦਰਸਾਉਂਦੀ ਹੈ ਅਤੇ **root ਤੋਂ ਹਰੇਕ ਰਸਤਾ** ਇੱਕ ਪ੍ਰੇਫਿਕਸ ਨੂੰ ਸਪੈਲ ਕਰਦਾ ਹੈ। ਜੋ ਸ਼ਬਦ ਇੱਕ ਪ੍ਰੇਫਿਕਸ ਨੂੰ ਸਾਂਝਾ ਕਰਦੇ ਹਨ, ਉਹ ਉਹੀ ਰਸਤਾ ਸਾਂਝਾ ਕਰਦੇ ਹਨ, ਜਿਸ ਨਾਲ prefix lookups ਬਹੁਤ ਤੇਜ਼ ਹਨ।

## ਢਾਂਚਾ

```text
Insert "cat", "car", "dog":
        root
       /    \
      c      d
      |      |
      a      o
     / \     |
    t*  r*   g*       (* marks end-of-word)
```

## ਕੋਡ

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

## ਜਟਿਲਤਾ

| Operation | Time |
|---|---|
| insert | O(L) |
| search | O(L) |
| prefix query | O(L) |

ਮਹੱਤਵਪੂਰਨ ਤੌਰ 'ਤੇ, ਖਰਚ **ਸ਼ਬਦ ਦੀ ਲੰਬਾਈ L** 'ਤੇ ਨਿਰਭਰ ਕਰਦਾ ਹੈ, ਸਟੋਰ ਕੀਤੇ ਸ਼ਬਦਾਂ ਦੀ ਗਿਣਤੀ 'ਤੇ *ਨਹੀਂ*।

## Trade-offs

- **ਸ਼ਕਤੀਆਂ:** fast prefix search; autocomplete; ਸਾਂਝੇ ਪ੍ਰੇਫਿਕਸ ਸਮਾਨ ਸ਼ਬਦਾਂ ਲਈ ਥਾਂ ਬਚਾਉਂਦੇ ਹਨ।
- **ਕਮਜ਼ੋਰੀਆਂ:** ਪ੍ਰਤੀ node ਉੱਚ memory overhead (ਹਰੇਕ ਲਈ ਇੱਕ child map); ਸੰਬੰਧਿਤ ਨਹੀਂ ਕੁੰਜੀਆਂ ਲਈ hash set ਨਾਲੋਂ ਵਧੇਰੇ ਥਾਂ ਦੀ ਵਰਤੋਂ ਕਰ ਸਕਦੇ ਹਨ।

## ਇਹ ਮਹੱਤਵਪੂਰਨ ਕਿਉਂ ਹੈ

Tries autocomplete, spell-checkers, IP routing tables, ਅਤੇ dictionary-based search ਨੂੰ ਚਲਾਉਂਦੇ ਹਨ ਜਿਥੇ **prefix** matching ਮਹੱਤਵਪੂਰਨ ਹੈ।

ਜਦੋਂ ਇੱਕ hash set ਸਿਰਫ "exact match" ਦਾ ਜਵਾਬ ਦਿੰਦਾ ਹੈ, ਇੱਕ trie ਵਾਧੂ ਤੌਰ 'ਤੇ "ਕਿਹੜੇ ਸ਼ਬਦ X ਨਾਲ ਸ਼ੁਰੂ ਹੁੰਦੇ ਹਨ?" ਨੂੰ ਕੁਸ਼ਲਤਾ ਨਾਲ ਜਵਾਬ ਦਿੰਦਾ ਹੈ।