Binary Search Tree

 Pada pertemuan kali ini saya belajar tentang Binary Search Tree. Binary Search Tree adalah salah satu jenis data struktur yang mendukung pencarian lebih cepat, sorting lebih cepat, dan insert and delete lebih mudah.

Binary Search Tree adalah binary tree yang sudah di sort atau diurutkan

Bagian sub kiri tree mengandung element yang lebih kecil daripada yang tersimpan di variabel x
Bagian sub kanan tree mengandung element yang lebih besar daripada yang tersimpan di variabel x

3 operasi dalam binary search adalah
1. Find key(x)
2. Insert key (x)
3. Remove key (x)

1. Search/find operation
Anggaplah kata kunci nya adalah variabel x:
1. Kita mulai dari akar
2. Jika root berisi X maka pencarian berhasil dihentikan.
3. Jika X kurang dari kunci root, maka cari secara rekursif pada sub pohon kiri, jika tidak cari secara rekursif pada sub pohon kanan.

// C function to search a given key in a given BST

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

}




2. Insertion Operation (pakai fungsi rekursif)

Anggaplah kata kunci nya adalah variabel x:

1. Mulailah dari akar 2. Jika X kurang dari kunci simpul maka masukkan X ke sub pohon kiri, jika tidak masukkan X ke sub pohon kanan

3. Ulangi sampai kami menemukan simpul kosong untuk meletakkan X

(X akan selalu menjadi daun baru)

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;

}

3. Deletion/Remove Operation

Ada 3 kasus yang harus dipertimbangkan:

a) Jika kunci ada di daun, hapus saja simpul itu. b) Jika kunci ada di simpul yang memiliki satu anak, hapus simpul itu dan sambungkan anaknya ke induknya c) Jika kunci ada di simpul yang memiliki dua anak, temukan anak paling kanan dari sub pohon

kirinya (simpul P), ganti kuncinya dengan kunci P dan hapus P secara rekursif. (atau secara

bergantian Anda dapat memilih anak paling kiri dari sub pohon kanannya)

/* Given a binary search tree and a key, this function deletes the key

   and returns the new root */

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;

}



Sumber: https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/
Sumber: https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/