Çfarë është një trie (pemë parashtesë) dhe kur është e dobishme?

Question

Accepted Answer

Një **trie** (pemë parashtese) është një pemë ku çdo **gjenë** përfaqëson një karakter dhe çdo **rrugë nga rrënja** përbën një parashte. Fjalët që ndajnë një parashte ndajnë të njëjtën rrugë, duke bërë kërkimin në parashte jashtëzakonisht të shpejtë.

## Struktura

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

## Kodi

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

## Kompleksiteti

| Operacioni | Koha |
|---|---|
| insert | O(L) |
| search | O(L) |
| prefix query | O(L) |

Më së rëndësishmi, kostoja varet nga **gjatësia e fjalës L**, *jo* nga numri i fjalëve të ruajtura.

## Kompromise

- **Pikat e forta:** kërkimi i shpejtë në parashte; plotësim automatik; parashtesat e përbashkëta kursejnë hapësirë për fjalë të ngjashme.
- **Pikat e dobëta:** fasadë e lartë memorie për nyje (hartë fëmijësh për secilën nyje); mund të përdorë më shumë hapësirë se një hash set për çelësa të palidhur.

## Pse është e rëndësishme

Tries-et fuqizojnë plotësimin automatik, kontrolluesit e drejtshkrimit, tabelat e rrugëzimit IP, dhe kërkimin e bazuar në fjalor ku **përputhja e parashtes** ka rëndësi.

Ndërsa një hash set i përgjigjet vetëm "përputhjes të saktë", një trie përgjigjet në mënyrë të efektshme edhe në "cilat fjalë fillojnë me X?".