Binary Tree

Binary Search Tree

Binary Search Tree adalah sebuah konsep penyimpanan data, dimana data disimpan dalam bentuk tree yang setiap node dapat memiliki anak maksimal 2 node. Selain itu, terdapat juga aturan dimana anak kiri dari parent selalu memiliki nilai lebih kecil dari nilai parent dan anak kanan selalu memiliki nilai lebih besar dari parent. Pada artikel ini, penulis akan membahas bagaimana cara mengimplementasikan binary search tree di dalam Bahasa C.

Pertama, kita harus mempersiapkan struct yang melambangkan setiap node. Untuk contoh sederhana, struct yang dibuat disini hanya berisi 1 buah integer. Berikut adalah contoh structnya :

Setelah struct dibuat, kita akan membuat sebuah function yang digunakan untuk membuat node baru, seperti di bawah ini :

fungsi di atas berguna untuk membuat node baru. Jadi setiap createNode dipanggil, contoh createNode(50), createNode(70), maka akan jadi seperti ini :

setelah fungsi di atas sudah siap, berikutnya kita tinggal membuat fungsi insert/push menggunakan single pointer seperti di bawah ini :

Berikut adalah penjelasan dari code di atas :

1. Pada if pertama, program akan melakukan cek pada root. Jika root bernilai NULL, artinya tree belum pernah terbentuk sama sekali. Karena itu kita tinggal melakukan malloc/ pemesanan memori pada root
2. Pada else if kedua, program melakukan pengecekkan terhadap nilai baru yang mau diinsert. Jika nilai baru tersebut lebih kecil daripada node sekarang dan anak kiri dari node sekarang sedang kosong, maka program akan melakukan malloc pada anak kiri tersebut dan mengarahkan pointer parent kepada node yang sekarang.
3. Pada else if ketiga, program akan melakukan pengecekkan seperti pada point 2. Hanya saja jika nilai baru tersebut lebih besar dari node sekarang dan anak kanan dari node sekarang sedang kosong, maka program akan melakukan malloc pada anak kanan tersebut dan mengarahkan pointer parent kepada node sekarang.
4. Pada else if keempat, program akan jalan jika nilai baru lebih kecil dari node sekarang, tetapi anak kiri dari node tersebut tidak kosong. Maka program akan melakukan rekursif, memanggil fungsi push kembali dengan parameter nodel->left, yang berarti node sekarang dipindahkan ke anak kiri dan nilai a yang mau diinput. Sehingga pada tahap ini, suatu saat program akan menemui kondisi dimana anak kiri dari node sekarang sedang kosong.
5. Pada else yang terakhir, program melakukan hal yang sama seperti point 4, hanya saja nilai yang dicek kondisinya harus lebih besar dari nilai node sekarang.

Jika kita ingin menggunakan double pointer, maka fungsi insert / push, akan jadi seperti ini :

Perbedaan cara memanggil fungsi single dan double pointer adalah seperti ini :

Contoh single : push(root,50);

Contoh double : push2(&root,50);

Jika dilihat dari code di atas, code double pointer terlihat lebih pendek karena dengan menggunakan double pointer, kita bisa melakukan passing by address. Sehingga ketika kita melakukan malloc atau memanggil newNode pada fungsi push2, maka root yang aslinya akan kena malloc juga. Berbeda dengan single pointer, jika kita melakukan node = newNode(a), maka root yang asli tidak akan ikut kena malloc, Karena ini merupakan passing by value.

Lalu ada juga delete pada Binary Search Tree, berikut cara menghapus sebuah node di dalam Binary Search Tree.

Pada tahap pertama, saya akan membuat sebuah fungsi search, seperti di bawah ini :

Fungsi di atas berfungsi untuk mencari sebuah node dengan nilai tertentu. Kemudian fungsi ini akan mengembalikan nilai berupa node yang ditemukan atau NULL jika nilai yang dicari tidak ditemukan.

Contoh pada gambar tree di atas, jika kita mencari angka 14, makan fungsi search akan mengembalikan node (struct tree*). Setelah fungsi search dibuat, berikutnya kita membuat fungsi pop seperti berikut ini:

Pada fungsi ini, kita memanggil fungsi search yang sudah dibuat sebelumnya. Artinya kita sudah mendapatkan lokasi dimana node tersebut. Setelah itu kita tinggal melakukan cek pada node tersebut. Jika node tidak NULL, maka kita akan menghapus node tersebut dengan fungsi rekursif. Hal ini diperlukan untuk mencari pengganti dari node yang sudah dihapus.

Berikut adalah tahapan dalam membuat fungsi popRecursive.

1. Pertama hal yang harus di cek adalah kondisi dimana sebuah node tidak memiliki child sama sekali. Node seperti ini bisa terjadi Karena 2 kemungkinan, yaitu node tersebut adalah root yang belum memiliki anak atau node tersebut adalah node yang berada di paling bawah dari sebuah tree. Berikut adalah code nya :
   
   Pada code di atas, kita melakukan cek jika node tersebut adalah root, maka kita tinggal hapus saja, tetapi jika node tersebut bukan root, kita harus setting anak kiri / anak kanan dari parentnya.

2. Kondisi kedua adalah jika node yang mau dihapus, tidak memiliki anak kanan (hanya ada anak kirinya saja).
   

3. Kondisi ketiga adalah jika node yang mau dihapus tidak memiliki anak kiri (hanya ada anak kanannya saja).
   

4. Kondisi terakhir adalah jika node memiliki anak kiri dan kanan, maka node akan digantikan oleh anak kiri yang memiliki nilai paling besar, kemudian node yang menggantikan akan dihapus lagi, sehingga kita perlu memanggil popRecursive sekali lagi. Berikut adalah codenya :
   

Dilihat dari coding di atas, kita menjumpai banyak code seperti ini :

code di atas berarti kita mengecek apakah node ini merupakan anak kiri atau anak kanan dari parentnya. Jika node tersebut merupakan anak kiri, maka kita perlu mengatur pointer left dari parent, jika node yang mau dihapus merupakan anak kanan, maka kita perlu mengatur pointer right dari parent.

Semua code di atas berlaku untuk tree yang memiliki parent. Jika kita menghilangkan node parent, artinya tree hanya memiliki left dan right, maka kita tidak perlu mengatur hubungan parentnya.