Struktur Data: Binary Search Tree

Struktur Data: Binary Search Tree

Apa itu binary search tree (BST)? BST adalah struktur data pohon biner berbasis node yang memiliki beberapa ciri. Ciri-ciri dari BST adalah:

• Nilai node yang lebih rendah selalu berada di sebelah kiri subtree.
• Nilai node yang lebih tinggi selalu berada di sebelah kanan subtree.
• Setiap subtree juga merupakan sebuah BST.

Gambar 1 - Contoh BST

Kenapa harus membedakan kiri dan kanan sesuai besaran nilainya? Tujuannya untuk memberikan efisiensi terhadap proses searching (pencarian). Kalau struktur data tree sudah tersusun rapi sesuai aturan mainnya, proses search akan lebih cepat.

Penelusuran BST

Penelusuran data BST dapat dilakukan dengan 3 cara, yaitu:

1. PreOrder. Cetak data, telusur ke kiri, telusur ke kanan.
2. InOrder. Telusur ke kiri, cetak data, telusur ke kanan.
3. PostOrder. Telusur ke kiri, telusur ke kanan, cetak data.

Sebelum itu, pertama-tama harus dipersiapkan dahulu struct yang melambangkan setiap node. Untuk contoh sederhana, struct yang dibuat disini hanya berisi 1 buah integer.

struct data {
    int angka;
    data *left, *right;
} *root;

Lalu setelah itu, persiapkan juga fungsi untuk menambahkan data pada BST yang akan dibuat.

void push (data **current, int angka) {
    if (*current == NULL) {
        *current = (struct data*) malloc (sizeof (data));
        *current->angka = angka;
        *current->left = *current->right = NULL;
    } else if (angka < *current->angka) {
         push (& *current->left, angka);
    } else if (angka >= *current->angka) {
        push (& *current->right, angka);
    }
}

Oh iya untuk menggunakan malloc, jangan lupa untuk menambahkan header stdlib.h di atas kodingan ya.

Selanjutnya, buat fungsi masing-masing untuk PreOrder, InOrder, dan PostOrder. Jangan lupa juga untuk membuat fungsi search untuk melakukan pencarian data nantinya.

void preOrder (data **current) {
    if (*current != NULL) {
        printf ("%d -> ", *current->angka);
        preOrder (& *current->left);
        preOrder (& *current->right);
    }
}

void inOrder (data **current) {
    if (*current != NULL) {
        inOrder (& *current->left);
        printf ("%d -> ", *current->angka);
        inOrder (& *current->right);
    }
}

void postOrder (data **current) {
    if (*current != NULL) {
        postOrder (& *current->left);
        postOrder (& *current->right);
        printf ("%d -> ", *current->angka);
    }
}

void search (data **current, int angka) {
    if(*current != NULL) {
        if(angka < *current->angka) {
            search (& *current->left, angka);
        } else if (angka > *current->angka) {
            search (& *current->right, angka);
        } else {
            printf ("Angka ditemukan: %d", *current->angka);
        }
    } else {
        printf ("Angka tidak ditemukan!");
    }
}

Setelah semua fungsinya dibuat, maka sekarang bisa dijalankan main nya.

int main (void) {
    push (&root, 11);
    push (&root, 22);
    push (&root, 13);
    push (&root, 15);
    push (&root, 9);
    inOrder (&root);
    printf ("\n");
    preOrder (&root);
    printf ("\n");
    postOrder (&root);
    printf ("\n");
    search (&root,91);
    getchar ();
}

Referensi

• https://www.geeksforgeeks.org/binary-search-tree-data-structure/
• https://socs.binus.ac.id/2017/05/10/implementasi-insert-pada-binary-search-tree-dengan-single-dan-double-pointer/
• https://www.mahirkoding.com/struktur-data-binary-search-tree-bst/