Binary Search Tree

Halo teman-teman, pada kesempatan kali ini saya ingin berbagi tentang Binary Search Tree.

Pendahuluan

Binary Search Tree (BST) adalah sebuah binary tree yang memiliki ciri-ciri sebagai berikut :

1. Setiap node mempunyai value dan tidak ada value yang double

2. Value yang ada di kiri tree lebih kecil dari rootnya

3. Value yang ada di kanan tree lebih besar dari rootnya

4. Kiri dan kanan tree bisa menjadi root lagi atau bisa mempunya child jadi BST ini memiliki sifat ( rekrusif )

Operasi Dasar 

Binary Search Tree memiliki 3 operasi dasar yaitu :
1. Searching : mencari value di dalam BST

2. Insertion : memasukkan value baru ke dalam BST

3. Deletion : menghapus key / value dari BST

Searching 

Bayangkan kita akan mencari value X :

1. Memulai Pencarian Dari Root

2. Jika Root adalah value yang kita cari , maka berhenti

3. Jika x lebih kecil dari root maka cari kedalam rekursif tree sebelah kiri

4. Jika x lebih besar dari root maka cari kedalam rekursif tree sebelah kanan

struct node* search(struct node* root, int key)

{

    // Base Cases: root is null or key is present at root

    if (root == NULL || root->key == key)

       return root;

     

    // Key is greater than root's key

    if (root->key < key)

       return search(root->right, key);

  

    // Key is smaller than root's key

    return search(root->left, key);

}

Insertion

Bayangkan kita menginsert value x :

1. Dimulai dari root

2. Jika x lebih kecil dari node value(key) kemudian cek dengan sub-tree sebelah kiri lakukan pengecekan secara berulang ( rekursif )

3. Jika x lebih besar dari node value(key) kemudian cek dengan sub-tree sebelah kanan lakukan pengecekan secara berulang ( rekursif )

4. Ulangi sampai menemukan node yang kosong untuk memasukan value X ( X akan selalu berada di paling bawah biasa di sebut Leaf atau daun )

struct node* insert(struct node* node, int key)

{

    /* If the tree is empty, return a new node */

    if (node == NULL) return newNode(key);

  

    /* Otherwise, recur down the tree */

    if (key < node->key)

        node->left  = insert(node->left, key);

    else if (key > node->key)

        node->right = insert(node->right, key);   

  

    /* return the (unchanged) node pointer */

    return node;

}

Deletion 

Akan ada 3 case yang ditemukan ketika ingin menghapus yang perlu diperhatikan :

1. Jika value yang ingin dihapus adalah Leaf(Daun) atau paling bawah , langsung delete

2. Jika value yang akan dihapus mempunyai satu anak, hapus nodenya dan gabungkan anaknya ke parent value yang dihapus

3. Jika value yang akan di hapus adalah node yang memiliki 2 anak , maka ada 2 cara , kita bisa cari dari left sub-tree anak kanan paling terakhir(leaf) (kiri,kanan)

struct node* deleteNode(struct node* root, int key)

{

    // base case

    if (root == NULL) return root;

  

    // If the key to be deleted is smaller than the root's key,

    // then it lies in left subtree

    if (key < root->key)

        root->left = deleteNode(root->left, key);

  

    // If the key to be deleted is greater than the root's key,

    // then it lies in right subtree

    else if (key > root->key)

        root->right = deleteNode(root->right, key);

  

    // if key is same as root's key, then This is the node

    // to be deleted

    else

    {

        // node with only one child or no child

        if (root->left == NULL)

        {

            struct node *temp = root->right;

            free(root);

            return temp;

        }

        else if (root->right == NULL)

        {

            struct node *temp = root->left;

            free(root);

            return temp;

        }

  

        // node with two children: Get the inorder successor (smallest

        // in the right subtree)

        struct node* temp = minValueNode(root->right);

  

        // Copy the inorder successor's content to this node

        root->key = temp->key;

  

        // Delete the inorder successor

        root->right = deleteNode(root->right, temp->key);

    }

    return root;

}