Apa itu Tries?
Tries adalah struktur data berbasis pohon yang digunakan untuk pencarian dan pengambilan string secara efisien. Setiap node di dalam pohon mewakili karakter dari satu atau beberapa string, dan setiap jalur dari root node ke node terakhir mewakili sebuah string lengkap.
Trie sering digunakan dalam aplikasi pemeriksaan ejaan (seperti auto-complete Google), serta dalam tabel rute untuk alamat IP.
Notes
- Trie dapat digunakan untuk mencari string yang memiliki awalan yang sama secara efisien. Hal ini karena semua string dengan awalan yang sama akan berbagi jalur yang sama dari node root sampai titik di mana karakter mereka berbeda.
- Trie juga dapat digunakan untuk aplikasi lain, seperti menyimpan dan mengambil data yang dapat direpresentasikan sebagai serangkaian karakter atau key.
- Trie dapat diimplementasikan menggunakan berbagai struktur data, seperti array atau linked list, tergantung pada persyaratan tertentu dari aplikasi.
- Kompleksitas waktu untuk insert dan search di trie sering kali O(m), di mana m adalah panjang string yang akan disisipkan atau dicari. Hal ini membuat trie menjadi struktur data yang sangat efisien untuk aplikasi yang membutuhkan pencarian dan pengambilan string yang cepat.
Ilustrasi
Berikut merupakan contoh ilustrasi dari Tries, dimana setiap node mempunyai 1 karakter dan string yang disimpan tergantung dari node mana mereka berakhir.
Contoh dimana kita melakukan search, kita mengetik "buk", maka akan keluar suggestion kata-kata berikutnya seperti "buku" dan "buka"
Implementasi
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ALPHABET_SIZE 26
typedef struct TrieNode {
struct TrieNode* children[ALPHABET_SIZE];
int isEndOfWord;
} TrieNode;
TrieNode* createNode() {
TrieNode* node = (TrieNode*) malloc(sizeof(TrieNode));
node->isEndOfWord = 0;
for (int i = 0; i < ALPHABET_SIZE; i++) {
node->children[i] = NULL;
}
return node;
}
void insert(TrieNode* root, char* key) {
TrieNode* node = root;
for (int i = 0; i < strlen(key); i++) {
int index = key[i] - 'a';
if (node->children[index] == NULL) {
node->children[index] = createNode();
}
node = node->children[index];
}
node->isEndOfWord = 1;
}
int search(TrieNode* root, char* key) {
TrieNode* node = root;
for (int i = 0; i < strlen(key); i++) {
int index = key[i] - 'a';
if (node->children[index] == NULL) {
return 0;
}
node = node->children[index];
}
return (node != NULL && node->isEndOfWord);
}
int main() {
TrieNode* root = createNode();
insert(root, "hello");
insert(root, "world");
insert(root, "trie");
insert(root, "tree");
printf("Search results:\n");
printf("hello: %d\n", search(root, "hello"));
printf("world: %d\n", search(root, "world"));
printf("trie: %d\n", search(root, "trie"));
printf("tree: %d\n", search(root, "tree"));
printf("test: %d\n", search(root, "test"));
return 0;
}Output
Search results:
hello: 1
world: 1
trie: 1
tree: 1
test: 0