Cara Implementasi Binary Search and Tree Golang

Pengertian Dasar

Struktur data Binary Search and Tree adalah pola yang digunakan untuk pencarian berbasis Tree. Sebelum kamu lebih lanjut mengenal Binary Search Tree biasa disebut BST, kamu perlu terlebih dahulu paham terhatap konsep Tree. Tree (pohon) adalah salah satu bentuk struktur data yang menggambarkan hubungan hierarki antar elemen-elemennya (seperti relasi one to many). Sebuah node dalam tree biasanya bisa memiliki beberapa node lagi sebagai percabangan atas dirinya.

Lalu ada lagi namanya Binary Tree, apa lagi tuh? Konsep sama saja dengan Tree, hanya saja kita akan mengambil sifat bilangan biner yang selalu bernilai 1 atau 0 (2 pilihan). Berarti, Binary Tree adalah tree yang hanya dapat mempunyai maksimal 2 percabangan saja.

Jadi, Binary Search Tree merupakan tree yang terurut (ordered Binary Tree) yang memiliki kelebihan bila dibanding dengan struktur data lain. Diantaranya adalah proses pengurutan (sorting) dan pencarian (searching) dapat dilakukan bila data sudah tersusun dalam struktur data BST. Pengurutan dapat dilakukan bila BST ditelusuri (traversed) menggunakan metode in-order. Detail dari proses penelusuran ini akan dibahas pada pertemuan selanjutnya. Data yang telah tersusun dalam struktur data BST juga dapat dicari dengan mudah dan memiliki rata-rata kompleksitas sebesar O(log n), namun membutuhkan waktu sebesar O(n) pada kondisi terjelek dimana BST tidak berimbang dan membentuk seperti linked list.

Aturan Binary Search Tree

Struktur data BST memiliki beberapa aturan sehingga bisa dikatakan seperti itu, berikut ini aturannya:

• Semua data dibagian kiri sub-tree dari node t selalu lebih kecil dari data dalam node t itu sendiri.
• Semua data dibagian kanan sub-tree dari node t selalu lebih besar atau sama dengan data dalam node t.

BST berikut adalah sebuah BST berukuran 9 dengan kedalaman 3 dengan node daun (leaf) adalah 1, 4, 7 dan 13.

Implementasi Kode

10
8
0
9
20
15
25
value  10
value  20
value  25
false

Penjelasan

Lihat dari implementasi diatas, kita tahu konsep Binary Search Tree, itu setelah kita memanggil func exists, dilihat hasil cetaknya memberikan informasi bahwa saat melakukan cetak kita akan menelusuri tree tersebut berdasarkan value dan kondisi. Pada contoh kode diatas, kita akan mencari nilai 26 dan kita cari di data tidak tersedia karena memang nilai 26 tidak di input atau ditambahkan ke dalam Tree.

Coba kita lihat cetak penelusurannya, karena nilai 26 itu lebih dari 10 dan lebih dari 20 dan terakhir lebih dari 25 maka, penelusurannya pun berada pada 3 kali loop sampai menentukan titik tidak ditemukan.