Apa Itu Trie?

Trie (dilafalkan "try", singkatan dari retrieval) adalah struktur data berbentuk pohon yang dibuat untuk menyimpan dan mencari string berdasarkan karakternya. Setiap edge pada pohon diberi label satu karakter, dan setiap jalur dari root ke node yang ditandai mengeja satu kata yang disimpan.

Struktur ini membuat pencarian awalan sangat cepat. Memeriksa apakah trie berisi kata yang diawali "car" hanya memerlukan tiga pencarian karakter dari root, berapa pun banyaknya ribuan kata yang disimpan. Trie menjadi mesin di balik fitur seperti pelengkapan otomatis, pemeriksaan ejaan, dan tabel perutean IP.

Setiap node dalam trie menyimpan dua bagian status:

• children: peta dari karakter ke TrieNode berikutnya.
• isEndOfWord: penanda yang bernilai true saat jalur dari root ke node ini mengeja kata lengkap yang telah dimasukkan.

Lima operasi utama pada trie adalah:

1. Insert: Tambahkan kata, dengan membuat node yang belum ada di sepanjang jalurnya.
2. Search: Periksa apakah sebuah kata lengkap disimpan.
3. StartsWith: Periksa apakah ada kata tersimpan yang memiliki awalan tertentu.
4. Delete: Hapus kata dan rapikan cabang yang tidak lagi digunakan.
5. WordCount: Hitung banyaknya kata berbeda yang disimpan.

Mari kita buat class Trie!