Binary Search Tree

Nama : Raymon Elnardi
Nim   : 2310908620
Kelas : LL01

       Hari ini akan membahas tentang Binary Search Tree atau disingkat BST. BST adalah sebuah data structure yang non-linear. BST memiliki sifat dimana setiap subtree yang berada di sebelah kiri node akan bernilai lebih kecil daripada node itu sendiri, sedangkan subtree yang berada di sebelah kanan node akan bernilai lebih besar daripada node itu. tapi bagaimana jika bernilai sama dengan node ? BST sifatnya adalah mensortir nilai sehingga nilai yang bernilai sama akan diabaikan perintahnya. BST memiliki 3 buah fingsi umum yaitu : Find, Insert, dan Delete.
Tetapi pertama-tama kita perlu struct untuk node tersebut.

====================================================================

||struct node

||{

||    int key;

||    struct node *left, *right;

||};

=====================================================================

       Codingan ini digunakan untuk wadah node tersebut, key untuk menyimpan value x, left untuk menghubungkan subtree kiri, right untuk menghubungkan subtree kanan.

       *Find(x)

       fungsi find bertujuan untuk mencari nilai x.
ada pula langkah-langkah sebagai berikut :
- Fungsi ini akan selalu mulai dari root
- jika berhasil menemukan nilai x, maka fungsi berhasil dijalankan
- jika nilai x lebih kecil dari nilai root, maka akan dicari menggunakan rekursif di subtree kiri, jika sebaliknya maka rekursif ke subtree kanan
- jika tidak ditemukan maka  yang akan dikembalikan

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

}

       *Insert(x)
       Insert adalah fungsi yang berguna untuk menambahkan node baru ke dalam BST.
ada pula langkah-langkah sebagai berikut :
- Fungsi ini akan selalu mulai dari root
- jika nilai x lebih kecil dari nilai root, maka x akan dimasukan x ke subtree kiri, jika sebaliknya maka dimasukkan ke subtree kanan
- ulangi hingga menemukan node kosong (x akan selalu menjadi leaf baru)

// A utility function to create a new BST node

struct node *newNode(int item)

{

    struct node *temp =  (struct node *)malloc(sizeof(struct node));

    temp->key = item;

    temp->left = temp->right = NULL;

    return temp;

}

   

// A utility function to do inorder traversal of BST

void inorder(struct node *root)

{

    if (root != NULL)

    {

        inorder(root->left);

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

        inorder(root->right);

    }

}

   

/* A utility function to insert a new node with given key in BST */

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;

}

Waktu kompleksitas (search dan insert)  : Worst case O(h) (h adalah height dari tree), Best case O(n) (n adalah jumlah node)


       *Delete(x)
       Delete adalah fungsi untuk menghapus node dengan nilai x
fungsi delete sendiri dapat terbilang kompleks, delete menggunakan konsep search tetapi setelah itu terjadi beberap hal, berikut adalah beberapa kasus yang mungkin terjadi jika menggunakan delete :
- Jika node yang dihapus adalah leaf, maka leaf akan dihapus dan berhenti
- Jika node adalah parent yang memiliki 2 subtree, maka parent akan dihapus dan posisi parent akan digantikan dengan subtree kiri yang memiliki nilai node terbesar, dan jika yang dipindahkan bukan leaf, maka subtree dari node yang diambil tersebut akan dihubungkan dengan node yang berada diatasnya
- Jika node adalah parent yang hanya memiliki subtree kiri, maka parent akan dihapus dan posisi parent akan digantikan dengan subtree kiri yang memiliki nilai node terbesar, dan jika yang dipindahkan bukan leaf, maka subtree dari node yang diambil tersebut akan dihubungkan dengan node yang berada diatasnya
- Jika node adalah parent yang hanya memiliki subtree kanan, maka parent akan dihapus dan diambil node kanan yang terdekat, dan jika yang dipindahkan bukan leaf, maka subtree dari node yang diambil tersebut akan dihubungkan dengan node yang berada diatasnya



Reference : https://www.geeksforgeeks.org/