Dalam penambahan elemen pada Binary Search Tree, terdapat 2 kasus yang harus kita perhatikan yaitu penambahan ke pohon kosong dan penambahan ke pohon pencarian biner (Binary Search Tree) yang sudah terisi. Penambahan ke pohon kosong tentunya cukup mudah, sedangkan untuk penambahan ke Binary Search Tree yang sudah terisi maka kita harus membandingkannya dengan kunci dari akar pohon yang bersangkutan. Jika kuncinya lebih kecil maka tambahkan simpul baru ke upapohon kiri, jika lebih besar maka tambahkan ke upapohon kanan, dan jika kunci nya sama atau simpul dengan kunci yang ingin ditambahkan sudah ada, maka tidak akan melakukan apa-apa. Berikut sketsa kasar penambahan elemen pada Binary Search Tree :
Algoritma Insert (kunci K, pohon P) 7
1. Jika pohon P kosong maka kembalikan pohon baru dengan kunci akar = K
2. Jika kunci akar P = K, kembalikan P (tanpa diubah)
3. Jika kunci K > kunci akar P,maka Insert (kunci K, upapohon kanan(P) )
4. Jika kunci K < kunci akar P, maka Insert (kunci K, upapohon kiri(P) )
Penghapusan elemen pada Binary Search Tree merupakan operasi yang paling kompleks dari ketiga operasi ini. Dalam penghapusan elemen ini ada 3 kasus yang harus kita perhatikan, antara lain :
1. Menghapus daun : menghapus simpul yang tidak mempunyai upapohon.
2. Menghapus simpul yang mempunyai sebuah upapohon kiri/kanan : hapus dan gantikan dengan upapohonnya
3. Menghapus simpul yang mempunyai 2 upapohon : timpa simpul yang ingin dihapus dengan simpul yang mempunyai kunci terbesar pada upapohon kiri
KESIMPULAN
Berdasarkan hal-hal diatas maka dapat diambil kesimpulan bahwa penerapan teori pohon sangatlah berguna dalam kajian struktur data dimana dengan teori pohon itu kita bisa mendapatkan struktur penyimpanan data alternatif yang relatif lebih baik dan efisien daripada struktur penyimpanan data lainnya, seperti representasi senarai berkait dan tabel kontigu misalnya. Terbukti bahwa representasi data dengan binary search tree jauh lebih baik daripada representasi data dengan tabel kontigu ataupun senarai berkait. Dan juga dapat kita tarik kesimpulan bahwa binary search tree sangat fleksibel dimana konsepnya ini masih dapat dikembangkan untuk menyelesaikan suatu permasalahan baru yang sekarang ini sudah umum ditemui.
DAFTAR REFERENSI
Munir, Rinaldi (2005) Diktat Kuliah IF2153 Matematika Diskrit. Program Studi Teknik Informatika, Institute Teknologi Bandung.
Liem, Inggriani (2005) Diktat Kuliah IF2182 Algoritma dan Struktur Data Program Studi Teknik Informatika Institute Teknologi Bandung.
https://id.wikipedia.org/wiki/Algoritme_pencarian_biner
tanggal akses 12 Juni 2021 Pukul 13.00 WIB
https://socs.binus.ac.id/2019/12/26/binary-search/
tanggal akses 12 Juni 2021 Pukul 14.00 WIB
https://socs.binus.ac.id/2019/12/26/binary-search/
tanggal akses 12 Juni 2021 Pukul 16.00 WIB
