Binary Search Tree (BST)

Stevanno Andrew Irawan
2301861005

BINARY SEARCH TREE (BST)

Binary Tree

       Tree adalah salah satu bentuk struktur data yang menggambarkan hubungan hierarki antar elemen elemennya. Sebuah node dalam tree biasanya bisa memiliki beberapa node lagi sebagai percabangan atas dirinya.

       Binary Tree adalah tree yang hanya dapat mempunyai meksimal 2 percabangan saja

                                            

Ada 3 jenis binary tree : 

1. Full Binary Tree, yaitu binary tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama

2. Complete Binary Tree, mirip dengan full binary tree namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.

3. Skewed Binary Tree, Binary Tree yang semua nodenya(kecuali leaf) hanya ada 1 child.

Binary Search Tree (BST)

       BST adalah struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap child node sebelah kiri selalu lebih kecil nilainya dari pada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya dari pada root node. 

Kenapa child node sebelah kiri harus lebih kecil dari child node sebelah kanan? Child node kiri harus lebih kecil untuk mempermudah / memberikan efisiensi terhadap proses searching.

Ada 3 jenis cara untuk melakukan penelusuran data(transversal) pada BST :

1. Pre Order : print data, telusur ke kiri, telusur ke kanan

2. In Order : terlusur ke kiri, print data, telusur ke kanan

3. Post Order : Telusur ke kiri, telusur ke kanan, print data

Insertion BST

Insertion dalam BST dilakukan dengan cara rekursif, Berikut adalah teorinya :

misalkan node baru adalah x,

1. mulai dari root/akar

2. jika x lebih kecil dari key node maka masukan x ke subtree kiri, selain itu masukan x ke subtree kanan

3. ulangi langkah diatas hingga menemukan node kosong untuk menaruh x(x akan selalu menjadi leaf / daun baru.

Deletion BST

Ada 3 hal yang harus diperhatikan :

1. jika key adalah leaf baru, maka tinggal dihapus saja.

2. jika key adalah sebuah node yang yang memiliki child node, hapus node tersebut dan sambung child node ke parent node dari node tersebut.

3. jika key ada di sebuah node yang memiliki 2 child node, cari node yang paling kanan dari subtree kiri(node P), ganti key tersebut dari key dari node P dan hapus P secara rekursif.

Koding untuk search :

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

{

    if (root == NULL || root->key == key) return 0;

    if (root->key < key) return search(root->right, key);

    return search(root->left, key);

}

Koding untuk inorder

void inorder(struct node *root)

{

    if (root != NULL)

    {

          inorder(root->left);

          printf("%d \n", root->key);

          inorder(root->right);

    }

}