TreesMenengahFase D–FE1E5

TRIE

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.

Example use case

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

Syllabus

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

Objectives

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

How It Works

·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

Prerequisites

·Pohon
·String

Real-World Uses

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

Complexity O(panjang kata)