Class TrieNode: Penyisipan dan Pencarian
Bangun TrieNode dengan kamus children dan penanda is_end, implementasikan penyisipan dan pencarian tepat, lalu analisis waktu O(m) per operasi dengan m sebagai panjang kata
Class TrieNode: Penyisipan dan Pencarian adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 1 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa Itu Trie
Trie (pohon prefiks) adalah struktur data berbentuk pohon yang setiap simpulnya merepresentasikan satu karakter. Kata-kata disimpan dengan merangkai karakter dari akar ke daun. Akar merepresentasikan teks kosong. Setiap jalur dari akar ke simpul is_end = True membentuk satu kata tersimpan. Trie ideal untuk kueri berbasis prefiks seperti autocomplete, pemeriksaan ejaan, dan perutean IP, serta lebih unggul daripada peta hash untuk kasus penggunaan ini.
Desain Kelas TrieNode
Sebuah TrieNode memiliki dua bidang: children — kamus yang memetakan karakter ke TrieNodes anak — dan is_end — nilai logika yang menandai apakah simpul ini merupakan akhir kata tersimpan. Penggunaan kamus (alih-alih larik tetap berisi 26 karakter) menggeneralisasi struktur ini ke kumpulan karakter apa pun dan menghemat memori untuk Trie yang jarang. Setiap simpul dalam Trie merepresentasikan tepat satu posisi karakter dalam kata-kata di bawahnya.
class TrieNode:
def __init__(self):
self.children = {} # char -> TrieNode
self.is_end = False # True if a word ends here
class Trie:
def __init__(self):
self.root = TrieNode()
def __repr__(self):
return f'Trie(root with {len(self.root.children)} children)'
t = Trie()
print(t) # Trie(root with 0 children)Operasi insert
Untuk melakukan insert sebuah kata, telusuri dari akar dengan membuat TrieNode baru untuk setiap karakter yang belum ada dalam children simpul saat ini. Setelah semua karakter diproses, tetapkan is_end = True pada simpul terakhir. Melakukan insert pada 'apple' dan 'app' membuat rantai a→p→p→l→e (is_end=True untuk 'apple'), dengan p pada posisi 3 juga ditandai is_end=True untuk 'app'.
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
t = Trie()
t.insert('apple')
t.insert('app')
print('Inserted apple and app')
print('app is_end:', t.root.children['a'].children['p'].children['p'].is_end)Operasi search
Untuk mencari kata secara persis, telusuri Trie dengan mengikuti setiap karakter. Jika ada karakter yang tidak ditemukan dalam children simpul saat ini, kembalikan nilai salah. Jika semua karakter ditemukan, kembalikan node.is_end — nilainya benar hanya jika sebuah kata berakhir tepat di sini (bukan sekadar prefiks). Perbedaan antara 'prefiks ada' dan 'kata persis ada' ini sangat penting dan sering diuji.
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 c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def search(self, word):
node = self.root
for c in word:
if c not in node.children:
return False
node = node.children[c]
return node.is_end # must be a complete word
t = Trie()
t.insert('apple')
print(t.search('apple')) # True
print(t.search('app')) # False (app not inserted)
print(t.search('orange')) # Falsestarts_with (Pencarian Prefiks)
Metode starts_with memeriksa apakah ada kata yang telah disisipkan dengan prefiks yang diberikan. Metode ini mengikuti penelusuran yang sama seperti search, tetapi alih-alih memeriksa is_end, metode ini mengembalikan nilai benar segera setelah semua karakter prefiks berhasil diikuti — artinya, jalur prefiks tersebut ada di dalam 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 c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def search(self, word):
node = self.root
for c in word:
if c not in node.children: return False
node = node.children[c]
return node.is_end
def starts_with(self, prefix):
node = self.root
for c in prefix:
if c not in node.children: return False
node = node.children[c]
return True # prefix path exists
t = Trie()
t.insert('apple')
print(t.starts_with('app')) # True
print(t.starts_with('ape')) # False
print(t.search('app')) # False (not inserted)Kompleksitas Waktu dan Ruang
Setiap operasi Trie (insert, search, starts_with) memerlukan waktu O(m), dengan m sebagai panjang kata — kita menelusuri paling banyak m simpul. Ruang: O(ukuran ALPHABET × N × M), dengan N sebagai jumlah kata dan M sebagai panjang kata rata-rata. Dalam praktiknya, prefiks yang digunakan bersama secara signifikan mengurangi ruang. Kamus children berbasis peta hash menggunakan lebih sedikit ruang daripada larik tetap berisi 26 karakter untuk Trie yang jarang, dengan biaya beban tambahan konstan per pencarian yang sedikit lebih tinggi.
Menggunakan Larik, bukan Kamus
Untuk huruf Inggris kecil saja, gunakan larik berukuran tetap children = [None] * 26 dengan indeks ord(c) - ord('a'). Cara ini lebih cepat (pencarian anak O(1) dibandingkan peta hash) dan memiliki tata letak memori yang dapat diprediksi. Gunakan versi kamus ketika kumpulan karakter berukuran besar atau tidak diketahui (misalnya, Unicode), dan versi larik untuk soal bergaya kompetisi yang hanya menggunakan huruf kecil.
class TrieNodeArray:
def __init__(self):
self.children = [None] * 26
self.is_end = False
class TrieArray:
def __init__(self):
self.root = TrieNodeArray()
def insert(self, word):
node = self.root
for c in word:
idx = ord(c) - ord('a')
if node.children[idx] is None:
node.children[idx] = TrieNodeArray()
node = node.children[idx]
node.is_end = True
def search(self, word):
node = self.root
for c in word:
idx = ord(c) - ord('a')
if node.children[idx] is None: return False
node = node.children[idx]
return node.is_end
t = TrieArray()
t.insert('cat')
print(t.search('cat')) # True
print(t.search('car')) # FalseOperasi Penghapusan
Penghapusan dari Trie harus menangani tiga kasus: (1) kata tidak ada — tidak melakukan apa-apa; (2) kata ada tetapi merupakan prefiks kata lain — hanya hapus tanda pada is_end; (3) kata ada dan bukan prefiks — hapus simpul dari bawah ke atas, berhenti ketika sebuah simpul memiliki anak lain atau merupakan akhir kata lain. Penghapusan jarang diuji dalam wawancara, tetapi baik untuk diketahui secara konseptual.
Menghitung Kata dengan Prefiks
Tambahkan bidang count pada setiap simpul yang nilainya dinaikkan setiap kali simpul tersebut dilewati saat insert. Untuk menghitung kata dengan prefiks tertentu, telusuri hingga simpul akhir prefiks tersebut lalu kembalikan nilainya. Hal ini memungkinkan kueri autocomplete O(m) tanpa menelusuri semua anak — perluasan yang berguna untuk sistem autocomplete di dunia nyata.
class TrieNodeCount:
def __init__(self):
self.children = {}
self.is_end = False
self.count = 0 # words passing through this node
class TrieCount:
def __init__(self):
self.root = TrieNodeCount()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNodeCount()
node = node.children[c]
node.count += 1 # increment on each level
node.is_end = True
def count_with_prefix(self, prefix):
node = self.root
for c in prefix:
if c not in node.children: return 0
node = node.children[c]
return node.count
t = TrieCount()
for w in ['apple','app','application','apply']:
t.insert(w)
print(t.count_with_prefix('app')) # 4
print(t.count_with_prefix('appl')) # 3Perbandingan Trie dan Peta Hash
Peta hash dapat melakukan pencarian persis dalam waktu rata-rata O(m), tetapi tidak dapat menjawab kueri prefiks secara efisien (perlu memindai semua kunci). Trie menjawab kueri prefiks dalam O(p), dengan p sebagai panjang prefiks, secara alami mengelompokkan kata berdasarkan prefiks bersama, dan tidak memerlukan perhitungan hash. Gunakan Trie ketika: kueri prefiks sering dilakukan, autocomplete, pemeriksaan ejaan. Gunakan peta hash ketika: hanya diperlukan pencarian persis.
Penggunaan Trie dalam Sistem Nyata
Penggunaan Trie dalam sistem nyata meliputi: autocomplete (saran pencarian Google), pemeriksa ejaan (menemukan kata yang paling mendekati), perutean IP (pencocokan prefiks terpanjang pada perute), teks prediktif T9 (pembedaan karakter), dan penyelesai DNS (pencarian nama domain hierarkis). Dalam setiap kasus, kompromi waktu O(m) per operasi dan ruang O(ALPHABET × jumlah simpul) pada Trie menjadikannya alat yang tepat untuk pencarian cepat berbasis prefiks dalam skala besar.
Pemeriksaan Cepat
Uji pemahaman Anda terhadap konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini Anda telah mempelajari: TrieNode memiliki kamus children dan nilai logika is_end, insert menelusuri karakter demi karakter, membuat simpul sesuai kebutuhan, dan menetapkan is_end di akhir, serta search memeriksa is_end, sedangkan starts_with hanya memeriksa apakah jalur prefiks ada. Berikutnya kita akan menambahkan autocomplete berbasis prefiks dan membahas metode starts_with secara lebih mendalam.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Class TrieNode: Penyisipan dan Pencarian” gratis?
Ya — teks lengkap “Class TrieNode: Penyisipan dan Pencarian” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Class TrieNode: Penyisipan dan Pencarian”?
Bangun TrieNode dengan kamus children dan penanda is_end, implementasikan penyisipan dan pencarian tepat, lalu analisis waktu O(m) per operasi dengan m sebagai panjang kata Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 1 dari 4.
Berapa lama pelajaran “Class TrieNode: Penyisipan dan Pencarian” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Class TrieNode: Penyisipan dan Pencarian
- Pencarian Awalan dan Starts-With
- Pencarian Wildcard dan Regex dalam Trie
- Pencarian Kata II: Trie + Penelusuran Mundur pada Grid