Binary Search Tree

Binary Search Tree adalah sebuah struktur data yang terdiri dari node yang memiliki cabang paling banyak 2 cabang. Cabang tersebut biasa dinamakan node kanan dan node kiri. Node kiri selalu berisi data yang nilainya lebih kecil dari node sebelumnya, sedangkan node kanan selalu berisi data yang nilainya lebih besar dari node sebelumnya. Node utama yang berada paling atas dinamakan root. Sedangkan node yang paling luar yang tidak memiliki children dinamakan leaf. Ilustrasi dari sebuah binary search tree adalah seperti berikut:

Contoh sebuah struct untuk node binary tree dengan C++:

struct bst{

    int value;

    bst *parent;

    bst *left;

    bst *right;

    bst(int val){

        value = val;

        parent = nullptr;

        left = nullptr;

        right = nullptr;

    }

} *root = nullptr;

value di didalam struct ini adalah untuk menyimpan datanya. Lalu ada 3 pointer, pointer parent menunjuk ke arah parent atau node diatasnya, pointer left menunjuk ke arah data yang nilainya lebih kecil, pointer right menunjuk ke arah data yang nilainya lebih besar.


Ada 3 operasi dasar pada binary search tree yaitu insert(), find(), dan remove().
Operasi yang pertama adalah find().Operasi ini adalah operasi untuk mencari apakah suatu nilai ada di dalam tree-nya. Contoh fungsi find():

bst* find(int val){

    if(root == nullptr) return nullptr;

    bst *cur = root;

    while(true){

        if(val == cur->value)

            return cur;

        else if(val > cur->value){

            if(cur->right == nullptr)

                break;

            else

                cur = cur->right;

        }

        else if(val < cur->value){

            if(cur->left == nullptr)

                break;

            else

                cur = cur->left;

        }   

    }

    return nullptr;

}

Fungsi ini akan mengembalikan pointer dari nilai yang dicari jika ketemu dan mengembalikan pointer kosong (nullpointer) jika tidak ketemu. Karena fungsi ini mengembalikan pointer ke struct yang dicari, maka perlu dibuat fungsi lain yang gunanya untuk mengecek jika nilai tersebut ada atau tidak.

bool exist(int val){

    if(find(val) != nullptr)

        return true;

    else

        return false;

}

 Fungsi exist() ini adalah fungsi boolean yang akan mengembalikan true apabila nilai yang dicari ada dan false bila tidak ada. Fungsi ini dibuat untuk mempermudah melakukan pengecekan nilai karena tidak perlu mengecek dari adanya data atau nullpointer.


Operasi yang kedua adalah operasi insert(). Operasi ini berfungsi untuk memasukkan nilai baru kedalam sebuah binary search tree. Contoh operasi insert():

void insert(int val){

    if(root == nullptr) // If root is empty, create root

        root = new bst(val);

    else{

        bst *cur = root;

        while(true){

            if(val > cur->value){   // If value is bigger traverse left

                if(cur->right == nullptr){

                    bst *newnode = new bst(val);

                    cur->right = newnode;

                    newnode->parent = cur;

                    break;

                }

                else

                    cur = cur->right;

            }

            else if(val < cur->value){  // If value is smaller traverse left

                if(cur->left == nullptr){

                    bst *newnode = new bst(val);

                    cur->left = newnode;

                    newnode->parent = cur;

                    break;

                }

                else

                    cur = cur->left;

            }

            else break; // If value already exist, break

        }

    }

}

Fungsi insert() hanya akan boleh berjalan apabila nilai yang ingin dimasukkan belum ada pada tree-nya. Jika rootnya belum ada maka node baru akan dibuat di root. Jika root sudah ada maka node tersebut akan ditempatkan sesuai dengan aturan binary search tree yaitu kiri lebih kecil, kanan lebih besar.

Operasi dasar terakhir adalah operasi remove(). Operasi ini berguna untuk menghapus data yang sudah ada. Contoh operasi remove():

void remove(int val){

    bst* cur = find(val);   // Find the value to be deleted

    if(cur == nullptr) return;  // If value is not found

    // Check the position if the data is on the right or left node

    bool isroot = false, isleft = false;

    if(cur->parent == nullptr)  // If the is a root

        isroot = true;

    else if(cur->parent->left == cur)

        isleft = true;

    else if(cur->parent->right == cur)

        isleft = false;

    if(cur->left == nullptr && cur->right == nullptr){  // If node has no children

        if(!isroot){

            if(isleft)

                cur->parent->left = nullptr;

            else

                cur->parent->right = nullptr;

        }

        delete cur;

    }

    else if(cur->left != nullptr && cur->right == nullptr){ // If node only has one children on left

        if(isroot){

            root = cur->left;

        }

        else{

            if(isleft)

                cur->parent->left = cur->left;

            else

                cur->parent->right = cur->left;

        }

        delete cur;

    }

    else if(cur->left == nullptr && cur->right != nullptr){ // If node only has one children on right

        if(isroot){

            root = cur->right;

        }

        else{

            if(isleft)

                cur->parent->left = cur->right;

            else

                cur->parent->right = cur->right;

        }

        delete cur;

    }

    else{   // If node has two childrens

       bst *successor = cur->right;

        // Finding successor

        while(true){

            if(successor->left != nullptr)

                successor = successor->left;

            else

                break;

        }

        // Put the node's successor as replacement

        if(isroot){

            // Check if successor is the first node after 

            if(successor->parent == cur){

                successor->left = root->left;

                successor->parent = nullptr;

            }

            else{

                // Put the right side of successor (if there's any) to it's parent

                successor->parent->left = successor->right;

                

                // replacing the root with successor

                successor->left = root->left;

                successor->right = root->right;

                successor->parent = nullptr;

            }

            root = successor;

        }

        else{

            // Check if successor is the first node after 

            if(successor->parent == cur){

                successor->left = cur->left;

                successor->parent = cur->parent;

                if(isleft)

                    cur->parent->left = successor;

                else

                    cur->parent->right = successor;

            }

            else{

                // Put the right side of successor (if there's any) to it's parent

                successor->parent->left = successor->right;

                

                // replacing the root with successor

                successor->left = cur->left;

                successor->right = cur->right;

                successor->parent = cur->parent;

                

                if(isleft)

                    cur->parent->left = successor;

                else

                    cur->parent->right = successor;

            }

        }

        delete cur;

    }

}

Pertama fungsi nilai yang ingin di delete dicari lebih dulu dengan menggunakan fungsi find(). Lalu fungsi remove() dibagi menjadi 2 kondisi yaitu ketika dia root atau bukan dan dibagi lagi menjadi 3 kondisi yaitu ketika dia memiliki satu children, dua children, dan tidak ada children. Cara untuk menghapus untuk setiap kondisi berbeda-beda yang dapat dilihat dari kode diatas.

Setelah membuat ketiga fungsi diatas, tentu saja perlu suatu fungsi untuk memprint angka untuk mengecek hasilnya. Contoh fungsi yang memprint angka dari kecil ke besar (secara inorder):

void printinorder(bst *node){

    if(node->left != nullptr)

        printinorder(node->left);

    cout << node->value << " ";

    if(node->right != nullptr)

        printinorder(node->right);

}

Lalu contoh program untuk mengetes semua fungsi diatas:

int main(){

    // Adding numbers to the tree

    insert(5);

    insert(3);

    insert(9);

    insert(6);

    insert(1);

    cout << "All numbers in ascending order:" << endl;

    printinorder(root);

    cout << endl;

    if(exist(3))

        cout << "3 exist in the tree" << endl;

    else

        cout << "3 not exist in the tree" << endl;

    cout << endl;

    // Removing 3 from the tree

    remove(3);

    cout << "After removal:" << endl;

    printinorder(root);

    cout << endl;

    if(exist(3))

        cout << "3 exist in the tree" << endl;

    else

        cout << "3 not exist in the tree" << endl;

    

    return 0;

}

Output:

    All numbers in ascending order:

1 3 5 6 9

    3 exist in the tree

    After removal:

    1 5 6 9

    3 not exist in the tree

Hash Table dan Implementasinya dalam Blockchain

Hash Table adalah sebuah struktur data yang menggunakan array sebagai media penyimpanannya. Sebuah data diproses melalui suatu fungsi yang akan menentukan index dari array untuk menyimpannya. Fungsi tersebut dinamakan hash function dan isi dari sebuah hash function bermacam-macam. Collision terjadi ketika sebuah data dimasukkan ke hash function dan menghasilkan index yang sama dengan data yang berbeda.

Suatu hash function yang bagus adalah ketika jarang terjadinya collision dengan data yang bermacam-macam. Maka dari itu hash function yang bagus memiliki sifat pseudo-random yaitu acak tetapi terkontrol. Artinya output yang dikeluarkan hanya mengeluarkan 1 jenis untuk 1 tipe data. Itulah alasannya mengapa hash table biasanya digunakan dalam pengenkripsian data.

Contoh penggunaan hash table untuk meginput data:

int hash_table[100];   // Deklarasi hash table sebesar 100

hash_table[hash_function(10)] = 10; // Menaruh data ke index dari suatu hash function

Lalu ketika memprint hanya tinggal mendapatkan indeks array dari hash functionnya lagi

cout << hash_table[hash_function(10)];

Output:

10

Karena indeks dari hash table bisa didapatkan hanya dengan perantara hash function maka waktu untuk insert, delete, dan searching dalam hash table adalah O(1). Tetapi tentu saja itu hash table hanya akan O(1) jika tidak terjadi collision sama sekali.

Salah satu implementasi dari hash table adalah dalam blockchain. Blockchain adalah sebuah record yang disimpan dengan kriptografi. Satu record dalam blockchain disebut sebagai blok. Sebuah blok di blockchain disimpan dengan suatu kunci melalui sebuah hash function kriptografis. Artinya hash function tersebut akan mengeluarkan kunci yang unik untuk setiap data yang berbeda. Suatu blok menyimpan kunci dari blok sebelumnya dan blok tersebut juga akan disimpan kuncinya oleh blok yang baru. Itulah yang membuat blok chain aman karena kunci dari setiap blok disimpan dari masing-masing blok setelahnya dibandingkan dengan semua kunci disimpan di satu pusat.

Ketika seseorang melakukan penyerangan kepada sebuah blok di dalam blockchain, dia harus mengubah dari akarnya karena jika dia mengubah isi dari suatu blok yang berada di tengah maka kunci yang keluar akan berbeda dengan yang disimpan oleh blok-blok selanjutnya. Ini disebabkan oleh sifat dari hash function kriptografis tadi yang hasilnya akan berubah jika ada sedikit perubahan dalam datanya. Contoh penggunaan blockchain adalah dalam sistem Cryptocurrency. Dengan menyimpan data transaksi para penggunanya ke dalam sebuah blokchain maka data tersebut diamankan dari penyerang yang ingin mengubah data transaksi tersebut.

Mebuat sebuah Linked List

Untuk membuat linked list yang pertama adalah dengan membuat struct yang akan dijadikan linked list.

Struct linked list simpel:

template<class T>

struct llist{

    T val;

    llist *next = NULL;

};

Setelah dibuat struct-nya harus dibuat pointer untuk menentukan awal dan akhir untuk linked list tersebut. Barulah dibuat fungsi untuk memasukkan dan menghapus nilai di dalam sebuah linked list.

Mendeklarasi awal dan akhir linked list dengan tipe data int:

llist<int> *start = NULL, *end = NULL;

Tipe data bisa diganti dengan apa saja, tetapi untuk contoh menggunakan int dulu.

Fungsi insert untuk memasukkan data ke dalam linked list:

template<class T>

void insert(T val, llist<T> *&start, llist<T> *&end){

    if(start == NULL){

        llist<T> *newstart = new llist<T>;

        newstart->val = val;

        start = newstart;

        end = start;

    }

    else{

        llist<T> *newnode = new llist<T>;

        newnode->val = val;

        

        end->next = newnode;

        end = newnode;

    }

}

jika awal dari linked list masih kosong, maka node awal akan dibuat. Selain dari itu node baru akan dimasukkan di akhir dari linked list.

Fungsi remove untuk menghapus data dari linked list.

template<class T>

void remove(T val, llist<T> *start){

    llist<T> *cur = start, *prevcur = NULL;

    

    while(cur != NULL){

        if(cur->val == val){

            prevcur->next = cur->next;

            delete cur;

            cur = prevcur;

        }

        prevcur = cur;

        cur = cur->next;

    }

}

 Nilai yang ingin dihapus dicari lebih dulu dengan looping, kemudian node tersebut dihapus dan node sebelum dan sesudahnya disambung. 

 Fungsi untuk mem-print isi dari linked list:

template<class T>

void showlist(llist<T> *start){

    if(start == NULL) return;

    llist<T> *cur = start;

    while(cur != NULL){

        std::cout << cur->val << " ";

        cur = cur->next;

    }

    std::cout << std::endl;

}

Print isi dari linked list dengan men-loop seluruh node-nya hingga ketemu NULL.

 Contoh program untuk menggunakan semua fungsi diatas:

#include<iostream>

template<class T>

struct llist{

    T val;

    llist *next = NULL;

};

template<class T>

void insert(T val, llist<T> *&start, llist<T> *&end){

    if(start == NULL){

        llist<T> *newstart = new llist<T>;

        newstart->val = val;

        start = newstart;

        end = start;

    }

    else{

        llist<T> *newnode = new llist<T>;

        newnode->val = val;

        

        end->next = newnode;

        end = newnode;

    }

}

template<class T>

void remove(T val, llist<T> *start){

    llist<T> *cur = start, *prevcur = NULL;

    

    while(cur != NULL){

        if(cur->val == val){

            prevcur->next = cur->next;

            delete cur;

            cur = prevcur;

        }

        prevcur = cur;

        cur = cur->next;

    }

}

template<class T>

void showlist(llist<T> *start){

    if(start == NULL) return;

    llist<T> *cur = start;

    while(cur != NULL){

        std::cout << cur->val << " ";

        cur = cur->next;

    }

    std::cout << std::endl;

}

int main(){

    llist<int> *start = NULL, *end = NULL;

    insert<int>(1, start, end);

    insert<int>(4, start, end);

    insert<int>(6, start, end);

    insert<int>(4, start, end);

    remove<int>(4, start);

    showlist<int>(start);

    return 0;

}

          Output:

1 6