Apa iku trie (prefix tree) lan kapan iku migunani?

Question

IT Interview Practice · Accepted Answer

A **trie** (prefix tree) iku pohon kang saben **edge** nggambarake aksara lan saben **path saka root** ngorepake prefiks. Tembung-tembung kang ngibagi prefiks padha ngibagi dalan kang padha, nggawe prefix lookups ati-ati banget cepet.

## Structure

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

## Code

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

## Complexity

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

Krucial banget, biaya gantung saka **word length L**, *ora* saka nomer kata-kata kang kaimbuh.

## Trade-offs

- **Strengths:** prefix search cepet; autocomplete; prefiks-prefiks kang padha kasimpen spasi kanggo tembung-tembung kang padha.
- **Weaknesses:** nomer memory overhead saben node nggede banget (peta anak-anakan kanggo saben); bisa nggunakake spasi luwih akeh tinimbang hash set kanggo kunci-kunci kang ora ana hubungane.

## Mengapa iki penting

Tries ngusir autocomplete, spell-checkers, tabel IP routing, lan pencarian berbasis kamus kang **prefix** matching penting.

Bisake hash set mung njawab "exact match," trie menambahi "tembung-tembung apa kang diwiwiti X?" kanthi efisien.

Structure

Code

Complexity

Trade-offs

Mengapa iki penting

Pitakon sing gegandhengan