Melaksanakan Trie dengan Insert, Search, Prefix, dan Delete

Kehendak Soalan dan Konteks Berkaitan

Laksanakan Trie yang menyimpan satu set perkataan dengan empat operasi:

• insert(word) menambah perkataan dan bersifat idempoten apabila perkataan itu sudah wujud.
• search(word) mengembalikan sama ada perkataan lengkap itu disimpan.
• startsWith(prefix) mengembalikan sama ada laluan awalan tersebut wujud; untuk awalan yang tidak kosong, ini bermakna sekurang-kurangnya satu perkataan yang disimpan mempunyainya.
• delete(word) membuang perkataan lengkap tersebut dan mengembalikan sama ada ia wujud sebelumnya.

Anggap insert, search, dan delete menerima perkataan bahasa Inggeris huruf kecil yang tidak kosong. startsWith juga menerima awalan kosong, yang mengembalikan true kerana API ini mentakrifkan laluan punca sebagai awalan kosong walaupun sebelum sebarang pemasukan dibuat. Pelaksanaan adalah dalam memori, berbenang tunggal (single-threaded), dan tidak menyenaraikan cadangan, menyusun kedudukan hasil, mengekalkan data, atau menormalkan Unicode. Pengesahan input berada di luar kelas.

Ini merupakan soalan temu duga pengekodan yang representatif untuk peranan kejuruteraan perisian. Tugas teras adalah untuk memodelkan awalan yang dikongsi dan membezakan antara "laluan ini wujud" daripada "perkataan berakhir di sini." Menambah pemadaman mendedahkan sama ada calon benar-benar memahami model tersebut: memadamkan app mesti mengekalkan apple, manakala memadamkan akhiran unik terakhir boleh menuntut semula nod-nodnya.

Perkara yang Dinilai oleh Penemu Duga

Isyarat pertama ialah penerbitan struktur daripada operasi. Hash set mengendalikan keahlian tepat, tetapi pertanyaan awalan perlu memeriksa perkataan yang disimpan atau mengekalkan indeks lain. Trie menjadikan setiap awalan sebagai laluan dari punca, jadi kos pertanyaan bergantung pada panjang input dan bukannya bilangan perkataan yang disimpan.

Isyarat kedua ialah penanda terminal. Laluan untuk app wujud selepas memasukkan apple, tetapi search("app") kekal palsu sehingga nod tersebut ditandakan sebagai perkataan lengkap. startsWith("app") hanya memerlukan laluan tersebut. Satu pembantu perentasan boleh memenuhi kedua-dua operasi sementara syarat akhir masing-masing kekal berbeza.

Isyarat ketiga ialah keselamatan pemadaman. Mengosongkan penanda terminal sudah mencukupi untuk pemadaman logik. Pemangkasan fizikal adalah pilihan dan hanya boleh diteruskan ke atas selagi anak tersebut bukan terminal dan tidak mempunyai anak. Peraturan ini mengekalkan kedua-dua perkataan yang lebih panjang dan perkataan yang lebih pendek yang berkongsi laluan yang dipadamkan.

Akhir sekali, penemu duga mencari kejujuran dalam kekompleksan dan ujian. Nod bersandarkan peta (map) mengelakkan peruntukan 26 slot anak pada setiap nod yang jarang (sparse), tetapi operasi peta menggunakan andaian prestasi purata masa larian bahasanya. Pemadaman juga mengekalkan timbunan laluan O(L); mendakwa ruang bantuan malar akan bercanggah dengan kod tersebut.

Soalan untuk Dijelaskan Sebelum Menjawab

• Apakah aksara yang dibenarkan? Huruf kecil a-z membenarkan tatasusunan 26 slot. Unicode, campuran huruf besar-kecil, atau abjad yang jarang lebih mengutamakan peta dan mungkin memerlukan kontrak penormalan.
• Adakah pemasukan pendua dikira? Masalah ini menyimpan satu set, jadi pemasukan kali kedua adalah idempoten. Multiset memerlukan pembilang terminal dan awalan.
• Apakah yang patut dilaporkan oleh pemadaman? Ia mengembalikan false untuk perkataan yang tidak wujud dan true hanya apabila perkataan lengkap yang disimpan berjaya dialih keluar.
• Adakah pemadaman mesti menuntut semula nod? Di sini ia melakukan pemangkasan selamat. Jika pemadaman jarang berlaku dan memori tidak terhad, mengosongkan penanda terminal adalah lebih mudah dan masih betul.
• Adakah perkataan kosong sah? Tidak. Awalan kosong dibenarkan, tetapi rentetan kosong tidak boleh dimasukkan atau dicari sebagai perkataan dalam kontrak ini.
• Adakah hasil awalan disenaraikan atau sekadar dikesan? API ini mengembalikan boolean. Menyenaraikan padanan menambah perentasan subpokok dan kos sensitif output.
• Adakah keserentakan diperlukan? Tidak. Pembacaan dan penulisan serentak memerlukan penyegerakan atau reka bentuk snapshot tak boleh ubah (immutable).

Rangka Jawapan 30 Saat

"Saya akan mewakili setiap awalan sebagai laluan daripada satu punca. Setiap nod memetakan aksara seterusnya kepada nod anak dan mempunyai bendera isWord. Insert mencipta nod yang tiada dan menandakan nod akhir. Search menelusuri laluan dan memeriksa bendera tersebut; carian awalan hanya memerlukan laluan itu. Delete mula-mula merekodkan laluan, mengosongkan bendera akhir, kemudian membuang nod ke arah belakang hanya jika nod tersebut tidak mempunyai anak dan bukan penghujung perkataan lain. Setiap operasi dijangka O(L) dengan anak bersandarkan peta, jumlah storan ialah O(C), dan delete menggunakan ruang bantuan O(L)."

Jawapan Mendalam Langkah demi Langkah

Senarai atau set perkataan yang tidak disusun menyebabkan pertanyaan awalan bergantung pada bilangan perkataan. Tatasusunan yang disusun boleh mencari padanan awalan pertama yang mungkin dengan carian perduaan (binary search) dan menarik untuk kamus statik yang kebanyakannya dibaca sahaja, tetapi pemasukan dan pemadaman memerlukan anjakan atau pembinaan semula. Trie menanggung overhed nod per aksara untuk menyokong keempat-empat operasi dalam talian ini secara langsung.

Gunakan invarians ini:

Bagi setiap perkataan yang disimpan, aksaranya membentuk laluan punca-ke-nod, dan isWord adalah benar pada nod tepat apabila laluan yang mengeja nod tersebut merupakan perkataan lengkap yang disimpan.

Invarians ini menerangkan semua operasi. Insert memanjangkan satu laluan dan menghidupkan penanda akhirnya. Search memerlukan kedua-dua laluan dan penanda tersebut. Carian awalan hanya memerlukan laluan tersebut. Delete mematikan tepat satu penanda dan mengalih keluar akhiran hanya apabila tiada perkataan yang tinggal boleh 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
  }
}

Pemadaman paling mudah disahkan dengan dua contoh kontra. Jika app dan apple disimpan, memadamkan app mengosongkan penanda pada p kedua tetapi menghentikan pemangkasan kerana nod tersebut mempunyai anak l. apple kekal boleh dicari. Jika app dan apt disimpan, memadamkan app hanya mengalih keluar p akhir; pemangkasan kemudiannya berhenti pada nod ap yang dikongsi kerana ia masih mempunyai anak t.

Kebenaran dibuktikan melalui aruhan. Trie kosong memenuhi invarians. Insert hanya mengubah satu laluan dan penanda akhirnya. Search dan carian awalan tidak mengubah keadaan. Delete yang berjaya mula-mula mengalih keluar tepat penanda sasaran. Setiap nod yang dipangkas adalah bukan terminal dan tidak mempunyai anak, jadi ia tidak boleh mewakili perkataan yang disimpan atau membawa kepada satu perkataan. Mengalih keluarnya mengekalkan setiap laluan tersimpan yang tinggal; berhenti pada nod terminal atau nod pencabangan pertama mengekalkan awalan yang dikongsi.

Katakan L ialah panjang input dan C ialah bilangan nod aksara yang diperuntukkan pada masa ini. Di bawah carian peta purata, insert, search, dan carian awalan mengambil masa jangkaan O(L). Delete merentas ke hadapan dan memangkas paling banyak L tepi yang sama, jadi ia juga jangkaan O(L). Trie menggunakan ruang O(C), dihadkan oleh jumlah aksara awalan tersimpan yang berbeza; laluan delete menggunakan ruang bantuan O(L).

Untuk abjad huruf kecil yang tetap, TrieNode | undefined[26] memberikan capaian terindeks terus dan kerja per aksara yang boleh diramal, tetapi memperuntukkan 26 rujukan bagi setiap nod. Peta hanya menyimpan tepi yang wujud dan mengendalikan abjad yang lebih luas, dengan overhed pencincangan dan objek. Jawapan harus memilih berdasarkan abjad dan ketumpatan, bukan mendakwa satu perwakilan sentiasa menang.

Pengesahan harus memeriksa peralihan keadaan, bukan hanya satu carian. Mulakan dengan startsWith("") === true, search("") === false, dan pemadaman daripada Trie kosong. Masukkan app, apple, dan apt; masukkan semula app; bezakan search("ap") daripada startsWith("ap"); padamkan app sambil mengekalkan apple; tolak pemadaman kali kedua; kemudian padamkan perkataan yang tinggal dan sahkan awalan mereka hilang. Ujian rawak boleh membandingkan semua operasi dengan rujukan Set<string> yang mudah dan mengimbas set tersebut untuk pertanyaan awalan.

Jika keperluannya hanyalah keahlian tepat, hash set adalah lebih pendek dan biasanya lebih digemari. Jika kamus adalah statik dan disusun, carian perduaan boleh menjawab kewujudan awalan tanpa storan nod yang banyak. Jika rantaian anak tunggal yang panjang mendominasi memori, radix tree memampatkan rantaian tersebut dengan kos logik pemisahan dan penggabungan yang lebih kompleks.

Contoh Jawapan Berkualiti Tinggi

"Saya akan mengesahkan abjad, semantik pendua, dan sama ada pemadaman mesti menuntut semula memori terlebih dahulu. Saya akan menganggap perkataan huruf kecil yang tidak kosong, semantik set, awalan kosong yang sepadan, dan pemangkasan selamat semasa delete.

Setiap nod Trie menyimpan tepi aksara keluar dan bendera terminal. Laluan punca-ke-nod ialah awalan; bendera menyatakan sama ada laluan yang sama itu juga merupakan perkataan tersimpan yang lengkap. Insert mencipta anak yang tiada dan hanya menandakan nod akhir. Search menyemak bendera akhir, manakala startsWith hanya menyemak sama ada perentasan berjaya.

Untuk delete, saya merekodkan setiap induk, tepi, dan anak semasa menelusuri perkataan. Jika laluan tiada atau nod akhir bukan terminal, saya mengembalikan false tanpa mengubah keadaan. Jika sebaliknya, saya mengosongkan penanda dan menelusuri ke belakang. Saya mengalih keluar tepi hanya apabila anaknya tidak mempunyai anak dan bukan terminal, berhenti pada nod pertama yang masih diperlukan oleh perkataan lain. Itulah yang memastikan apple kekal utuh apabila memadamkan app.

Dengan anak bersandarkan peta, semua operasi adalah jangkaan O(L). Jumlah storan ialah O(C) nod aksara, dan delete menggunakan timbunan laluan O(L). Saya akan menguji kes kosong dan kes tiada, pemasukan pendua, perkataan yang merupakan awalan kepada perkataan lain, dua perkataan yang bercabang, dan pemangkasan penuh selepas perkataan terakhir dialih keluar. Jika carian tepat adalah satu-satunya operasi, saya akan menggunakan hash set sebaliknya."

Kesilapan Lazim

• Menganggap setiap laluan yang boleh dicapai sebagai perkataan → search("app") menjadi true selepas hanya memasukkan apple → wajibkan isWord untuk carian tepat.
• Membuat startsWith menyemak isWord → awalan yang sah ditolak melainkan dimasukkan secara berasingan → kembalikan kejayaan apabila laluan tersebut wujud.
• Mengosongkan atau mengalih keluar keseluruhan laluan semasa pemadaman → memadamkan app memusnahkan apple → kosongkan penanda terminal dahulu dan pangkas daun bukan terminal sahaja.
• Memangkas melepasi nod pencabangan → perkataan yang tidak berkaitan seperti apt hilang → berhenti apabila anak masih mempunyai anak.
• Memangkas melepasi nod terminal lain → memadamkan perkataan yang lebih panjang membuang perkataan awalan yang lebih pendek → berhenti apabila anak adalah terminal.
• Mengembalikan true apabila hanya laluan pemadaman yang wujud → memadamkan app selepas hanya memasukkan apple mengubah keadaan atau tersilap melaporkan keadaan → wajibkan nod akhir menjadi terminal.
• Mengira pemasukan pendua secara tidak sengaja → semantik set bertukar menjadi multiset tersembunyi → gunakan satu penanda boolean atau ubah kontrak secara eksplisit kepada pembilang.
• Mendakwa keempat-empat operasi menggunakan masa malar → kerja bertambah mengikut panjang input → nyatakan jangkaan O(L) dan andaian peta.
• Mendakwa pemadaman tidak menggunakan ruang tambahan → pelaksanaan menyimpan laluan untuk pemangkasan ke belakang → laporkan ruang bantuan O(L) atau gunakan alternatif rekursif yang wajar dengan had timbunan yang sama.
• Sentiasa memperuntukkan 26 anak → data yang jarang atau Unicode membazirkan ruang atau melanggar kontrak abjad → pilih tatasusunan berbanding peta selepas menjelaskan set aksara.
• Menggunakan Trie untuk carian tepat sahaja → overhed nod menanggung kos untuk ciri awalan yang tidak pernah digunakan oleh produk → utamakan hash set untuk keahlian tepat sahaja.

Soalan Susulan dan Maklum Balas

Soalan Susulan 1: Bagaimanakah perkataan pendua dan semantik padam-satu (erase-one) mengubah reka bentuk?

Gantikan isWord dengan wordCount, dan simpan prefixCount pada nod jika kiraan awalan ditanya. Insert menambah kiraan di sepanjang laluan. Erase mula-mula mengesahkan wordCount > 0, mengurangkan laluan yang sama, dan memangkas hanya apabila kiraan berkaitan mencapai sifar. Pelaksanaan boolean tidak dapat membezakan satu pemasukan daripada lima pemasukan.

Soalan Susulan 2: Bagaimanakah anda akan mengembalikan hasil autolengkap (autocomplete) K teratas?

Mencari nod awalan masih menelan kos O(L), tetapi menyenaraikan subpokoknya adalah sensitif terhadap output dan subpokok. Untuk volum pertanyaan yang rendah, rentas dan susun kedudukan mengikut permintaan (on demand). Untuk volum pertanyaan yang tinggi, simpan cache senarai calon berkedudukan terhad pada setiap nod dan kemas kininya semasa penulisan, menukar memori tambahan dan amplifikasi penulisan demi kependaman bacaan yang lebih rendah. Skor kedudukan dan peraturan pemutus seri (tie-breaking) mestilah eksplisit.

Soalan Susulan 3: Bagaimanakah padanan Unicode dan tidak peka huruf besar-kecil (case-insensitive) berfungsi?

Takrifkan penormalan sebelum memilih perwakilan. Contohnya, normalkan kepada satu bentuk Unicode dan gunakan dasar huruf peka setempat (locale-aware) pada kedua-dua masa insert dan query. Ulang lelar mengikut unit yang dipersetujui—titik kod (code points) atau kluster grafem—dan gunakan tepi bersandarkan peta. Menormalkan pertanyaan sahaja atau pemasukan sahaja akan mencipta laluan yang tidak akan sepadan.

Soalan Susulan 4: Bagaimanakah anda membuat Trie selamat untuk bebenang (thread-safe)?

Satu kunci baca-tulis (read-write lock) di sekeliling keseluruhan Trie ialah jawapan betul yang paling mudah: insert dan delete mengambil kunci tulis, manakala search dan prefix search mengambil kunci baca. Kunci nod yang lebih halus memerlukan susunan pemerolehan yang tetap dan perlindungan rapi semasa pemangkasan. Snapshot tak boleh ubah atau punca salin-semasa-tulis (copy-on-write) memudahkan pembaca apabila kemas kini jarang berlaku.

Soalan Susulan 5: Bagaimana jika memori ialah sumber yang terhad?

Ukur ketumpatan nod dahulu. Tatasusunan tetap boleh mendominasi memori dalam data yang jarang, manakala peta membawa overhed objek dan pencincangan tersendiri. Radix tree memampatkan rantaian anak tunggal; ternary search tree mengurangkan storan anak; struktur keadaan terhingga (finite-state) yang minimum boleh memampatkan kamus statik dengan lebih lanjut. Pilihan-pilihan ini mengubah kekompleksan kemas kini dan risiko pelaksanaan.

Soalan Susulan 6: Bagaimanakah pemadanan kad bebas (wildcard) atau awalan terpanjang (longest-prefix) mengubah perentasan?

Pemadaman awalan terpanjang menelusuri pertanyaan sambil mengingati nod terminal terdalam, kekal linear mengikut panjang pertanyaan. Kad bebas seperti . bercabang ke setiap anak pada kedudukan tersebut, jadi kerja kes terburuk boleh berkembang bersama-sama subpokok yang diterokai. API mesti menyatakan sintaks kad bebas dan sama ada ia mengembalikan kewujudan, satu hasil, atau semua hasil.