Pertemuan 4 - (Tree Concept and Binary Concept)

Konsep Tree

tree adalah kumpulan node yang terhubung satu sama lain dan membentuk struktur seperti sebuah pohon.

istilah istilah yang sering digunakan dalam tree

1. Degree = banyak child dalam suatu node
2. Height = banyak tingkatan dalam suatu tree
3. Size = banyaknya node dalam suatu tree
4. Predecesor = node yang berada diatas suatu node tertentu
5. Successor = node yang berada dibawah suatu node tertentu
6. Parent = predecesor satu level diatas suatu node
7. Child = successor satu level dibawah suatu node
8. Sibling = node - node yang memiliki parent yang sama
9. Ancestor = seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama 
10. Descendant = seluruh node yang terletak setelah node tertentu dan terletak pada jalur yang sama

Pembentukan Tree

Dapat dilakukan dengan 2 cara : Rekursif dan Non Rekursif 

Perhatikan kapan node dipasang di kiri dan dipasang di kanan


Jenis Tree ada yang berupa Binary Tree.

Binary Tree

merupakan Tree dengan syarat bahwa tiap nodenya maksimal memiliki dua subpohon dan masing masing subpohon harus terpisah.

Jenis - jenis Binary Tree

1. Full Binary Tree

tree yang memiliki 2 child dan setiap pohon memiliki panjang yang sama

2. Complete Binary Tree

tree yang mirip dengan Full Binary Tree tetapi setiap subtree boleh memiliki panjang yang berbeda. Full Binary Tree pasti merupakan Complete Binary Tree

3. Skewed Binary Tree
tree yang setiap nodenya hanya mempunyai satu child

Sifat - Sifat Binary Tree

Maksimum node dalam satu level dapat dihitung dengan cara 2^k. dimana k adalah level.

Maksimum node yang ada dalam binary tree dapat dihitung dengan cara 2^(h+1) - 1. Dimana h adalah height atau tingkatannya

Minimum height dapat dihitung dengan cara 2log(n) . Dimana n adalah jumlah node

Maksimum height dapat dihitung dengan cara n-1 . Dimana n adalah jumlah node