Binary Tree atau Struktur Data seperti pohon

Nama                       : Dikdik Nawa Cendekia Agung

NPM                         : 23552011240

Kelas/Semester     : 223PD /Semester 1 (ganjil)

Binary Tree

Sebuah Binary Tree adalah struktur data yang terdiri dari simpul-simpul yang terhubung secara hierarkis. Setiap simpul memiliki maksimum dua anak, yaitu anak kiri dan anak kanan. Konsepnya sederhana, tapi penggunaannya sangat luas. Binary Tree digunakan untuk memodelkan hubungan hierarkis, seperti struktur organisasi perusahaan.

Namun bagaimana caranya Binary Tree bekerja? operasi-operasi apa yang dapat kita lakukan? dan apa keuntungan menggunakan struktur data ini?

Binary tree adalah struktur data yang terdiri dari simpul-simpul yang saling terhubung melalui sisi-sisi yang disebut sebagai "edge". Setiap simpul dalam binary tree dapat memiliki maksimum dua anak, yaitu anak kiri dan anak kanan. Simpul yang tidak memiliki anak disebut sebagai "daun".

Binary tree sering digambarkan secara visual dengan menggunakan diagram pohon, di mana simpul-simpulnya direpresentasikan oleh lingkaran dan sisi-sisinya direpresentasikan oleh garis-garis yang menghubungkan simpul-simpul tersebut. Dalam binary tree, setiap simpul memiliki satu simpul "induk" yang terhubung langsung kepadanya, kecuali simpul akar yang tidak memiliki induk.

Jenis-jenis Binary Tree

Terdapat beberapa jenis binary tree yang dapat kita temui, di antaranya adalah complete binary tree, full binary tree, perfect binary tree, dan balanced binary tree. Mari kita bahas masing-masing jenis ini secara singkat.

1. Complete Binary Tree: Binary tree di mana semua tingkat, kecuali mungkin tingkat terakhir, terisi penuh dengan simpul-simpul. Jika ada simpul yang tidak terisi pada tingkat terakhir, simpul tersebut harus terletak paling kiri.
2. Full Binary Tree: Binary tree di mana setiap simpul memiliki tepat dua anak, yaitu anak kiri dan anak kanan. Tidak ada simpul yang memiliki hanya satu anak atau tidak memiliki anak sama sekali.
3. Perfect Binary Tree: Binary tree di mana semua tingkat, termasuk tingkat terakhir, terisi penuh dengan simpul-simpul. Jumlah simpul pada tingkat terakhir adalah 2^k, di mana k adalah tingkat terakhir.
4. Balanced Binary Tree: Binary tree di mana perbedaan tinggi antara anak kiri dan anak kanan dari setiap simpul tidak lebih dari satu.

Traversal Binary Tree

Traversal adalah proses mengunjungi semua simpul dalam binary tree. Terdapat tiga cara umum untuk melakukan traversal binary tree, yaitu traversal sebelum, traversal selama, dan traversal setelah.

1. Traversal Sebelum (Preorder): Pada traversal sebelum, simpul diunjungi terlebih dahulu, kemudian anak kiri, dan akhirnya anak kanan. Dalam traversal sebelum, simpul-simpul akan diunjungi dalam urutan: akar, anak kiri, anak kanan.
2. Traversal Selama (Inorder): Pada traversal selama, simpul anak kiri diunjungi terlebih dahulu, kemudian simpul, dan akhirnya simpul anak kanan. Dalam traversal selama, simpul-simpul akan diunjungi dalam urutan: anak kiri, akar, anak kanan.
3. Traversal Setelah (Postorder): Pada traversal setelah, simpul anak kiri diunjungi terlebih dahulu, kemudian anak kanan, dan akhirnya simpul. Dalam traversal setelah, simpul-simpul akan diunjungi dalam urutan: anak kiri, anak kanan, akar.

Operasi pada Binary Tree

Selain traversal, terdapat beberapa operasi lain yang dapat kita lakukan pada binary tree, di antaranya adalah penyisipan (insertion), penghapusan (deletion), dan pencarian (search). Mari kita bahas masing-masing operasi ini secara singkat.

1. Penyisipan (Insertion): Operasi penyisipan pada binary tree dilakukan untuk menambahkan simpul baru ke dalam struktur. Simpul baru akan ditempatkan pada posisi yang tepat sesuai dengan aturan binary tree.
2. Penghapusan (Deletion): Operasi penghapusan pada binary tree dilakukan untuk menghapus simpul tertentu dari struktur. Penghapusan dapat dilakukan dengan mempertahankan aturan binary tree.
3. Pencarian (Search): Operasi pencarian pada binary tree dilakukan untuk mencari simpul tertentu dalam struktur. Pencarian dilakukan dengan membandingkan nilai simpul yang dicari dengan nilai simpul pada setiap langkah traversal.

Aplikasi Binary Tree dalam Ilmu Komputer

Binary tree memiliki banyak aplikasi dalam ilmu komputer. Beberapa contoh aplikasi binary tree adalah:

1. Representasi Struktur: Binary tree dapat digunakan untuk merepresentasikan struktur data lainnya, seperti heap, trie, dan huffman tree.
2. Pencarian dan Pengurutan: Binary tree dapat digunakan untuk melakukan pencarian dan pengurutan data dengan efisien. Contohnya adalah binary search tree yang digunakan untuk pencarian data.
3. Algoritma Kompresi: Binary tree dapat digunakan dalam algoritma kompresi data, seperti algoritma huffman coding yang digunakan dalam kompresi file.

Keuntungan dan Kekurangan Binary Tree

Penggunaan binary tree memiliki beberapa keuntungan dan kekurangan yang perlu dipertimbangkan sebelum mengimplementasikannya. Berikut adalah beberapa keuntungan dan kekurangan binary tree:

Keuntungan: 

1. Efisiensi Pencarian: Binary tree dapat digunakan untuk melakukan pencarian data dengan efisien, terutama pada binary search tree.
2. Struktur Hierarkis: Binary tree dapat digunakan untuk merepresentasikan struktur hierarkis dengan mudah, seperti dalam kasus struktur organisasi perusahaan.
3. Pemeliharaan Data: Binary tree memungkinkan pemeliharaan dan manipulasi data yang efisien, seperti penyisipan dan penghapusan simpul.

Kekurangan: 

1. Ketidakefisienan Pada Worst Case: Beberapa operasi pada binary tree, seperti pencarian dan penghapusan, dapat menjadi tidak efisien pada kasus-kasus tertentu, terutama jika binary tree tidak seimbang.
2. Penggunaan Memori: Binary tree membutuhkan alokasi memori yang cukup besar tergantung pada jumlah simpul yang digunakan.