Data Structure 4

Rangkuman Binary Tree

Tugas Rangkuman 004

Gw belajar apa itu "Binary Tree" dalam Data Structure itu dari Youtube. Sebelumnya, gua cuman pernah tau istilah "Binary Tree" ini dalam mata kuliah "Matematika Diskrit" pas gw masih semester 1 kemaren. Mungkin, di semester 1 yang lalu, itu juga tujuannya gw diajarin konsep "Binary Tree" ini untuk membangun pondasi konsep gw tentang Binary Tree di semester yang akan datang seperti sekarang.

Nah dari Youtube, gw belajar atau diingetin lagi apa itu Binary Tree. Yang gw dapet, Binary Tree itu adalah konsep Tree yang mempunyai akar/root pastinya. Tapi, yang membedakan dia dari Tree biasa itu adalah banyak anaknya/cabangnya. Kalau dalam Binary Tree, kita cuman bisa punya anak sebanyak 0-2 anak/cabang.

Nah, Binary Tree ini pun masih ada jenis-jenisnya lagi. Yang pertama itu, Strict Binary Tree, di mana kita cuman boleh punya anak antara 0 atau 2. Jadi, kita gaboleh cuman punya 1 anak, apalagi 3, 4, 5, dst. 

Nah, jenis Binary Tree yang ke-2 itu namanya Complete Binary Tree yang justru punya aturan lebih strik lagi dari yang sebelumnya. Aturannya adalah, kita harus punya anak sampe level yang sejajar. Maksudnya itu, dalam "dunia" Tree ini kita bakal kenal sama yang namanya level-levelan. Kalau misalnya root/akar itu kita anggap adalah level 0, maka anak pertama dari root ini kita sebut levelnya menjadi level 1. Begitu pula seterusnya. Nah jadi kalau misalnya di antara cabang-cabang kita ada yang punya anak sampe dengan level 3, maka semuanya juga harus ngikutin punya anak sampe level 3 juga. Mungkin agak susah kalo dibayangin tanpa gambar. Makanya nih gw kasih gambarannya biar lebih kebayang.

Nah kita bisa liat dari gambar di atas, perbedaannya Binary Tree yang "complete" sama yang "gak complete".

Dan jenis Binary Tree yang terakhir itu namanya "Perfect Binary Tree". Kenapa dinamain perfect, karena dia bentukannya harus kayak gambar di bawah ini.

Nah, kalo udah ngerti konsepnya dalam matematika, kita tinggal terapin ke dalam codingannya.

deklarasiin tree dalam bahasa C bisa dengan struct kayak gini:

struct node

{

     int data;

     node* left;

     node* right;

};

Kenapa harus ada left dan right? Karena masing-masing node dalam tree ini bisa punya 0-2 anak. Kalo seandainya punya 0 anak, makan nilai pointer dari left dan rightnya = NULL. 

Tapi kita juga bisa deklarasiin Binary Tree ini bukan hanya dengan struct aja, bisa juga dengan array. Tapi, ini cuman berlaku kalo kita mau bikin "Perfect Binary Tree" aja. Kita bisa mulai dari root sebagai index 0, anak left dari rootnya sebagai index 1, anak kanan dari rootnya sebagai index 2, dan seterusnya. Setelah itu, kita bisa pake logic untuk node pada index i, index anak kirinya = 2i + 1 dan index anak kanannya = 2i + 2