Mengimplementasikan Trie dengan Insert, Search, Prefix, dan Delete

Konteks Soal dan Penerapannya

Implementasikan Trie yang menyimpan sekumpulan kata dengan empat operasi:

• insert(word) menambahkan kata dan bersifat idempoten jika kata tersebut sudah ada.
• search(word) mengembalikan apakah kata lengkap tersebut tersimpan.
• startsWith(prefix) mengembalikan apakah jalur prefiks tersebut ada; untuk prefiks tidak kosong, ini berarti setidaknya ada satu kata tersimpan yang memilikinya.
• delete(word) menghapus kata lengkap tersebut dan mengembalikan apakah kata itu sebelumnya ada.

Asumsikan insert, search, dan delete menerima kata bahasa Inggris berhuruf kecil yang tidak kosong. startsWith juga menerima prefiks kosong, yang mengembalikan true karena API ini mendefinisikan jalur root sebagai prefiks kosong bahkan sebelum ada penyisipan apa pun. Implementasi dilakukan di dalam memori, berutas tunggal (single-threaded), dan tidak melakukan enumerasi saran, pemeringkatan hasil, persistensi data, atau normalisasi Unicode. Validasi input berada di luar kelas.

Ini adalah masalah wawancara pengodean yang representatif untuk posisi rekayasa perangkat lunak. Tugas utamanya adalah memodelkan prefiks bersama dan membedakan antara "jalur ini ada" dengan "sebuah kata berakhir di sini." Menambahkan operasi penghapusan akan memperlihatkan apakah kandidat benar-benar memahami model tersebut: menghapus app harus tetap mempertahankan apple, sementara menghapus sufiks unik terakhir dapat mereklamasi simpul-simpulnya.

Apa yang Dinilai oleh Pewawancara

Sinyal pertama adalah menurunkan struktur data dari kebutuhan operasi. Hash set dapat menangani keanggotaan eksak, tetapi kueri prefiks perlu memeriksa kata-kata yang tersimpan atau memelihara indeks lain. Trie menjadikan setiap prefiks sebagai jalur dari root, sehingga biaya kueri bergantung pada panjang input, bukan pada jumlah kata yang tersimpan.

Sinyal kedua adalah penanda terminal. Jalur untuk app sudah ada setelah menyisipkan apple, tetapi search("app") tetap bernilai false hingga simpul tersebut ditandai sebagai kata lengkap. startsWith("app") hanya membutuhkan keberadaan jalur. Satu fungsi pembantu penelusuran dapat melayani kedua operasi sementara kondisi akhirnya tetap berbeda.

Sinyal ketiga adalah keamanan penghapusan. Menghapus penanda terminal sudah cukup untuk penghapusan logis. Pemangkasan fisik bersifat opsional dan hanya boleh berjalan ke atas selama simpul anak tersebut non-terminal dan tidak memiliki anak. Aturan ini menjaga kata yang lebih panjang maupun kata yang lebih pendek yang berbagi jalur yang dihapus.

Terakhir, pewawancara mencari kejujuran dalam analisis kompleksitas dan pengujian. Simpul berbasis map menghindari alokasi 26 slot anak pada setiap simpul yang jarang (sparse), tetapi operasi map menggunakan asumsi performa rata-rata runtime bahasanya. Penghapusan juga mempertahankan tumpukan jalur O(L); mengklaim ruang bantu konstan akan bertentangan dengan kodenya.

Pertanyaan Klarifikasi Sebelum Menjawab

• Karakter apa saja yang diperbolehkan? Huruf kecil a-z memungkinkan array 26 slot. Unicode, huruf besar-kecil campuran, atau alfabet yang renggang lebih cocok menggunakan map dan mungkin memerlukan kontrak normalisasi.
• Apakah penyisipan duplikat dihitung? Masalah ini menyimpan himpunan (set), jadi penyisipan kedua bersifat idempoten. Sebuah multiset akan membutuhkan penghitung terminal dan prefiks.
• Apa yang harus dikembalikan oleh operasi penghapusan? Operasi ini mengembalikan false untuk kata yang tidak ditemukan dan true hanya ketika kata lengkap yang tersimpan berhasil dihapus.
• Haruskah penghapusan mereklamasi simpul? Di sini dilakukan pemangkasan yang aman. Jika penghapusan jarang terjadi dan memori tidak terbatas, membersihkan penanda terminal lebih sederhana dan tetap benar.
• Apakah string kosong valid sebagai kata? Tidak. Prefiks kosong diperbolehkan, tetapi string kosong tidak dapat disisipkan atau dicari sebagai kata dalam kontrak ini.
• Apakah hasil prefiks dihitung/didaftar atau hanya dideteksi? API ini mengembalikan nilai boolean. Menampilkan daftar kecocokan menambahkan penelusuran subtree dan biaya yang sensitif terhadap output.
• Apakah konkurensi diperlukan? Tidak. Pembacaan dan penulisan konkuren akan memerlukan sinkronisasi atau desain snapshot yang immutable.

Kerangka Jawaban 30 Detik

"Saya akan merepresentasikan setiap prefiks sebagai jalur dari satu root. Setiap simpul memetakan karakter berikutnya ke simpul anak dan memiliki flag isWord. Insert membuat simpul yang belum ada dan menandai simpul terakhir. Search menelusuri jalur dan memeriksa flag tersebut; pencarian prefiks hanya membutuhkan jalurnya. Delete pertama-tama mencatat jalur, membersihkan flag akhir, lalu menghapus simpul ke arah belakang hanya jika simpul tersebut tidak memiliki anak dan bukan merupakan akhir dari kata lain. Setiap operasi diperkirakan O(L) dengan anak berbasis map, total penyimpanan adalah O(C), dan delete menggunakan ruang bantu O(L)."

Jawaban Mendalam Langkah demi Langkah

Sebuah list atau himpunan kata yang tidak terurut membuat kueri prefiks bergantung pada jumlah kata. Array terurut dapat menemukan kecocokan prefiks pertama yang memungkinkan dengan binary search dan menarik untuk kamus statis yang sebagian besar hanya dibaca, tetapi penyisipan dan penghapusan memerlukan pergeseran elemen atau pembangunan ulang. Trie membayar overhead simpul per karakter untuk mendukung keempat operasi daring ini secara langsung.

Gunakan invarian ini:

Untuk setiap kata yang tersimpan, karakter-karakternya membentuk jalur dari root ke simpul, dan isWord bernilai true pada sebuah simpul tepat ketika jalur yang mengeja simpul tersebut adalah kata lengkap yang tersimpan.

Invarian ini menjelaskan semua operasi. Insert memperpanjang satu jalur dan menyalakan penanda akhirnya. Search membutuhkan jalur sekaligus penandanya. Pencarian prefiks hanya membutuhkan jalurnya. Delete mematikan tepat satu penanda dan menghapus sufiks hanya jika tidak ada kata lain yang tersisa yang dapat menggunakannya.

class TrieNode {
  readonly children = new Map<string, TrieNode>()
  isWord = false
}

class Trie {
  private readonly root = new TrieNode()

  insert(word: string): void {
    let node = this.root

    for (const character of word) {
      let child = node.children.get(character)
      if (!child) {
        child = new TrieNode()
        node.children.set(character, child)
      }
      node = child
    }

    node.isWord = true
  }

  search(word: string): boolean {
    return this.walk(word)?.isWord ?? false
  }

  startsWith(prefix: string): boolean {
    return this.walk(prefix) !== undefined
  }

  delete(word: string): boolean {
    let node = this.root
    const path: Array<[TrieNode, string, TrieNode]> = []

    for (const character of word) {
      const child = node.children.get(character)
      if (!child) return false

      path.push([node, character, child])
      node = child
    }

    if (!node.isWord) return false
    node.isWord = false

    for (let index = path.length - 1; index >= 0; index -= 1) {
      const [parent, character, child] = path[index]
      if (child.isWord || child.children.size > 0) break
      parent.children.delete(character)
    }

    return true
  }

  private walk(text: string): TrieNode | undefined {
    let node = this.root

    for (const character of text) {
      const child = node.children.get(character)
      if (!child) return undefined
      node = child
    }

    return node
  }
}

Penghapusan paling mudah diverifikasi dengan dua contoh berlawanan. Jika app dan apple tersimpan, menghapus app akan membersihkan penanda pada p kedua tetapi menghentikan pemangkasan karena simpul tersebut memiliki anak l. apple tetap dapat dicari. Jika app dan apt tersimpan, menghapus app hanya menghapus p terakhir; pemangkasan kemudian berhenti pada simpul bersama ap karena masih memiliki anak t.

Kebenaran dapat dibuktikan melalui induksi. Trie yang kosong memenuhi invarian. Insert hanya mengubah satu jalur dan penanda akhirnya. Search dan pencarian prefiks tidak mengubah state. Delete yang berhasil pertama-tama menghapus tepat penanda target. Setiap simpul yang dipangkas adalah non-terminal dan tidak beranak, sehingga tidak dapat mewakili kata yang tersimpan atau mengarah ke kata lain. Menghapusnya akan mempertahankan setiap jalur tersimpan yang tersisa; berhenti pada simpul terminal atau simpul percabangan pertama akan mempertahankan prefiks bersama.

Misalkan L adalah panjang input dan C adalah jumlah simpul karakter yang saat ini dialokasikan. Di bawah pencarian map rata-rata, insert, search, dan pencarian prefiks membutuhkan waktu yang diperkirakan O(L). Delete menelusuri ke depan dan memangkas paling banyak L edge yang sama, sehingga juga diperkirakan O(L). Trie menggunakan ruang O(C), yang dibatasi oleh jumlah karakter prefiks tersimpan yang berbeda; jalur delete menggunakan ruang bantu O(L).

Untuk alfabet huruf kecil tetap, TrieNode | undefined[26] memberikan akses terindeks langsung dan beban kerja per karakter yang dapat diprediksi, tetapi mencadangkan 26 referensi per simpul. Sebuah map hanya menyimpan edge yang ada dan menangani alfabet yang lebih luas, dengan overhead hashing dan objek. Jawaban harus memilih berdasarkan alfabet dan kepadatannya, bukan mengklaim satu representasi selalu lebih unggul.

Validasi harus memeriksa transisi state, bukan hanya satu pencarian. Mulailah dengan startsWith("") === true, search("") === false, dan penghapusan dari Trie kosong. Sisipkan app, apple, dan apt; sisipkan ulang app; bedakan search("ap") dari startsWith("ap"); hapus app sambil mempertahankan apple; tolak penghapusan kedua; lalu hapus kata-kata yang tersisa dan pastikan prefiksnya menghilang. Pengujian acak dapat membandingkan semua operasi dengan referensi sederhana Set<string> dan memindai set tersebut untuk kueri prefiks.

Jika persyaratannya hanya keanggotaan eksak, hash set lebih ringkas dan biasanya lebih disukai. Jika kamus bersifat statis dan terurut, binary search dapat menjawab keberadaan suatu prefiks tanpa penyimpanan simpul yang besar. Jika rantai anak tunggal yang panjang mendominasi memori, radix tree dapat memadatkan rantai tersebut dengan konsekuensi logika pemisahan dan penggabungan yang lebih rumit.

Contoh Jawaban Berkualitas Tinggi

"Pertama-tama saya akan mengonfirmasi alfabet, semantik duplikat, dan apakah penghapusan harus mereklamasi memori. Saya akan mengasumsikan kata-kata huruf kecil tidak kosong, semantik himpunan (set), prefiks kosong yang cocok, dan pemangkasan aman saat delete.

Setiap simpul Trie menyimpan edge karakter keluar dan flag terminal. Jalur dari root ke simpul adalah prefiks; flag tersebut menyatakan apakah jalur yang sama juga merupakan kata tersimpan yang lengkap. Insert membuat anak yang belum ada dan hanya menandai simpul terakhir. Search memeriksa flag akhir, sedangkan startsWith hanya memeriksa apakah penelusuran berhasil.

Untuk delete, saya mencatat setiap induk, edge, dan anak saat menelusuri kata. Jika jalurnya tidak ada atau simpul akhirnya bukan terminal, saya mengembalikan false tanpa mengubah state. Jika ada, saya membersihkan penanda dan menelusuri mundur. Saya menghapus edge hanya jika anaknya tidak memiliki anak dan bukan terminal, berhenti pada simpul pertama yang masih dibutuhkan oleh kata lain. Itulah yang menjaga apple tetap utuh saat menghapus app.

Dengan anak berbasis map, semua operasi diperkirakan O(L). Total penyimpanan adalah O(C) simpul karakter, dan delete menggunakan tumpukan jalur O(L). Saya akan menguji kasus kosong dan tidak ditemukan, penyisipan duplikat, kata yang merupakan prefiks kata lain, dua kata yang bercabang, dan pemangkasan penuh setelah kata terakhir dihapus. Jika pencarian eksak adalah satu-satunya operasi, saya akan menggunakan hash set sebagai gantinya."

Kesalahan Umum

• Menganggap setiap jalur yang dapat dijangkau sebagai kata → search("app") menjadi true setelah hanya menyisipkan apple → wajibkan isWord untuk pencarian eksak.
• Membuat startsWith memeriksa isWord → prefiks yang valid ditolak kecuali disisipkan secara terpisah → kembalikan sukses saat jalurnya ada.
• Membersihkan atau menghapus seluruh jalur saat penghapusan → menghapus app akan merusak apple → bersihkan penanda terminal terlebih dahulu dan pangkas hanya daun non-terminal.
• Memangkas melewati simpul percabangan → kata yang tidak terkait seperti apt menghilang → berhenti ketika anak masih memiliki anak.
• Memangkas melewati simpul terminal lain → menghapus kata yang lebih panjang akan menghapus kata prefiksnya yang lebih pendek → berhenti ketika anak adalah simpul terminal.
• Mengembalikan true padahal hanya jalur penghapusan yang ada → menghapus app setelah hanya menyisipkan apple akan memutasi atau salah melaporkan state → wajibkan simpul akhir berstatus terminal.
• Menghitung penyisipan duplikat secara tidak sengaja → semantik set berubah menjadi multiset tersembunyi → gunakan satu penanda boolean atau ubah kontrak secara eksplisit ke penghitung.
• Mengklaim keempat operasi menggunakan waktu konstan → beban kerja bertambah seiring panjang input → nyatakan nilai perkiraan O(L) dan asumsi map.
• Mengklaim penghapusan tidak menggunakan ruang ekstra → implementasi menyimpan jalur untuk pemangkasan mundur → laporkan ruang bantu O(L) atau gunakan alternatif rekursif yang dapat dijustifikasi dengan batas tumpukan yang sama.
• Selalu mengalokasikan 26 anak → data yang renggang atau Unicode membuang-buang ruang atau merusak kontrak alfabet → pilih array versus map setelah memperjelas kumpulan karakter.
• Menggunakan Trie hanya untuk pencarian eksak → overhead simpul membayar fitur prefiks yang tidak pernah digunakan produk → lebih baik gunakan hash set untuk keanggotaan eksak saja.

Pertanyaan Lanjutan dan Tanggapannya

Pertanyaan Lanjutan 1: Bagaimana kata duplikat dan semantik hapus-satu (erase-one) mengubah desain?

Ganti isWord dengan wordCount, dan simpan prefixCount pada simpul jika jumlah prefiks ingin dikueri. Insert menambah hitungan di sepanjang jalur. Erase pertama-tama mengonfirmasi wordCount > 0, mengurangi hitungan pada jalur yang sama, dan memangkas hanya ketika hitungan yang relevan mencapai nol. Implementasi boolean tidak dapat membedakan satu penyisipan dari lima penyisipan.

Pertanyaan Lanjutan 2: Bagaimana Anda akan mengembalikan hasil pelengkapan otomatis (autocomplete) K teratas?

Menemukan simpul prefiks tetap memerlukan biaya O(L), tetapi menghitung/mengenumerasi subtreenya sensitif terhadap output dan ukuran subtree. Untuk volume kueri yang rendah, telusuri dan lakukan pemeringkatan sesuai permintaan (on demand). Untuk volume kueri yang tinggi, lakukan caching daftar kandidat berperingkat terbatas di setiap simpul dan perbarui saat ada penulisan, menukar memori ekstra dan amplifikasi penulisan demi latensi baca yang lebih rendah. Skor pemeringkatan dan aturan pemutus seri (tie-breaking) harus dibuat eksplisit.

Pertanyaan Lanjutan 3: Bagaimana pencocokan Unicode dan case-insensitive bekerja?

Definisikan normalisasi sebelum memilih representasi. Misalnya, lakukan normalisasi ke satu bentuk Unicode dan terapkan aturan huruf besar/kecil yang peka lokal (locale-aware) baik pada saat insert maupun query. Lakukan iterasi berdasarkan unit yang disepakati—code point atau grapheme cluster—dan gunakan edge berbasis map. Melakukan normalisasi hanya pada kueri atau hanya pada penyisipan akan menciptakan jalur yang tidak akan pernah cocok.

Pertanyaan Lanjutan 4: Bagaimana Anda membuat Trie thread-safe?

Satu read-write lock di sekeliling seluruh Trie adalah jawaban benar yang paling sederhana: insert dan delete mengambil write lock, sedangkan search dan startsWith mengambil read lock. Kunci simpul yang lebih halus memerlukan urutan perolehan yang tetap dan perlindungan pemangkasan yang hati-hati. Immutable snapshot atau root copy-on-write menyederhanakan pembaca saat pembaruan jarang terjadi.

Pertanyaan Lanjutan 5: Bagaimana jika memori adalah sumber daya yang terbatas?

Ukur kepadatan simpul terlebih dahulu. Array tetap dapat mendominasi memori pada data yang renggang, sementara map membawa overhead objek dan hashing tersendiri. Radix tree memadatkan rantai anak tunggal; ternary search tree mengurangi penyimpanan anak; struktur finite-state minimal dapat memadatkan kamus statis lebih jauh lagi. Pilihan-pilihan ini mengubah kompleksitas pembaruan dan risiko implementasi.

Pertanyaan Lanjutan 6: Bagaimana pencocokan wildcard atau longest-prefix mengubah penelusuran?

Pencocokan longest-prefix menelusuri kueri sambil mengingat simpul terminal terdalam, tetap linear terhadap panjang kueri. Wildcard seperti . bercabang ke setiap anak pada posisi tersebut, sehingga beban kerja terburuk dapat meluas seiring dengan subtree yang dieksplorasi. API harus menyatakan sintaks wildcard dan apakah ia mengembalikan status keberadaan, satu hasil, atau semua hasil.