AYSKA AULYA
2001100
AWALINDA ZUDAINI
2001099
HABIB RIZKY AL-HAFIZ
2001110
DOSEN PEMBIMBING
INDRA GUNAWAN M.KOM
Disusun Untuk Memenuhi Tugas Pada Mata Kuliah Struktur Data
di Semester 2 Kelas  20T03  STIKOM Tunas Bangsa
ABSTRACK
Binary Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya
Salah satu penerapan teori pohon yang paling berguna dan dipakai yaitu konsep binary search tree dimana konsep ini memberikan struktur data yang memudahkan operasi pencarian, penambahan, dan penghapusan terhadap data. Operasi tersebut lebih efisien dan jauh lebih baik pada konsep ini dibanding sequential search pada senarai berkait dalam waktu eksekusi / run-time. Dari konsep binary search tree ini dikembangkan lagi suatu struktur penyimpanan data yang merupakan modifikasi dari binary search tree tersebut yaitu AVL-Tree dan Splay Tree yang masing-masing mempunyai keunggulan pada kasus tertentu yang sekarang ini sering dijumpai.
Kata Kunci : Binary Tree
PENDAHULUAN
Pendahuluan Teori pohon merupakan salah satu teori yang cukup tua karena sudah dikenal sejak tahun 1857, dimana ketika itu matematikawan Inggris Arthur Cayley menggunakan teori pohon ini untuk menghitung jumlah senyawa kimia.
Teori pohon ini sebenarnya adalah suatu mekanisme penyelesaian suatu masalah dengan menganalogikan permasalahan tersebut kedalam struktur pohon untuk memudahkan pencarian solusi masalah tersebut. Teori pohon ini juga merupakan salah satu penerapan konsep graf. Dimana pohon itu dapat didefinisikan sebagai graf tak-berarah terhubung yang tidak mengandung sirkuit.
Kajian struktur data merupakan kajian yang sangat penting dalam bidang informatika. Dan di zaman sekarang ini yang teknologinya semakin berkembang, dibutuhkan struktur data yang efisien yang dapat meningkatkan kinerja program. Teori pohon ini merupakan teori yang sangat berguna dalam struktur data dimana aplikasi aplikasi dari teori pohon ini dapat dijadikanstruktur penyimpanan data yang sangat baik dalam kasus tertentu yang mana kasus tersebut sudah umum ditemui sekarang ini. Oleh karena itu dalam makalah ini akan dijelaskan beberapa aplikasi teori pohon yang dipakai untuk membentuk suatu struktur penyimpanan data yang efisien.
PEMBAHASAN
Jika kita memperhatikan setiap simpul dalam pohon biner, kita bisa menyusun struktur data yang tepat dari simpul-simpul tersebut. Kita dapat melihat bahwa dalam setiap simpul selalu berisi dua buah pointer untuk menunjuk ke cabang kiri dan cabang kanan, dan informasi yang akan disimpan dalamsimpul tersebut. Dengan memperhatikan hal ini, simpul dalam pohon biner disajikan sebagai berikut:
KIRI
INFO
KANAN
Gambar
Sesuai dengan gambar, maka deklarasi list yang sesuai adalah:
typedef char TypeInfo;
typedef struct Simpul *Tree;
struct Simpul { TypeInfo Info;
 tree Kiri, /* cabang kiri */Kanan;
/* cabang kanan */ };
BINARY SEARCH TREE
Binary Tree ini memiliki sifat dimana semua left child harus lebih kecil dari pada right child dan parentnya. Semua right child juga harus lebih besar dari left child serta parentnya. Binary search tree dibuat untuk mengatasi kelemahan pada binary tree biasa, yaitu kesulitan dalam searching / pendarian node tertentu dalam binary tree. Pada dasarnya operasi dalam Binary Search Tree sama dengan Binary Tree biasa, kecuali pada operasi insert, update, dan delete.
Bayangkan apabila kita ingin mencari sebuah data pada sebuah senarai berkait, tentunya tidak ada cara selain mencarinya secara sekuensial dari pointer elemen pertama senarai. Bandingkan jika kita melakukan pencarian di tabel kontigu dan dengan pencarian biner (binary search), tentunya pencarian akan lebih cepat. Dan sekarang bayangkan jika kita ingin melakukan operasi penambahan dan penghapusan elemen senarai.Operasi tersebut akan lebih lambat pada tabel kontigu daripada senarai berkait. Hal ini disebabkan karena operasi penambahan dan penghapusan pada tabel kontigu memerlukan pemindahan banyak entri data setiap saat, dibandingkan dengan senarai berkait yang hanya membutuhkan sedikit permainan pointer.
Dari permasalahan diatas tentunya dapat kita simpulkan bahwa alangkah baiknya jika kita dapat melakukan operasi pencarian dengan kecepatan eksekusi tinggi (seperti pada tabel kontigu dan pencarian biner) dan operasi penambahan dan penghapusan dengan kecepatanek sekusi tinggi (seperti pada senarai berkait).Disinilah keunggulan Binary Search Tree akansangat berguna,dimana Binary Search Treedapat menjadi solusi permasalahan tersebut karena pencarian serta penambahan dan penghapusan elemennya memiliki kecepatan eksekusi yang tinggi. Operasi pencarian, penambahan, dan penghapusan pada Binary Search Tree memiliki run-time O (log n).
Misalkan kita memiliki int arr[] = {70, 60, 30, 50, 40,20}, data para int arr harus diurutkan terlebih dahulu menggunakan teknik sorting seperti bubble sort. Sehingga array kita akan menjadi int arr[] = {20,30,40,50,60,70}. Apabila angka yang dicari adalah angka 40, berikut gambaran dari implementasi BinarySearch:
1stCycle:
(20,30,40,50,60,70)
LOW=0
HIGH=N
MID=(LOW+HIGH)/3
(arr[MID]==40)
(20,30,40,50,60,70)(50==40)//FALSE
HIGH = MID-1
*Array di mulai dari index ke 0, maka index ke 3 berisi nilai 50.
2ndCycle:
(20,30,40,50,60,70)
MID = (LOW + HIGH)/2= (0+2)/2=1
(arr[MID]==40)
(20,30,40,50,60,70)
(30==40)//FALSE
LOW = MID+1
3rdCycle:
(20,30,40,50,60,70)
MID=(LOW+HIGH)/2=(2+2)/2+2
(arr[MID]==40)
(20,30,40,50,60,70)
(40==40) // TRUE
Jika data ditemukan, maka program akan keluar dari looping. Jika kita ingin menampilkan index dari data yang dicari, kita tinggal menyimpan index dari array tersebut dan menampilkan nya.
Berikut implementasi dari Binary Search menggunakan Bahasa C:
Binary Search Tree adalah sebuah pohon biner yang mempunyai properti tambahan. Properti ini adalah :
Semua elemen pada upapohon (subpohon) kiri nilainya lebih kecil atau sama dengan nilai akar.
Semua elemen pada upapohon kanan nilainya lebih besar dari nilai akar.
Upa pohon kiri dan kanan merupakan Binary Search Tree.
Terdapat 3 operasi yang sangat mendasar dan juga sangat penting pada binary search tree yaitu operasi pencarian, penambahan, dan penghapusan elemen. Ketiga operasi tersebut merupakan operasi yang sangat mendasar yang harus ada pada setiap struktur penyimpanan data.
Untuk melakukan operasi pencarian pada Binary Search Tree, pertama-tama kita bandingkan dahulu kunci data yang ingin kita cari dengan kunci dari data akar, jika tidak cocok maka cari pada upapohon kiri atau kanan sampai kunci data yang ingin dicari cocok.Berikut sketsa kasar algoritma operasi pencarian pada Binary Search Tree : Algoritma Cari Simpul (kunci K, pohon P) Jika pohon P kosong kembalikan nilai NULL (tak terdefinisi). Jika kunci K cocok dengan kunci akar t maka kembalikan simpul P. Jika kunci K > kunci akar simpul P maka kembalikan nilai dari Cari Simpul (kunci K, upapohon kanan (P) ) Jika kunci K <= kunci akar simpul P maka kembalikan nilai dari Cari Simpul (kunci K, upapohon kiri(P).
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
