STRUKTUR DATA By : Sri Rezeki Candra Nursari
2 SKS
Literatur • Sjukani Moh., (2007), “Struktur Data (Algoritma & Struktur Data 2) dengan C, C++”, Mitra Wacana Media • Utami Ema. dkk, (2007),”Struktur Data (Konsep & Implementasinya Dalam Bahasa C & Free Pascal di GNU/Linux)”, Graha Ilmu • Hubbard Jhon, R., Ph.D, (2000), “Schaum’s Outline Of Theory and Problems of Data Structures With C++” McGraw-Hill • Bambangworawan Paulus., (2004), “Struktur Data Dengan C”, Andi Yogyakarta
Materi 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.
Data dan Struktur Data Array Struktur dan Record Pointer Linked List Stack (Tumpukan) Queue (Antrian) Tree (Pohon) AVL Tree Heap dan B-Tree Sorting Search Hashing Graph
TREE - POHON Pertemuan 09
2 SKS
TREE - POHON • Tree merupakan salah satu bentuk struktur data yang non linear/tidak linear yang menggambarkan hubungan yang bersifat hirarki (hubungan one to many) antara elemen-elemen • Tree dapat juga didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut ROOT dan node yang lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungan satu sama lain (disebut SUBTREE)
Istilah Umum Dalam TREE 1. 2. 3. 4. 5. 6. 7. 8.
Tree (pohon) dan Graph (Graf) Simpul (Vertex, Node) dan Busur (Edge, Arc) Superordinat dan subordinat, father dan son, parent dan children Root (akar) dan Leaf (daun) Level (tingkat) dan Depth (kedalaman) Degree (derajat) simpul dan degree pohon M-ary tree dan binary tree Link dan null-link
1. Tree/Pohon & Graph/Graf • Tree (pohon) merupakan bagian dari graph • Dengan simbol matematik pernyataan Tree dapat dituliskan sebagai berikut : T = G
2. Simpul & Busur • Pohon merupakan kumplan dari simpul dan busur, dimana salah satu simpul merupakan akar (root) dan simpul-simpul lain membentuk suatu sub pohon / sub tree yang dapat dituliskan sbb: T = (V, E) V = vertex/node/titik/simpul E = edge/arc/busur
2. Simpul & Busur • Simpul/Node/Titik/Vertex – Tree terdiri dari 14 buah simpul (n=14) simpul A s.d. N atau v0 s.d. v13 V = {v0, v1, v2....... , v13)
• Busur/Edge – Tree terdiri dari 13 buah busur (m=12) e0 s.d. v12 E = {e0, e1, e2....... , e12)
3. Superordinat & Subordinat • Superordinatdiistilahkan dengan father/bapak/parent sedangkan subordinat diistilahkan dengan son/anak/child • Contoh: – Simpul B merupakan superordinat simpul E dan F – Simpul E dan F merupakan subordinat simpul B – Simpul B mempunyai superordinat yaitu simpul E (left child) dan F (right child)
• •
Parent : predecessor satu level di atas suatu node Child : successor satu level di bawah suatu node
4. Root/Akar & Leaf/Daun • Root (akar) adalah simpul yang tidak mempunyai superordinat. – Untuk pohon yang dicontohkan disamping, maka akar adalah simpul A
– Root : Satu-satunya node khusus dalam tree yang tak punya predecessor
• Leaf/daun adalah simpul yang tidak mempunyai subordinat – Untuk pohon yang dicontohkan disamping, maka daun adalah simpul C, E, G, I, J, K, L, M, N
– Leaf : Node-node dalam tree yang tidak memiliki successor
5. Level & Depth/Kedalaman • Level (tingkat) akar dinyatakan berada pada level 0, setiap turunan satu subordinat, level bertambah 1 • Depth (kedalaman) satu pohon yang mempunyai level teratas atau level tertinggi = k, maka disebut kedalamannya = k – Untuk pohon yang dicontohkan disamping, karena level tertinggi adalah 3 maka depth =3
• Height : Banyaknya tingkatan/level dalam suatu tree
6. Degree sebuah simpul • Degree merupakan sebuah simpul yang menyatakan jumlah simpul subordinat dari simpul tersebut – Untuk pohon disamping : • Simpul A : degree = 3 • Simpul B : degree = 2 • Simpul C : degree = 0
• Degree: Banyaknya child yang memiliki suatu node
istilah-istilah umum dalam tree • Predecessor: node yang berada di atas node tertentu • Successor : node yang berada di bawah node tertentu
istilah-istilah umum dalam tree • Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama • Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama • Sibling : node-node yang memiliki parent yang sama dengan suatu node • Size :Banyaknya node dalam suatu tree
A
B C
D
E
F
Ancestor (F) =A Descendant (A) = F,G & D,E Parent (D) =B Child (A) = B,C Sibling (F) =G Size =7 Height =3 Root =A Leaf = D,E,F,G G
Ancestor (F) = …… Descendant (C) = …. Parent (D) = …. Child (A) = ….. Sibling (F) = …. Size = …. Height = …. Root = ….. Leaf = …… Degree = ….
A
B C
D
E
F
G
J H
I
Root/Akar Leaf/Daun Degree
= ….. = ……
Simpul ......, Degree = .... Simpul ......, Degree = .... etc......
Superordinat/Parent Subordinat/Child
= ….
Simpul ......, Child = .... Simpul ......, Child = .... etc......
Node/Vertex/Titik/Simpul = …. Busur/Edge/Arc = …. Level = ...... Height /Depth/Kedalaman = …. Ancestor (G) / Ancestor (7) = ..... Descendant (G) / Descendant (7) = ..... Sibling (F) / Sibling (3) = ...... Size = .....
