Data Structure 04

Data Stucture pertemuan 04

Pada pertemuan 4 ini, kami membahas mengenai TREE CONCEPT . Tree Concept ini digunakan pada saat kami mempelajari Data Base nanti, dan contohnya seperti penggunaan Directory .Sesuai namanya Tree berarti Pohon . Maka Tree Concept ini digambarkan seperti membuat pohon :

 

Dalam Tree terdapat istilah-istilah yang perlu diketahui:
1.       Parent

Pada Tree diatas:

-Parent of E : B

-Parent of C : A

2.       Root

Root merupakan akar dari segala node yang ada, dan terdapat di level teratas .

Pada Tree diatas:

Root : A

3.       Edge

Edge merupakan garis yang menghubungkan parent ke child nya

4.       Leaf

Leaf merupakan node yang terbawah , atau bias dibilang node yang tidak mempunyai child lagi

Leaf : K , L , M

5.       Siblings

Siblings merupakan node yang mempunyai parent yang sama

Siblings of F : G , H

Siblings of B : C , D

6.       Degree

Degree merupakan node pada total sub tree

Degree of tree : 4

Degree of C : 3

7.       Height/Depth

Height merupakan maximum degree pada tree tersebut

Height of Tree : 4

8.       Ancestor

Ancestor merupakan nenek moyang dari nodes .

Ancestor of G : C , A

9.       Descendant

Descendant merupakan keturunan dari nodes

Descendant of C : F , G , H , M

Binary Tree hanya mempunyai 2 anak (Left Child & Right Child).

Type of Binary Tree:
1.       Perfect Binary Tree
2.       Complete Binary Tree
3.       Skewed Binary Tree
4.       Balanced Binary Tree

1.       Perfect Binary Tree

Tree yang masing-masing mempunyai 2 anak, dimana kanan dan kiri seimbang

2.       Complete Binary Tree

Tree yang hampir sempurna atau seperti Perfect Binary Tree yang tidak seimbang



3.       Skewed Binary Tree

Tree yang parent-nya hanya mempunyai 1 anak

4.       Balanced Binary Tree

Tree yang jarak dari root ke leaf sama dengan jarak antara kiri dan kanan

PROPERTY BINARY TREE

Rumus :

1.       Menghitung maximum node per level : 2^k (k = level)

2.       Menghitung maximum node per height : 2^h+1 – 1 (h = level)

3.       Menghitung minimum height : 2 log n (n=node) atau cara mudahnya menggambar tree dimana setiap parent mempunyai 2 anak

4.       Menghitung maximum height : n-1 (n=node) atau cara mudahnya menggambar dengan type skewed

REPRESENTATION OF BINARY TREE WITH ARRAY/LINKED LIST

1.       Array

Rumus :

1.       Index Left Child : 2p+1

2.       Index Right Child : 2p+2

3.       Index Parent : (c-1)/2

2.       Linked List

EXPRESSION TREE CONCEPT

Prefix -> Print Left Right                                                                                       

Postfix ->Left Right Print                                                                                       

Infix -> Left Print Right