Τι είναι ένα 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;".