Binary Search Tree

Angelia
2301854492
COMP6048 - CB01

Pertemuan tanggal 17 Maret 2020 merupakan pertemuan tatap muka terakhir yang dilakukan kampus sebelum dilaksanakannya online learning. Pada pertemuan ini, telah dibahas mengenai Binary Search Tree beserta dengan simulasinya. Maka, berikut ini pembahasan mengenai"Binary Search Tree".

"BINARY SEARCH TREE"

A. Pengertian Binary Search Tree
Binary Search Tree atau biasa disingkat BST merupakan salah satu struktur data yang mempercepat pencarian dan pengurutan (sorting), dengan metode insertion dan deletion yang mudah. BST dikenal juga sebagai binary tree yang diurutkan (sorted version of Binary Tree).


B. Properti Binary Tree
Berikut ini penjelasan properti di Binary Search Tree:

Sumber: Geeksforgeeks.org

Menggunakan contoh dari gambar di atas, maka akan dijelaskan macam-macam istilah dalam BST:
- Root    : Berperan sebagai akar paling atas/pusatnya tree, yaitu angka 8.
- Parent  : Node yang berada satu level di atas suatu node tertentu, contohnya angka 3 adalah parent node dari angka 1 dan angka 6.
- Child   : Node yang berada satu level di bawah suatu node tertentu, contohnya angka 14 adalah child node dari angka 10.
- Leaf     : Node yang tidak memiliki child, contohnya angka 1, 4, 7, dan 13.
- Sibling : Node yang memiliki parent yang sama, contohnya angka 1 dan angka 6.


C. Konsep Binary Search Tree
Binary Tree memiliki akar atau yang disebut root node dan memiliki 2 sisi cabang tree yaitu tree cabang kiri dan tree cabang kanan.

Tree cabang kiri akan selalu menampung value yang lebih kecil dari value parentnya, sedangkan
tree cabang kanan akan selalu menampung value yang lebih besar dari value parentnya.

Binary Tree memiliki syarat yaitu batas maksimum anak dari node parent adalah 2 child nodes.

Simulasi alur penempatan value di BST (dengan root angka '8' dan inputan angka '4':

1. Cek apakah nilai 4 lebih kecil/besar dari root 8, ternyata lebih kecil maka masuk ke cabang tree kiri.
2. Cek apakah cabang di root 8 sudah ada 2 child nodes? Ya, maka perlu turun cabang.
3. Cek apakah 4 lebih kecil/besar dari 3, ternyata lebih besar maka masuk ke cabang tree kanan.
4. Cek apakah cabang di node 3 sudah ada 2 child nodes? Ya, maka perlu turun cabang.
5. Cek apakah 4 lebih kecil/besar dari 6, ternyata lebih kecil maka masuk ke cabang tree kiri.
6. Cek apakah cabang di node 6 sudah ada 2 child nodes? Tidak/belum, maka value 4 diletakkan di cabang sebelah kiri dari parent node 6.

D. Operasi Binary Search Tree

• find(x), mencari value x di BST.

Alurnya dimulai dari rootnya. Jika value x sama dengan value rootnya, maka sudah temukan. Sedangkan apabila bukan, maka ada 2 kondisi, apabila nilai x lebih kecil dari value node parent maka akan dilakukan rekursif ke cabang sebelah kiri, lalu jika nilai x lebih besar dari value node parent maka akan dilakukan rekursif ke cabang sebelah kanan.

struct node* search (struct node *curr, int X) {

if ( curr == NULL ) return NULL;

// X is found

if ( X == curr->data ) return curr;

// X is located in left sub tree

if ( X  < curr->data ) return search(curr->left, X);

// X is located in right sub tree

return search(curr->right, X);

}

• insert(x), memasukkan value x di BST.

Alurnya dimulai dari rootnya. Menggunakan metode rekursif. Jika value x lebih kecil dari value node maka masukkan x ke cabang sebelah kiri, jika lebih besar dari value node maka masukkan x ke cabang sebelah kanan. Terus ulangi hingga ada parent node yang masih memiliki cabang kurang dari 2 cabang. Jika sudah ditemukan, maka value x akan disambunkan ke parent node dan menjadi child node dari parent node.

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

{ 

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

    if (node == NULL) return new Node(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; 

} 

• remove(x), menghapus value x di BST.

Ada 3 kondisi yang harus dibuat:

1. Node yang dihapus berada di leaf
2. Node yang dihapus memiliki 1 anak cabang
3. Node yang dihapus memiliki 2 anak cabang

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; 
} 

• viewInfix(), melihat value data secara urut.

void viewInfix(Node *root){

 if(root != NULL){
  viewInfix(root->left);
  printf("%d\n",root->value);
  viewInfix(root->right);
 }
}

• viewPrefix(), menampilkan urutan data dari kiri ke kanan mulai dari paling atas

void viewPrefix(Node *root){

 if(root != NULL){

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

  viewPrefix(root->left);

  viewPrefix(root->right);

 }

}

• viewPostfix(), mirip infix tapi ditampilkan data dari bagian kanan pada cabang kiri hingga habis kemudian bergerak ke kanan hingga habis lalu print hasilnya

void viewPostfix(Node*root){
 if(root != NULL){
  viewPostfix(root->left);
  viewPostfix(root->right); 
  printf("%d\n",root->num);
 }
}

Demikian pembahasan dari materi yang saya pelajari. Mohon maaf apabila ada kesalahan dan kekurangan. Terima kasih.

Angelia
2301854492
COMP6048 - CB01

Referensi:
PPT BinusMaya
https://www.geeksforgeeks.org/binary-search-tree-data-structure/
http://dinda-dinho.blogspot.com/2013/07/pengertian-dan-konsep-binary-tree.html
https://www.includehelp.com/data-structure-tutorial/binary-tree-definition-and-its-properties.aspx
https://commons.wikimedia.org/wiki/File:Binary_search_tree_search_4.svg
https://socs.binus.ac.id/2017/05/10/implementasi-delete-pada-binary-search-tree/