Struktur Data - Binary Tree dan Huffman Coding

Tree adalah struktur data dimana tiap-tiap titik(node)-nya memiliki nilai serta pointer ke titik di bawahnya(child node).

Terdapat istilah-istilah yang perlu diketahui pada struktur data Tree ini. Perhatikan gambar di samping. Node yang memiliki angka 1 disebut sebagai root node, dan node yang berangka 5, 6, 7, 8, dan 9 disebut sebagai leaves. Node 2 dan node 3 merupakan siblings karena kedua node tersebut berasal dari parent node yang sama, yaitu 1. Sedangkan 5, 6, 7 adalah child node dari 3. Lalu 2 merupakan parent node dari 4.

Struktur data tree terdapat beberapa jenis, salah satunya adalah Binary Tree. Binary Tree merupakan struktur data tree yang tiap-tiap parent node-nya hanya memiliki dua child node. Tiap-tiap node pada binary tree tersusun oleh dua pointer dan data yang disimpan. Misalnya binary tree yang menyimpan integer, maka tiap-tiap node pada binary tree tersusun dari variabel bertipe integer, pointer ke child node kanan, dan pointer ke child node kiri.

Cara mendefinisikan node pada Binary Tree

typedef struct node
{
    // data yang disimpan
    int value;

    // pointer ke child node kiri
    struct node* left;

    // pointer ke child node kanan
    struct node* right;
} node;

// deklarasi root node sebagai variabel global
node* root = NULL;

Ketika ingin mencari suatu data pada Binary Tree, pastikan terlebih dahulu bahwa data pada Binary Tree tersebut dalam keadaan terurut. Maksudnya adalah nilai child node sebelah kanan harus lebih besar dari nilai parent node, sedangkan nilai child node sebelah kiri harus lebih kecil dari nilai parent node-nya, atau sebaliknya.

Pada setiap parent node yang memiliki child node, nilai child node sebelah kanan lebih besar sedangkan nilai child node sebelah kiri lebih kecil

Setelah dipastikan terurut, pencarian data dimulai dari root node. Kita dapat menggunakan algoritma Binary Search untuk mencari data pada Binary Tree. Misalkan nilai yang kita cari lebih besar dari nilai node yang kita cek, maka pencarian akan bergerak ke child node sebelah kanan, lalu kemudian ketika nilai pada child node itu di cek lagi dan ternyata lebih besar dari nilai yang kita cari, maka pencarian akan bergerak ke child node sebelah kiri. Jika nilai pada node sama dengan nilai yang kita cari maka ketemu, namun ketika kita sampai pada node yang tidak ada nilai(NULL), berarti tidak ketemu.

Fungsi pencarian pada Binary Tree dengan nilai kembalian berupa boolean

/**
 * @param value: nilai yang ingin dicari
 * @param tree: tree yang salah satu nilainya sedang dicari
 */
bool contains(int value, node* tree)
{
    // pencarian dimulai dari root node
    node* current = tree;
    
    // pencarian terus berlanjut selama tidak ketemu NULL
    while (current != NULL)
    {
        if (current->value == value)
        {
            // jika nilai yang dicek sama dengan nilai yang dicari, berarti ketemu
            return true;
        }
        else if (current->value < value)
        {
            // jika nilai yang dicek lebih kecil dari yang dicari, 
            // maka pencarian bergerak ke child node kanan
            current = current->right;
        }
        else
        {
            // jika nilai yang dicek lebih besar dari yang dicari, 
            // maka pencarian bergerak ke child node kiri
            current = current->left;
        }
    }

    // tidak ketemu karena bertemu NULL
    return false;
}

Ketika ingin menyisipkan nilai pada Binary Tree, berarti kita akan menambahkan child node baru. Child node tersebut akan ditambah pada lokasi NULL tadi lalu dihubungkan dengan parent node. Jadi kita melakukan pencarian lokasi yang cocok untuk dimasukkan nilai tersebut. Jika bertemu NULL, maka masukkan nilai tersebut.

Fungsi memasukkan nilai pada Binary Tree dengan nilai kembalian berupa boolean

/**
 * @param value: nilai yang ingin dicari
 * @param tree: tree yang salah satu nilainya sedang dicari
 */
bool insert(int value, node* tree)
{
    // alokasi memori untuk membuat node baru
    node* new_node = malloc(sizeof(node));
    if (new_node == NULL)
    {
        // alokasi memori gagal
        return false;
    }
    
    // inisialisasi nilai tersebut ke node baru
    new_node->value = value;
    new_node->right = NULL;
    new_node->left = NULL;

    // pointer pembantu untuk mencari lokasi penyisipan
    node* current = tree;
    node* previous = NULL;

    // jika tree kosong
    if (current == NULL)
    {
        // berarti root node diinisialisasi oleh node baru tadi
        root = new_node;
        return true;
    }

    // lakukan pencarian lokasi selama belum ketemu NULL
    while (current != NULL)
    {
        // jika nilai yang ingin dimasukkan telah ada sebelumnya
        if (current->value == value)
        {
            // release memori dari nilai tersebut
            free(new_node);
            return false;
        }

        if (current->value < value)
        {
            // jika nilai yang dicek lebih kecil dari yang dicari, 
            // maka pencarian bergerak ke child node kanan
            previous = current;
            current = current->right;
        }
        else
        {
            // jika nilai yang dicek lebih besar dari yang dicari, 
            // maka pencarian bergerak ke child node kiri
            previous = current;
            current = current->left;
        }
    }

    // jika ketemu null
    if (current == NULL)
    {
        // maka sisipkan node baru pada lokasi tersebut
        current = new_node;

        if (previous->value < value)
        {
            // jika nilai yang disisipkan lebih besar dari parent node-nya,
            // berarti node baru dihubungkan oleh pointer sebelah kanan dari parent node-nya
            previous->right = current;
        }
        else
        {
            // jika nilai yang disisipkan lebih kecil dari parent node-nya,
            // berarti node baru dihubungkan oleh pointer sebelah kiri dari parent node-nya
            previous->left = current;
        }

        // penyisipan berhasil
        return true;
    }

    // penyisipan gagal
    return false;
}

Struktur data Binary Tree ini digunakan sebagai model untuk mengkompres(mengecilkan ukuran memori) dari suatu file. Suatu file yang berukuran besar perlu dikompres ketika ingin mengirimkannya melalui internet. Pengkompresan file ini menggunakan jumlah bits memori yang lebih kecil dari jumlah bits yang biasanya dipakai untuk merepresentasikan sebuah data. Metode ini dinamakan Huffman Coding.

Biasanya kita menggunakan ASCII untuk merepresentasikan data. ASCII adalah skema encoding yang berukuran tetap(biasanya 8 bit). Di sisi lain, huffman encoding adalah skema encoding yang ukurannya berbeda-beda tergantung pada banyaknya frekuensi suatu data yang ingin di-encoding.

Misalnya ketika kita ingin mengkompres sebuah string seperti pada gambar di samping. Kita akan menggunakan binary tree untuk menyusun skema encoding pada tiap karakter. Pertama-tama kita harus mencari tahu frekuensi kemunculan dari masing-masing karakter tersebut, nilainya dapat dilihat pada gambar di samping. Lalu susun nilai-nilai frekuensi tersebut sebagai leaves dari tree yang akan kita buat.

Kemudian, gabungkan dua node menjadi satu node dan tambahkan nilai frekuensi keduanya. Lakukan terus menerus hingga terbentuknya suatu tree seperti gambar di bawah

Lalu kita buat skema bahwa setiap child node sebelah kanan direpresentasikan oleh 1 sedangkan yang sebelah kiri direpresentasikan oleh 0. Jadi kita dapat merepresentasikan tiap huruf dengan jumlah bit yang berbeda. Misalnya huruf E yang frekuensi kemunculannya paling besar, kita hanya perlu merepresentasikannya dengan bit 1 dengan ukuran 1 bit dan itu akan menghemat memori dari pada kita merepresentasikannya dengan jumlah 8 bit. Lalu misalnya untuk merepresentasikan huruf C kita menggunakan 0001 dengan ukuran 4 bit.

--------------------------------------------------------------------------------------------------
https://study.cs50.net/