PohonMenengahFase D–FE1E5

Trie (Pohon Prefix)

Trie menyimpan kata huruf-per-huruf sebagai pohon prefix; kata dengan awalan sama berbagi jalur node yang sama. Menelusuri sebuah prefix langsung memberi semua kata yang berawalan itu. Dasar autocomplete dan kamus digital.

Contoh kasus

Saran autocomplete: mengetik AP langsung memunculkan API dan APEL yang berbagi awalan sama.

Silabus

Pohon prefix yang menyimpan kata huruf per huruf, sehingga kata berawalan sama berbagi jalur dan prefix bisa dicari instan.

Tujuan Belajar

·Memahami penyimpanan kata sebagai jalur huruf pada pohon
·Menjelaskan bagaimana awalan sama berbagi node yang sama
·Menerapkan penelusuran prefix untuk fitur autocomplete

Cara Kerja

·Mulai dari node akar kosong
·Tiap huruf kata menjadi satu langkah turun ke node anak
·Kata dengan awalan sama memakai jalur node yang sama
·Tandai node terakhir sebagai akhir sebuah kata
·Telusuri sebuah prefix untuk mendapat semua kata di bawahnya

Prasyarat

·Pohon
·String

Contoh Nyata

·Saran autocomplete: ketik 'AP' langsung muncul 'API' dan 'APEL'
·Prediksi kata di keyboard HP saat mengetik pesan

Kompleksitas O(panjang kata)