Langsung ke konten utama

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/
Label:

Komentar

Posting Komentar

Postingan populer dari blog ini

Struktur Data: Hash Table dan Binary Trees

Struktur Data: Hash Table dan Binary Trees Keduanya merupakan jenis-jenis struktur data yang dapat dibuat. Lalu, apa itu hash table dan binary trees ? 1. Hashing dan Hash Table Hash table merupakan salah satu struktur data yang digunakan dalam penyimpanan data sementara. Tujuan dari hash table adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan. Hash table menggunakan suatu teknik penyimpanan sehingga waktu yang dibutuhkan untuk penambahan data ( insertions ), penghapusan data ( deletions ), dan pencarian data ( searching ) relatif sama dibanding struktur data atau algoritma yang lain. Hash table menggunakan memori penyimpanan utama berbentuk array dengan tambahan algoritma untuk mempercepat pemrosesan data. Pada intinya hash table merupakan penyimpanan data menggunakan key value yang didapat dari nilai data itu sendiri. Dengan key value tersebut didapat hash value . Jadi hash function merupakan suatu fungsi sederhana untuk mendapatkan
2 komentar
Baca selengkapnya

Struktur Data: Stack dan Queue

Struktur Data: Stack dan Queue Selain linked list , di dalam struktur data juga terdapat teknik lain. Antaranya adalah stack dan queue . Lalu, apa itu sebenarnya stack dan queue ? 1. Stack Stack , atau dalam Bahasa Indonesianya disebut tumpukan , merupakan salah satu teknik struktur data yang bersifat LIFO ( last in first out ). Data yang terakhir masuk ke stack merupakan data yang akan keluar pertama (namanya juga tumpukan). Misalnya terdapat data A, B, C, D, E, dan F. Jika urutan data yang masuk adalah A-B-C-D-E-F, maka untuk mengeluarkan data C, harus dilakukan pengeluaran data F-E-D terlebih dahulu. Algoritma Stack Seperti contoh yang telah dibahas di atas, algoritma dalam stack dilakukan dengan menguji apakah stack sudah penuh jika sedang memasukkan data ( push ). Jika sudah, maka data baru tidak dapat masuk. Jika belum, maka data yang terakhir dimasukkan merupakan data paling atas dari stack tersebut. Untuk mengeluarkan data ( pop ), maka dilakukan uji apaka
2 komentar
Baca selengkapnya

Struktur Data: AVL Tree

Struktur Data: AVL Tree Apa itu AVL Tree? AVL Tree merupakan sebuah BST yang bisa menyeimbangkan dirinya sendiri antara kanan dan kiri. Seimbang di sini maksudnya perbedaan panjang antara kaki kanan dan kaki kiri tree nya tidak lebih dari 1. Contoh gambarnya seperti ini: Nah bisa diliat dari contoh gambar di atas kalo panjang kaki kiri dan kanan nya sama (sejajar). Itu yang disebut AVL Tree. Nah kalo gambar yang itu bukan AVL, kenapa? Karena kaki kiri nya kepanjangan! Terus kalo gitu gimana caranya AVL menyeimbangkan dirinya sendiri? Hayo gimana, kepo ya? Jadi gini, si AVL itu bisa nyeimbangin dirinya sendiri dengan cara melakukan perputaran node di kaki yang terpanjang. Perputarannya sendiri terdiri dari 2 jenis, yaitu single rotation dan heavy double rotation . Single Rotation Single rotation akan dilakukan ketika kaki yang terpanjangnya memiliki arah yang lurus. Maksudnya gimana tuh? Jadi gini, liat gambar di bawah ini: Bisa diliat dari gambar di atas, ka
Posting Komentar
Baca selengkapnya