Data Structure Pertemuan 4, 23 Maret 2016

Binary Tree : Sebuah pohon data structure yang memiliki paling banyak 2 anak / keturunan.

Definisi Binary Tree :

1. Akar dari Tree disebut Root dan akar tersebut merupakan parents (orang tua) dari sebuah tree.
2. Edges adalah penghubung antar nodes.
3. Node yang tidak memiliki anak / keturunan disebut Leaf
4. Nodes yang mempunyai parent’s node yang sama disebut siblings(saudara)
5. Total subtree dalam sebuah Tree disebut Degrees
6. Depth/Kedalaman adalah degree dari sebuah Tree
7. Parent’s Tree maksimal memiliki 2 subtree/anak
8. Kedalaman/Depth sering disebut dengan Level

Jenis-jenis Binary Tree :

1. Perfect Binary Tree : Binary tree yang memiliki anak/keturunan yang sama antara Kiri dan Kanan dan memiliki kedalaman (Depth) yang sama
2. Complete Binary Tree : Binary Tree yang mirip seperti perfect tapi terdapat perbedaan depth antara kiri dan kanan
3. Skewed Binary Tree : Setiap node hanya memiliki 1 anak jadi seperti Binary Tree kanan / sebaliknya
4. Balanced Binary Tree : Perbedaan Depth antara node kiri dan kanan maksimal 1 Level

Rumus pada Binary Tree :

1. Tinggi minimum dari binary tree dengan jumlah node n  -> ²Log(n)
2. Jumlah node maksimum pada suatu level di Binary Tree  -> 2^k
3. Tinggi maksimum dari Binary Tree adalah -> n-1
4. Jumlah node maksimum dari Binary Tree adalah -> 2^h+1-1