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