Binary Search Tree | Kode Kampus

Apa itu Binary Search Tree?

Binary Search Tree adalah struktur data pohon di mana setiap node memiliki paling banyak dua anak dan mengikuti sifat binary search tree: semua node di subtree kiri memiliki nilai lebih kecil dari nilai node tersebut, dan semua node di subtree kanan memiliki nilai lebih besar dari nilai node tersebut. Hal ini membuat operasi insert, search, dan delete efisien.

Notes

Dalam binary search tree, semua node di subtree kiri dari suatu node memiliki nilai lebih kecil dari nilai node tersebut, dan semua node di subtree kanan memiliki nilai lebih besar dari nilai node tersebut.
Binary search tree tidak selalu seimbang, dan pohon yang tidak seimbang dapat mengakibatkan kinerja operasinya yang buruk.
Sebuah binary search tree yang seimbang memiliki tinggi O(log n), di mana n adalah jumlah node di dalam pohon.
Kompleksitas waktu dari operasi dasar pada binary search tree, seperti pencarian, penyisipan, dan penghapusan, adalah O(log n) dalam kasus rata-rata dan O(n) dalam kasus terburuk, di mana n adalah jumlah node di dalam pohon.

Ilustrasi

Berikut merupakan visualisasi dari Binary Search Tree, dimana untuk setiap node, semua angka di bagian bawah kiri pasti lebih rendah dan semua angka di bagian kanan pasti lebih tinggi.

BST Search

Proses pencarian data menjadi efisien karena kita tinggal mengikuti aturan BST (kiri lebih rendah, kanan lebih tinggi).

Contoh dalam pencarian angka 9, kita lihat angka 9 lebih rendah dari angka 10, maka kita pergi ke kiri.

Angka 9 lebih tinggi dari angka 8, maka kita pergi ke kanan.

Akhirnya kita menemukan angka 9!

BST Insert

Proses insert juga sama yaitu tinggal mengikut aturan BST.

Contoh kita ingin memasukkan angka 7, kita cek bahwa 7 lebih rendah dari 10 maka kita ke kiri.

7 lebih rendah lagi dari 8, maka kita ke kiri lagi.

7 lebih tinggi dari 2 dan tidak ada node di sebelah kanan, maka kita tinggal masukkan saja angka 7 tersebut.

BST Delete

CASE I (No Child Node)

Jika tidak ada node dibawah yang kita mau delete, maka kita tinggal menghapus seperti biasa.

CASE II (One Child Node)

Jika kita mempunyai 1 node dibawah yang kita mau delete, maka kita taruh node yang dibawah keatas (copy), dan kita delete original node.

Angka 7 yang di node merah adalah node copy dari bawah (yang penting valuenya sama), dan node bawah sekarang adalah yang ingin kita delete.

Node bawah akan di delete karena valuenya sudah di copy keatas.

CASE III (Two Child Node)

Jika kita mempunyai dua node dibawah, maka kita perlu mencari yang namanya inorder successor (node sebelah kanan yang paling kiri). Karena berdasarkan aturan BST, node sebelah kanan lebih besar, dan kita perlu mencari yang terkiri karena itu yang terkecil di bagian sebelah kanan.

Angka 9 terpilih karena tidak ada node sebelah kiri lagi di bagian kanan.

Kita tukar posisi 9 dan 8, dan kita delete angka 8 dibawah.

Implementasi

#include <stdio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node *left;
    struct node *right;
};

struct node *createNode(int data) {
    struct node *newNode = (struct node *) malloc(sizeof(struct node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

struct node *insert(struct node *root, int data) {
    if (root == NULL) {
        return createNode(data);
    } else if (data < root->data) {
        root->left = insert(root->left, data);
    } else if (data > root->data) {
        root->right = insert(root->right, data);
    }
    return root;
}

struct node *findMin(struct node *root) {
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

struct node *delete(struct node *root, int data) {
    if (root == NULL) {
        return root;
    } else if (data < root->data) {
        root->left = delete(root->left, data);
    } else if (data > root->data) {
        root->right = delete(root->right, data);
    } else {
        // Case 1: No child
        if (root->left == NULL && root->right == NULL) {
            free(root);
            root = NULL;
        }
        // Case 2: One child
        else if (root->left == NULL) {
            struct node *temp = root;
            root = root->right;
            free(temp);
        } else if (root->right == NULL) {
            struct node *temp = root;
            root = root->left;
            free(temp);
        }
        // Case 3: Two children
        else {
            struct node *temp = findMin(root->right);
            root->data = temp->data;
            root->right = delete(root->right, temp->data);
        }
    }
    return root;
}

struct node *search(struct node *root, int data) {
    if (root == NULL || root->data == data) {
        return root;
    } else if (data < root->data) {
        return search(root->left, data);
    } else {
        return search(root->right, data);
    }
}

void inorder(struct node *root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

int main() {
    struct node *root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);
    printf("Inorder traversal of the binary search tree: ");
    inorder(root);
    printf("\n");

    root = delete(root, 40);

    printf("Inorder traversal of the binary search tree after deleting 20: ");
    inorder(root);
    printf("\n");

    if (search(root, 60) != NULL) {
        printf("60 found in the binary search tree.\n");
    } else {
        printf("60 not found in the binary search tree.\n");
    }

    if (search(root, 40) != NULL) {
        printf("40 found in the binary search tree.\n");
    } else {
        printf("40 not found in the binary search tree.\n");
    }
    return 0;
}

Output

Inorder traversal of the binary search tree: 20 30 40 50 60 70 80
Inorder traversal of the binary search tree after deleting 20: 20 30 50 60 70 80
60 found in the binary search tree.
40 not found in the binary search tree.