Pengenalan Algoritma dan Struktur Data - BAB 4 Struktur Data Tree & Binary Tree

BAB 4 STRUKTUR DATA TREE DAN BINARY TREE

CPMK3/CO3: Mahasiswa mampu menjelaskan struktur data non linier tree dan graf serta membahas algoritme terkait tree dan graf

4.1 Pendahuluan

Pembahasan pada topik keempat ini adalah struktur data tree dan binary tree. Apa itu struktur data tree dan binary tree? Semua akan dibahas pada bahasan di bawah ini. Sebelumnya apakah kalian sudah mengenal apa itu data? Data merupakan sesuatu yang didapatkan dan apabila diolah akan dapat menghasilkan sesuatu yang informatif. Apabila data belum diolah menjadi informasi, data akan menjadi sebuah fakta saja. Informasi dari data dapat dimanfaatkan untuk banyak hal. Untuk itu kita perlu mempelajari lebih lanjut apa itu data.

4.2 STRUKTUR DATA TREE

Mengenal Struktur Data Tree

Sudah dijelaskan pada pembahasan sebelumnya bahwa data merupakan suatu fakta yang didapatkan dari berbagai sumber. Data yang dioleh dapat memberikan informasi kepada kita. Untuk mengolah data kita membutuhkan pengelompokkan-pengelompokkan pada data. Untuk mengetahui pengelompokkan data inilah kita perlu mempelajari struktur data. Struktur data memberikan kita bagaimana mengorganisasian data, mengatur data, mengolah data agar tersimpan dan dapat dimanfaatkan secara mudah. Sehingga struktur data merupakan bagaimana kita nantinya mengolah data agar mudah dipahami dan digunakan kembali.

Struktur data sendiri terbagi menjadi struktur data sederhana dan struktur data majemuk. Struktur data sederhana contohnya array dan record. Sedangkan struktur data majemuk contohnya Stack, Queue, Binary Tree, dan sebagainya. Stack dan Queue sudah kita bahas pada Bab 3. Data sendiri memiliki type data berupa angka, huruf, dan karakter yang biasa kita sebut dengan integer, real, boolean, character, string, dan lain sebagainya seperti pada Tabel 1. 

Tabel 1. Data Mahasiswa Mata Kuliah Komputer

Setelah mengetahui sedikit mengenai data, kemudian kita membahas apa itu struktur data tree. Struktur data tree memiliki artian bahwa pengolahan data menggunakan model tree. Tree memiliki arti terjemahan ‘pohon’. Di dalam pohon sendiri terdapat akar (root), cabang dan leaf (daun) seperti bagian pohon pada umumnya dari bawah ke atas. Namun struktur data tree di sini adalah pohon yang terbalik, sehingga pohon dilihat seperti pada Gambar 14.

Gambar 14. Pohon Terbalik

Kenapa disebutnya struktur data tree? Karena seperti pohon saling terhubung sehingga antara data satu dengan yang lain layaknya sebuah pohon saling terhubung. Model pohon sangat sering digunakan untuk melakukan organisir data yang bertingkat atau memiliki urutan. Di dalam struktur data tree ini berisi kumpulan data-data yang sering dinamakan node. Beberapa istilah dalam tree antara lain node, root, leaf, parent, child, sibling, dan level. Struktur data tree menggambarkan hubungan bertingkat atau hirarki (one-to-many). Maksudnya hirarki disini adalah saling berhubungan. Contoh penggunaan pada struktur ini yaitu silsilah keluarga, competition, perusahaan dan struktur penyimpanan file seperti pada Gambar 15. Berbeda dengan dengan array yang dia merupakan data linear, struktur data tree bersifat hirarkhis. Pada Gambar 15, Direktur memiliki hubungan dengan wakil direktur I, bidang I, dan Staff I.

Gambar 15. Tree Sebuah Perusahaan

Mengenal Level pada Tree

Tree memiliki level dan derajat data. Hal ini digunakan untuk menentukan pembacaan atau pemahaman awal mengenai struktur data. Level dilihat dari atas atau data yang pertama kali muncul. Derajat dilihat dari bawah atau dilihat dari data yang paling tinggi. Penjelasan lebih lanjut dapat dilihat pada Gambar 16.

Gambar 16. Perbedaan Level (a) dan Derajat (b)

Mengenal Istilah Tree

Tree memiliki istilah-istilah yang harus dimengerti. Istilah-istilah tree akan dijelaskan pada Tabel 2 di bawah ini.

Tabel 2. Istilah Tree

Ordered dan Unordered Tree

Sesuai dengan istilahnya ordered memiliki arti bahwa suatu daftar mempunyai urutan. Sedangkan unordered memiliki arti suatu daftar tidak memiliki urutan tertentu. Contoh dari unordered tree dapat dilihat pada Gambar 15 dan ordered tree dapat dilihat pada Gambar 17.

Gambar 17. Ordered Tree

Operasi Tree

Beberapa operasi yang ada di dalam tree yaitu:

• Create

Digunakan untuk membuat binary tree.

• Clear

Digunakan untuk melakukan penghapusan seluruh node di binary tree.

• Empty

Digunakan untuk melakukan pengecekan pada binary tree sudah terisi atau belum.

• Insert

Digunakan untuk memasukkan node ke tree.

• Update

Digunakan untuk merubah isian node di tree.

4.3 BINARY TREE

Binary memiliki konsep setiap node hanya memiliki maksimal 2 subtree dan harus terpisah. Beberapa aturan di dalam binary tree yaitu sebagai berikut:

1. Boleh tidak mempunyai child
2. Boleh tidak mempunyai subtree
3. Boleh hanya memiliki left atau right subtree
4. Boleh memiliki left dan right subtree

Jenis-jenis Binary Tree

Jenis-jenis binary tree digunakan untuk membaca tipe yang ada di Binary Tree. Berikut merupakan jenis-jenis Binary Tree, yaitu:

a. Full Binary Tree

Full binary tree yaitu binary tree yang semua banyak child di nodenya sama rata kecuali leaf. Misalnya sebuah tree memiliki root A. Root A memiliki child B dan C. Node B memiliki child D dan E, sedangkan node C memiliki child F dan G. Masing- masing node D, E, F, dan G memiliki child H, I, J, K, L, M, N, dan O yang memiliki posisi sebagai leaf.

b. Complete Binary Tree

Berbeda dengan full binary tree, complete binary memperbolehkan memiliki jalur yang berbeda. Contohnya Gambar 17.

c. Skewed Binary Tree

Binary tree yang hanya memiliki satu child saja, boleh di kiri atau di kanan saja kecuali leaf. Contohnya seperti gambar 17, misalnya root 80 memiliki child 60. Sedangkan node 60 memiliki child 20. Sehingga hanya satu jalur saja.

Tree Tranversal

Tree tranversal memiliki arti sebuah cara untuk melakukan penelurusan sesuai aturan sehingga node-node hanya dapat ditelusuri satu kali. Jika ditemukan node tidak terisi maka tranversal tidak dilanjutkan. Beberapa cara untuk melakukan penelusuran seperti preOrder, inOrder, dan postOrder.

a. preOrder

• Pertama lihat root
• Penelusuran mulai dari left subtree
• Penelusuran dari Right subtree

Pada gambar 18, jalur preOrder-nya yaitu A, B, D, E, F, C.

Gambar 18. PreOrder

 b. inOrder

• Penelusuran dimulai dari left subtree
• Penelusuran ke root
• Penelusuran Right subtree

Pada gambar 18, jalur inOrder-nya yaitu D, B, F, E, C.

c. postOrder

• Penelusuran dimulai dari left subtree
• Penelusuran Right subtree
• Terakhir ke root

Pada gambar 18, jalur inOrder-nya yaitu D, F, E, B, C, A.

4.4 Referensi

Rerung, R. R., Algoritma dan Struktur Data untuk Perguruan Tinggi. Solok: CV. Insan Cendekia Mandiri, 2018.

Buana, I. K. S., Nata, G. N. M., dan Arnawa, I. B. K. S., Struktur Data. Yogyakarta: Andi, 2018.

Jagtap, A. M. dan Mali, A. S., Data Structures Using C A Practical Approach for Beginners,

Amerika serikat: CRC Press, 2021.

Subscribe Our Newsletter