Trie (மொழியின் முன்னொட்டு மரம்) என்றால் என்ன மற்றும் எப்போது பயனுள்ளதாக இருக்கும்?

Question

Accepted Answer

**Trie** (முன்னொட்டு மரம்) என்பது ஒரு மரமாகும், இதில் ஒவ்வொரு **விளிம்பு** ஒரு எழுத்தைக் குறிக்கிறது மற்றும் **வேரிலிருந்து ஒவ்வொரு பாதை** ஒரு முன்னொட்டை உருவாக்குகிறது. ஒரு முன்னொட்டைப் பகிர்ந்து கொள்ளும் வார்த்தைகள் ஒரே பாதையைப் பகிர்ந்து கொள்கின்றன, இது முன்னொட்டு தேடலை மிகவும் வேகமாக்குகிறது.

## அமைப்பு

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

## சிக்கலெண்ணம்

| செயல்பாடு | நேரம் |
|---|---|
| insert | O(L) |
| search | O(L) |
| prefix query | O(L) |

க்கிரூசியலாக, செலவு **வார்த்தையின் நீளம் L** மீது சார்ந்தुள்ளது, *சேமிக்கப்பட்ட வார்த்தைகளின் எண்ணிக்கை* மீது அல்ல.

## வர்த்தக-ஆஃப்

- **வலிமை:** வேகமான முன்னொட்டு தேடல்; தானியங்கி-நிறைவு; பகிர்ந்து கொள்ளப்பட்ட முன்னொட்டுகள் ஒத்த வார்த்தைகளுக்கு இடத்தை சேமிக்கிறது.
- **பலவீனம்:** ஒவ்வொரு முனையிலும் அதிக நினைவக மேல்நுட்பம் (ஒவ்வொரு முனைக்கும் குழந்தை வரைபடம்); தொடர்பற்ற விசைகளுக்கு hash set ஐ விட அதிக இடத்தைப் பயன்படுத்தலாம்.

## இது ஏன் முக்கியமானது

Trie கள் தானியங்கி-நிறைவு, எழுத்துப்பிழை-சரிபார்ப்பாளர்கள், IP ரூட்டிங் அட்டவணைகள் மற்றும் அகராதி-அடிப்படையிலான தேடல்களில் சக்தி வாய்ந்தவை, அங்கு **முன்னொட்டு பொருத்தம்** முக்கியமானது.

Hash set முறுமாக "சரியான பொருத்தம்" க்கு பதிலளிக்கும் பொழுது, trie கூடுதலாக "X உடன் எந்த வார்த்தைகள் தொடங்குகின்றன?" என்பதற்கு திறமையுடன் பதிலளிக்கிறது.