Data Structures #3: Trie – Panduan Lengkap dengan Contoh
Dalam dunia ilmu komputer, struktur data adalah fondasi dari pengembangan perangkat lunak yang efisien. Salah satu struktur data yang sering terlupakan namun sangat kuat adalah Trie (diucapkan “try”), juga dikenal sebagai prefix tree. Dalam posting blog ini, kita akan menyelami Trie secara mendalam, menjelajahi apa itu, bagaimana cara kerjanya, implementasinya, kompleksitasnya, dan kasus penggunaan praktisnya. Bersiaplah untuk membuka potensi Trie dan meningkatkan keterampilan pemrograman Anda!
Daftar Isi
- Pengantar Trie
- Apa itu Trie? Definisi dan Tujuan
- Mengapa Menggunakan Trie? Manfaat Utama
- Trie vs. Struktur Data Lainnya: Kapan Harus Menggunakan Trie?
- Anatomi Trie: Membongkar Struktur
- Nodes dan Edges: Komponen Dasar
- Root Node: Awal dari Segalanya
- Children Nodes: Ekspansi Trie
- End-of-Word Markers: Menandai Penyelesaian Kata
- Operasi Dasar Trie: Membangun dan Berinteraksi dengan Trie
- Penyisipan (Insertion): Menambahkan Kata ke Trie
- Pencarian (Search): Memeriksa Keberadaan Kata
- Penghapusan (Deletion): Menghapus Kata dari Trie
- Implementasi Trie: Langkah demi Langkah dengan Contoh Kode
- Representasi Node: Cara Memodelkan Node Trie
- Fungsi Penyisipan (Insertion): Implementasi Mendalam
- Fungsi Pencarian (Search): Implementasi Mendalam
- Fungsi Penghapusan (Deletion): Implementasi Mendalam
- Contoh Kode Lengkap (Python, Java, C++)
- Kompleksitas Waktu dan Ruang Trie: Menganalisis Kinerja
- Kompleksitas Waktu: Penyisipan, Pencarian, dan Penghapusan
- Kompleksitas Ruang: Efisiensi Penggunaan Memori
- Trade-off: Memahami Batasan
- Kasus Penggunaan Trie: Aplikasi Dunia Nyata
- Otokomplit (Autocomplete): Saran Kata yang Cepat
- Pemeriksaan Ejaan (Spell Checking): Mendeteksi dan Memperbaiki Kesalahan
- Pencarian Awalan (Prefix Searching): Menemukan Kata-Kata dengan Awalan Tertentu
- Perutean IP (IP Routing): Pencarian Rute yang Efisien
- Kamus (Dictionaries): Menyimpan dan Mencari Kata-Kata
- Trie Tingkat Lanjut: Variasi dan Optimalisasi
- Compressed Trie (Patricia Trie): Mengurangi Penggunaan Ruang
- Suffix Trie: Aplikasi untuk Pencarian String
- Trie Hash: Kombinasi Trie dan Hash Table
- Tips dan Trik Trie: Praktik Terbaik untuk Penggunaan yang Efisien
- Memilih Ukuran Alfabet yang Tepat
- Menangani Data Sensitif Huruf Besar/Kecil
- Optimalisasi Memori untuk Trie Skala Besar
- Kesimpulan: Meringkas Kekuatan Trie
- Kelebihan dan Kekurangan Trie
- Kapan Menggunakan Trie vs. Struktur Data Lainnya
- Langkah Selanjutnya: Sumber Daya untuk Pembelajaran Lebih Lanjut
1. Pengantar Trie
Apa itu Trie? Definisi dan Tujuan
Trie, yang berasal dari kata “retrieval”, adalah struktur data tree yang digunakan untuk menyimpan sekumpulan string. Berbeda dengan binary search tree (BST) di mana setiap node menyimpan satu kunci data, setiap node dalam Trie mewakili sebuah karakter. Jalur dari root ke sebuah node mewakili string. Tujuan utama Trie adalah memungkinkan operasi pencarian, penyisipan, dan penghapusan string yang cepat.
Bayangkan sebuah pohon di mana setiap cabang mewakili sebuah huruf. Untuk menemukan kata “cat”, Anda akan mulai di akar, mengikuti cabang ‘c’, lalu cabang ‘a’, dan akhirnya cabang ‘t’. Jika node ‘t’ ditandai sebagai akhir kata, maka “cat” ada di Trie.
Mengapa Menggunakan Trie? Manfaat Utama
Trie menawarkan beberapa keuntungan dibandingkan struktur data lainnya seperti hash table atau BST ketika menangani string:
- Pencarian Awalan yang Efisien: Trie sangat unggul dalam menemukan semua kata yang dimulai dengan awalan tertentu. Kompleksitasnya hanya bergantung pada panjang awalan.
- Penyisipan dan Pencarian Cepat: Penyisipan dan pencarian string memiliki kompleksitas O(m), di mana m adalah panjang string. Ini lebih cepat daripada BST, di mana kompleksitas bisa mencapai O(m log n) dalam kasus terburuk.
- Tidak Memerlukan Fungsi Hash: Karena Trie menggunakan karakter langsung sebagai kunci, tidak perlu fungsi hash, menghindari kemungkinan tabrakan.
- Pengurutan Alfabetis: Trie secara implisit mengurutkan string yang disimpan dalam urutan alfabetis.
Trie vs. Struktur Data Lainnya: Kapan Harus Menggunakan Trie?
Meskipun Trie memiliki banyak keuntungan, penting untuk mempertimbangkan kapan harus menggunakannya. Berikut perbandingan singkat dengan struktur data lainnya:
- Trie vs. Hash Table: Hash table memberikan pencarian dalam waktu O(1) rata-rata, tetapi tidak efisien untuk pencarian awalan atau menemukan kata-kata yang berdekatan secara leksikografis. Trie unggul dalam skenario ini. Jika Anda hanya membutuhkan pencarian kata yang cepat dan tidak memerlukan pencarian awalan, hash table mungkin lebih baik.
- Trie vs. Binary Search Tree (BST): BST efisien untuk data terurut dan memungkinkan pencarian, penyisipan, dan penghapusan dalam waktu O(log n) rata-rata. Namun, Trie lebih cepat untuk operasi string, terutama dengan pencarian awalan. BST juga lebih hemat ruang jika kata-kata memiliki awalan yang sangat tumpang tindih.
- Trie vs. Array: Array sederhana untuk menyimpan string, tetapi pencarian membutuhkan waktu O(n). Trie jauh lebih efisien untuk pencarian string.
Kesimpulan: Gunakan Trie ketika Anda membutuhkan:
- Pencarian awalan yang cepat.
- Penyisipan dan pencarian string yang efisien.
- Kemampuan untuk menemukan kata-kata yang berdekatan secara leksikografis.
2. Anatomi Trie: Membongkar Struktur
Nodes dan Edges: Komponen Dasar
Trie terdiri dari nodes dan edges. Setiap node mewakili sebuah karakter, dan edges menghubungkan nodes untuk membentuk kata-kata. Root node adalah awal dari semua kata.
Root Node: Awal dari Segalanya
Root node adalah node teratas dalam Trie. Ini tidak mewakili karakter apa pun, tetapi berfungsi sebagai titik masuk untuk semua kata dalam Trie. Semua pencarian dan penyisipan dimulai dari root node.
Children Nodes: Ekspansi Trie
Setiap node dapat memiliki beberapa children nodes, satu untuk setiap karakter yang mungkin mengikuti karakter yang diwakili oleh node saat ini. Misalnya, jika sebuah node mewakili karakter ‘a’, ia dapat memiliki children node untuk ‘b’, ‘c’, ‘d’, dan seterusnya, tergantung pada kata-kata yang disimpan dalam Trie.
End-of-Word Markers: Menandai Penyelesaian Kata
Untuk membedakan antara awalan dan kata lengkap, kita menggunakan end-of-word marker. Marker ini biasanya berupa boolean flag yang disimpan di setiap node. Jika flag ini diatur ke true, itu berarti jalur dari root ke node ini mewakili kata lengkap.
Contoh:
Misalkan kita ingin menyimpan kata-kata “cat”, “car”, dan “cab” dalam Trie. Struktur Trie akan terlihat seperti ini:
(root)
/|\
c a -
| |
a r b
| |
t - -
Dalam contoh ini, nodes yang diwakili oleh ‘t’, ‘r’, dan ‘b’ akan memiliki end-of-word markers yang diatur ke true.
3. Operasi Dasar Trie: Membangun dan Berinteraksi dengan Trie
Ada tiga operasi dasar yang dapat dilakukan pada Trie:
Penyisipan (Insertion): Menambahkan Kata ke Trie
Untuk menyisipkan kata ke dalam Trie, kita mulai dari root node dan melakukan iterasi melalui setiap karakter dalam kata. Untuk setiap karakter, kita periksa apakah node anak yang sesuai sudah ada. Jika ada, kita bergerak ke node anak itu. Jika tidak, kita membuat node anak baru dan bergerak ke sana. Setelah kita mencapai akhir kata, kita menandai node terakhir sebagai end-of-word node.
Algoritma Penyisipan:
- Mulai dari root node.
- Untuk setiap karakter dalam kata:
- Jika node anak untuk karakter ini ada, pindah ke node anak itu.
- Jika tidak, buat node anak baru dan pindah ke sana.
- Tandai node terakhir sebagai end-of-word node.
Pencarian (Search): Memeriksa Keberadaan Kata
Untuk mencari kata dalam Trie, kita mulai dari root node dan melakukan iterasi melalui setiap karakter dalam kata. Untuk setiap karakter, kita periksa apakah node anak yang sesuai ada. Jika tidak, kata tersebut tidak ada dalam Trie. Jika kita mencapai akhir kata dan node terakhir adalah end-of-word node, maka kata tersebut ada dalam Trie.
Algoritma Pencarian:
- Mulai dari root node.
- Untuk setiap karakter dalam kata:
- Jika node anak untuk karakter ini tidak ada, kembalikan false (kata tidak ada).
- Jika ada, pindah ke node anak itu.
- Jika node terakhir adalah end-of-word node, kembalikan true (kata ada). Jika tidak, kembalikan false (kata tidak ada).
Penghapusan (Deletion): Menghapus Kata dari Trie
Penghapusan dari Trie sedikit lebih rumit daripada penyisipan atau pencarian. Kita perlu memastikan bahwa kita tidak menghapus bagian dari kata lain yang masih ada dalam Trie. Ada beberapa cara untuk menghapus sebuah kata:
- Pencarian dan Penandaan: Cari kata tersebut. Jika ditemukan, tandai end-of-word marker pada node terakhir sebagai false. Ini secara efektif menghapus kata tersebut tanpa memengaruhi kata-kata lain yang berbagi awalan.
- Penghapusan Rekursif: Cari kata tersebut. Jika ditemukan, hapus node secara rekursif kembali ke root, tetapi *hanya* jika node tersebut tidak memiliki children dan bukan merupakan akhir dari kata lain.
Algoritma Penghapusan (Penghapusan Rekursif):
- Cari kata tersebut. Jika tidak ditemukan, tidak ada yang perlu dihapus.
- Jika kata tersebut ditemukan, mulai dari node terakhir dan rekursif kembali ke root:
- Jika node saat ini tidak memiliki children *dan* bukan merupakan end-of-word node (untuk kata lain), hapus node tersebut.
- Jika tidak, berhenti (karena node ini diperlukan untuk kata lain).
4. Implementasi Trie: Langkah demi Langkah dengan Contoh Kode
Mari kita implementasikan Trie dalam berbagai bahasa pemrograman. Kita akan fokus pada operasi penyisipan, pencarian, dan penghapusan.
Representasi Node: Cara Memodelkan Node Trie
Pertama, kita perlu mendefinisikan struktur node untuk Trie kita. Setiap node akan menyimpan:
- Sebuah array (atau hash table) dari children nodes, satu untuk setiap karakter yang mungkin.
- Sebuah boolean flag yang menunjukkan apakah node ini adalah akhir dari sebuah kata.
Fungsi Penyisipan (Insertion): Implementasi Mendalam
Fungsi penyisipan dimulai dari root node dan melakukan iterasi melalui setiap karakter dalam kata. Untuk setiap karakter, ia memeriksa apakah node anak yang sesuai sudah ada. Jika tidak, ia membuat node anak baru. Kemudian, ia bergerak ke node anak berikutnya. Akhirnya, ia menandai node terakhir sebagai akhir dari sebuah kata.
Fungsi Pencarian (Search): Implementasi Mendalam
Fungsi pencarian dimulai dari root node dan melakukan iterasi melalui setiap karakter dalam kata. Untuk setiap karakter, ia memeriksa apakah node anak yang sesuai sudah ada. Jika tidak, ia mengembalikan false. Jika ia mencapai akhir kata dan node terakhir ditandai sebagai akhir dari sebuah kata, ia mengembalikan true.
Fungsi Penghapusan (Deletion): Implementasi Mendalam
Fungsi penghapusan (menggunakan metode rekursif) dimulai dengan mencari kata. Jika ditemukan, ia memulai proses rekursif dari node terakhir. Node hanya dihapus jika tidak memiliki children dan bukan akhir dari kata lain.
Contoh Kode Lengkap (Python, Java, C++)
Berikut adalah contoh kode lengkap untuk implementasi Trie dalam Python, Java, dan C++:
Python
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word
def delete(self, word):
def _delete(node, word, index):
if index == len(word):
if not node.is_end_of_word:
return False # Word not in trie
node.is_end_of_word = False
return len(node.children) == 0
char = word[index]
if char not in node.children:
return False # Word not in trie
should_delete_child = _delete(node.children[char], word, index + 1)
if should_delete_child:
del node.children[char]
return len(node.children) == 0 and not node.is_end_of_word
return False
_delete(self.root, word, 0)
# Example Usage
trie = Trie()
trie.insert("cat")
trie.insert("car")
trie.insert("cab")
print(trie.search("cat")) # Output: True
print(trie.search("dog")) # Output: False
trie.delete("cat")
print(trie.search("cat")) # Output: False
print(trie.search("car")) # Output: True
Java
class TrieNode {
TrieNode[] children;
boolean isEndOfWord;
public TrieNode() {
children = new TrieNode[26]; // Assuming lowercase English alphabet
isEndOfWord = false;
}
}
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
int index = ch - 'a';
if (node.children[index] == null) {
node.children[index] = new TrieNode();
}
node = node.children[index];
}
node.isEndOfWord = true;
}
public boolean search(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
int index = ch - 'a';
if (node.children[index] == null) {
return false;
}
node = node.children[index];
}
return node.isEndOfWord;
}
public void delete(String word) {
deleteHelper(root, word, 0);
}
private boolean deleteHelper(TrieNode node, String word, int index) {
if (index == word.length()) {
if (!node.isEndOfWord) {
return false;
}
node.isEndOfWord = false;
return isEmpty(node);
}
char ch = word.charAt(index);
int charIndex = ch - 'a';
if (node.children[charIndex] == null) {
return false;
}
boolean shouldDeleteChild = deleteHelper(node.children[charIndex], word, index + 1);
if (shouldDeleteChild) {
node.children[charIndex] = null;
return isEmpty(node) && !node.isEndOfWord;
}
return false;
}
private boolean isEmpty(TrieNode node) {
for (int i = 0; i < 26; i++) {
if (node.children[i] != null) {
return false;
}
}
return true;
}
}
// Example Usage
public class Main {
public static void main(String[] args) {
Trie trie = new Trie();
trie.insert("cat");
trie.insert("car");
trie.insert("cab");
System.out.println(trie.search("cat")); // Output: true
System.out.println(trie.search("dog")); // Output: false
trie.delete("cat");
System.out.println(trie.search("cat")); // Output: false
System.out.println(trie.search("car")); // Output: true
}
}
C++
#include
#include
class TrieNode {
public:
std::vector children;
bool isEndOfWord;
TrieNode() : children(26, nullptr), isEndOfWord(false) {}
};
class Trie {
private:
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
void insert(const std::string& word) {
TrieNode* node = root;
for (char ch : word) {
int index = ch - 'a';
if (!node->children[index]) {
node->children[index] = new TrieNode();
}
node = node->children[index];
}
node->isEndOfWord = true;
}
bool search(const std::string& word) {
TrieNode* node = root;
for (char ch : word) {
int index = ch - 'a';
if (!node->children[index]) {
return false;
}
node = node->children[index];
}
return node->isEndOfWord;
}
void deleteWord(const std::string& word) {
deleteHelper(root, word, 0);
}
bool deleteHelper(TrieNode* node, const std::string& word, int index) {
if (index == word.length()) {
if (!node->isEndOfWord) {
return false;
}
node->isEndOfWord = false;
return isEmpty(node);
}
char ch = word[index];
int charIndex = ch - 'a';
if (node->children[charIndex] == nullptr) {
return false;
}
bool shouldDeleteChild = deleteHelper(node->children[charIndex], word, index + 1);
if (shouldDeleteChild) {
delete node->children[charIndex];
node->children[charIndex] = nullptr;
return isEmpty(node) && !node->isEndOfWord;
}
return false;
}
bool isEmpty(TrieNode* node) {
for (int i = 0; i < 26; ++i) {
if (node->children[i] != nullptr) {
return false;
}
}
return true;
}
};
int main() {
Trie trie;
trie.insert("cat");
trie.insert("car");
trie.insert("cab");
std::cout << std::boolalpha;
std::cout << trie.search("cat") << std::endl; // Output: true
std::cout << trie.search("dog") << std::endl; // Output: false
trie.deleteWord("cat");
std::cout << trie.search("cat") << std::endl; // Output: false
std::cout << trie.search("car") << std::endl; // Output: true
return 0;
}
Kode di atas memberikan implementasi dasar dari Trie dengan operasi insert, search, dan delete. Perhatikan bahwa implementasi penghapusan bersifat rekursif dan berhati-hati untuk tidak menghapus nodes yang digunakan oleh kata-kata lain.
5. Kompleksitas Waktu dan Ruang Trie: Menganalisis Kinerja
Kompleksitas Waktu: Penyisipan, Pencarian, dan Penghapusan
- Penyisipan: O(m), di mana m adalah panjang string yang akan disisipkan.
- Pencarian: O(m), di mana m adalah panjang string yang akan dicari.
- Penghapusan: O(m), di mana m adalah panjang string yang akan dihapus (ditambah, dalam kasus terburuk, perjalanan rekursif ke atas, tetapi ini masih terkait dengan panjang string).
Perhatikan bahwa kompleksitas waktu tidak bergantung pada jumlah kata yang disimpan dalam Trie. Ini adalah salah satu keuntungan utama Trie.
Kompleksitas Ruang: Efisiensi Penggunaan Memori
Kompleksitas ruang Trie bergantung pada jumlah kata yang disimpan dan panjang awalan umum. Dalam kasus terburuk, di mana tidak ada awalan umum, kompleksitas ruang bisa O(N * m), di mana N adalah jumlah kata dan m adalah panjang rata-rata kata.
Namun, jika ada banyak awalan umum, Trie dapat menghemat ruang secara signifikan dibandingkan dengan menyimpan setiap kata secara terpisah.
Trade-off: Memahami Batasan
Meskipun Trie cepat untuk pencarian string, ia menggunakan lebih banyak memori daripada struktur data lain seperti hash table. Oleh karena itu, penting untuk mempertimbangkan trade-off antara waktu dan ruang ketika memilih Trie.
6. Kasus Penggunaan Trie: Aplikasi Dunia Nyata
Trie memiliki banyak aplikasi dunia nyata, termasuk:
Otokomplit (Autocomplete): Saran Kata yang Cepat
Trie digunakan secara luas dalam sistem otokomplit untuk menyarankan kata-kata saat pengguna mengetik. Dengan melintasi Trie berdasarkan awalan yang diketik pengguna, sistem dapat dengan cepat menemukan semua kata yang dimulai dengan awalan itu.
Pemeriksaan Ejaan (Spell Checking): Mendeteksi dan Memperbaiki Kesalahan
Trie dapat digunakan untuk memeriksa ejaan kata. Jika sebuah kata tidak ditemukan dalam Trie, sistem dapat menyarankan kata-kata serupa berdasarkan kesalahan ketik umum.
Pencarian Awalan (Prefix Searching): Menemukan Kata-Kata dengan Awalan Tertentu
Seperti yang telah kita bahas, Trie sangat efisien untuk menemukan semua kata yang dimulai dengan awalan tertentu.
Perutean IP (IP Routing): Pencarian Rute yang Efisien
Trie dapat digunakan dalam perutean IP untuk mencari rute tujuan terbaik berdasarkan alamat IP tujuan.
Kamus (Dictionaries): Menyimpan dan Mencari Kata-Kata
Trie dapat digunakan untuk menyimpan dan mencari kata-kata dalam kamus.
7. Trie Tingkat Lanjut: Variasi dan Optimalisasi
Ada beberapa variasi dan optimalisasi dari Trie yang dapat digunakan untuk meningkatkan kinerja dan efisiensi ruang:
Compressed Trie (Patricia Trie): Mengurangi Penggunaan Ruang
Compressed Trie, juga dikenal sebagai Patricia Trie, mengompresi jalur nodes dengan hanya satu anak menjadi satu edge. Ini dapat secara signifikan mengurangi penggunaan ruang, terutama ketika ada banyak jalur nodes dengan hanya satu anak.
Suffix Trie: Aplikasi untuk Pencarian String
Suffix Trie adalah Trie yang berisi semua akhiran dari string. Ini dapat digunakan untuk berbagai masalah pencarian string, seperti menemukan semua kemunculan pola dalam string.
Trie Hash: Kombinasi Trie dan Hash Table
Trie Hash menggabungkan keuntungan dari Trie dan hash table. Ia menggunakan hash table untuk menyimpan children nodes dari setiap node, yang dapat meningkatkan kinerja pencarian.
8. Tips dan Trik Trie: Praktik Terbaik untuk Penggunaan yang Efisien
Berikut adalah beberapa tips dan trik untuk menggunakan Trie secara efisien:
Memilih Ukuran Alfabet yang Tepat
Ukuran alfabet memengaruhi ukuran array children di setiap node. Untuk alfabet yang lebih besar (misalnya, Unicode), menggunakan hash table atau map alih-alih array dapat lebih efisien.
Menangani Data Sensitif Huruf Besar/Kecil
Untuk menangani data sensitif huruf besar/kecil, Anda dapat mengonversi semua kata menjadi huruf kecil atau huruf besar sebelum memasukkannya ke dalam Trie.
Optimalisasi Memori untuk Trie Skala Besar
Untuk Trie skala besar, pertimbangkan untuk menggunakan teknik kompresi seperti Compressed Trie atau menggunakan memori eksternal untuk menyimpan data.
9. Kesimpulan: Meringkas Kekuatan Trie
Kelebihan dan Kekurangan Trie
Kelebihan:
- Pencarian awalan yang cepat.
- Penyisipan dan pencarian string yang efisien.
- Tidak memerlukan fungsi hash.
- Pengurutan alfabetis implisit.
Kekurangan:
- Penggunaan memori yang tinggi dalam kasus terburuk.
- Implementasi yang lebih kompleks daripada struktur data lainnya.
Kapan Menggunakan Trie vs. Struktur Data Lainnya
Gunakan Trie ketika Anda membutuhkan pencarian awalan yang cepat, penyisipan dan pencarian string yang efisien, dan kemampuan untuk menemukan kata-kata yang berdekatan secara leksikografis. Pertimbangkan struktur data lain seperti hash table atau BST jika Anda memiliki keterbatasan memori atau jika Anda tidak memerlukan pencarian awalan.
Langkah Selanjutnya: Sumber Daya untuk Pembelajaran Lebih Lanjut
Jika Anda ingin mempelajari lebih lanjut tentang Trie, berikut adalah beberapa sumber daya yang bermanfaat:
- Buku: "Introduction to Algorithms" oleh Thomas H. Cormen et al.
- Situs web: GeeksforGeeks, LeetCode
- Kursus online: Coursera, Udemy
Semoga panduan lengkap ini membantu Anda memahami Trie dan aplikasinya. Selamat coding!
```
