Belajar Data Structure - Trie (Prefix Tree)

#Pendahuluan

Setelah di episode 13 kita memahami B-Tree dan B+ Tree — tree dengan branching factor tinggi untuk database index — pada episode ini kita mempelajari Trie (prefix tree), tree di mana setiap node merepresentasikan satu karakter dan string yang memiliki prefix sama akan berbagi node yang sama.

Trie bukan hanya konsep teori — ia adalah implementasi di balik autocomplete yang kalian gunakan setiap hari di search engine, chat apps, dan IDE. Ketika kalian mengetik "dev" dan melihat saran "developer", "device", "devvnull" — itulah trie yang bekerja di balik layar.

#Konsep Dasar

#Apa Itu Trie?

Trie adalah tree di mana:

• Setiap node memiliki karakter
• Setiap edge merepresentasikan satu karakter transisi
• Root node kosong (tidak memiliki karakter)
• String disimpan sebagai path dari root ke leaf (atau node yang ditandai sebagai end-of-word)

#Mengapa Shared Prefix?

Ketika banyak string memiliki prefix yang sama (misal: "dev", "developer", "device"), trie menyimpan prefix "dev" hanya sekali. Ini menghemat ruang dibandingkan menyimpan setiap string secara terpisah di hash set.

#Operasi Trie

#Insert

Insert ke Trie

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False
 
class Trie:
    def __init__(self):
        self.root = TrieNode()
 
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

#Search

Search di Trie

def search(self, word):
    node = self.root
    for char in word:
        if char not in node.children:
            return False
        node = node.children[char]
    return node.is_end

#StartsWith (Autocomplete)

StartsWith di Trie

def starts_with(self, prefix):
    node = self.root
    for char in prefix:
        if char not in node.children:
            return False
        node = node.children[char]
    return True
 
def autocomplete(self, prefix):
    node = self.root
    for char in prefix:
        if char not in node.children:
            return []
        node = node.children[char]
 
    results = []
    self._collect_words(node, prefix, results)
    return results
 
def _collect_words(self, node, prefix, results):
    if node.is_end:
        results.append(prefix)
    for char, child in node.children.items():
        self._collect_words(child, prefix + char, results)

#Delete

Delete dari Trie

def delete(self, word):
    def _delete(node, word, depth):
        if depth == len(word):
            if not node.is_end:
                return False
            node.is_end = False
            return len(node.children) == 0
 
        char = word[depth]
        if char not in node.children:
            return False
 
        should_delete = _delete(node.children[char], word, depth + 1)
 
        if should_delete:
            del node.children[char]
            return len(node.children) == 0 and not node.is_end
 
        return False
 
    _delete(self.root, word, 0)

#Trie vs Hash Set

m = panjang string, k = jumlah hasil, n = jumlah string. Trie menang untuk prefix query karena prefix di-share.

#Aplikasi Trie

• Autocomplete: search engine, IDE, chat apps
• Spell checker: cek apakah kata ada di dictionary
• IP routing: longest prefix match di router
• Word game: Scrabble, Boggle

#Praktik: Autocomplete

Autocomplete dengan Trie

trie = Trie()
words = ["developer", "device", "devvnull", "design", "desktop"]
for word in words:
    trie.insert(word)
 
print(trie.autocomplete("dev"))
print(trie.autocomplete("des"))

#Penutup

Inti yang harus dibawa pulang:

• Trie: setiap node = satu karakter, shared prefix = hemat ruang.
• Insert, search, startsWith: semua O(m) di mana m = panjang string.
• Autocomplete: traverse subtree dari node prefix → kumpulkan semua kata.
• Trie unggul untuk prefix query dibandingkan hash set.
• Aplikasi: autocomplete, spell checker, IP routing, word game.

Ini adalah episode terakhir di Fase 3: Trees. Di episode 15 selanjutnya kita memasuki Fase 4: Graphs dengan membahas representasi graph — directed/undirected, weighted/unweighted, adjacency list vs adjacency matrix, serta trade-off memory vs lookup edge. Trees pada dasarnya adalah graph tanpa cycle — jadi pemahaman kalian sudah siap untuk lompatan ke graph!