Saturday, June 18, 2011

Tugas Struktur Data (Trie)

Trie (prefix tree) adalah sebuah struktur data tree yang tersusun dan digunakan untuk menyimpan sebuah array yang terasosiasi (biasanya string)


Istilah TRIE berasal dari kata reTRIEval, karena trie bisa menemukan sebuah kata dalam kamus hanya dengan prefix (awalan) dari kata tersebut.

Trie adalah tree dimana setiap vertex mewakili sebuah kata atau prefix.
Root (akar) mewakili karakter kosong (‘’).
Sebuah vertex yang tepi jaraknya k dari root (akar) mempunyai prefix yang terasosiasi dari panjang k.
Biarkan a dan b menjadi 2 simpul dari trie dan anggap a adalah orang tua langsung darib, maka b harus mempunyai prefix yang terasosiasi dari a.

Kita bisa menggunakan struktur ini untuk mengimplementasikan trie:

struct trie {
    char chr;
    int  word;
    struct trie* edge[128];
} *root = 0;

root = (struct trie*)malloc(sizeof(struct trie));
root->chr  = ‘’;
root->word = 0;
Untuk meng-Insert sebuah kata ke dalam trie, kita bisa menggunakan kode ini:

void insert(struct trie *curr, char *p) {
    if ( curr->edge[*p] == 0 )
        curr->edge[*p] = newnode(*p);
    if ( *p == 0 ) curr->word = 1;     else insert(curr->edge[*p],p+1); }

newnode() function
struct trie* newnode(char x) {
    struct trie* node =
        (struct trie*)malloc(sizeof(struct trie));
    node->chr  = x;
    node->word = 0;
    for (i = 0; i < 128; i++ )
        node->edge[i] = 0;
    return node;
}

Andaikan kita ingin menemukan semua string yang terdapat dalam trie yang mempunyai prefix tertentu.
char s[100] = {“...”}; // global

int  i, n, okay;
struct trie *curr;
n    = strlen(s);
okay = 1;
curr = root;
for ( i = 0; i < n && okay == 1; i++ )
    if ( curr->edge[s[i]] == 0 ) okay = 0;
    else curr = curr->edge[s[i]];
if ( okay ) find(curr,n);

dan fungsi find  (mereka akan mencetak semua string yang mempunyai prefixnya)

void find(struct trie *curr, int x) {
    if ( curr->word == 1 ) {
        s[x] = 0;
        puts( s );
    }
    for ( i = 0; i < 128; i++ )
        if ( curr->edge[i] != 0 ) {
            s[x] = i;
            find(curr->edge[i],x+1);
        }
}