Tree adalah kumpulan dari suatu node yang saling berhubungan secara bertingkat. Seperti artinya, Tree (pohon) dapat diliustrasikan sebagai suatu pohon. Pohon tersebut memiliki struktur one-to-many, yang artinya dari hanya 1 induk dengan banyak anak. Ada 3 model data mengenai node yang saling berhubungan ini :
1. Tiap node dapat memiliki data dan link menuju ke node lainnya,
2. Tiap node hanya memiliki 1 induk kecuali Root (akar),
3. Dan tiap node dapat mempunyai anak berapapun jumlahnya.
Tree :
Gambar di atas merupakan contoh sebuah Tree sederhana.
-Root : Angka 1, yang berada pada posisi paling atas. Beberapa sumber menggunakan Level 0 sebagai awal pada baris Root. Tetapi di dalam pembahasan ini, Level 1 akan digunakan pada baris Root .
-Degree : Total sub tree dari sebuah Node. Contoh : Total Degree dari angka 6 berjumlah 2.
-Children : Node yang terhubung langsung dengan Node yang berada di atasnya. Contoh : Children dari angka 6 adalah 7 dan 8.
- Leaf : Node yang tidak memiliki Children. Contoh : Angka 4, 5, 9, dan 10.
-Parent : Node yang terhubung langsung dengan Node yang berada di bawahnya. Contoh : Parent dari angka 4 dan 5 adalah angka 3.
-Sibling : Node yang berada pada Level yang sama, dan memiliki Parent yang sama . Contoh : Sibling dari angka 7 adalah angka 8.
-Descendant(Keturunan): Adalah Seluruh node yang terhubung dari suatu Node, dan berada di bawahnya. Contoh : Descendant dari angka 2 adalah angka 3, 4 dan 5.
-Ancestor : Kebalikan dari Descendant. Contoh : Ancestor dari angka 10 adalah angka 8,6, dan 1.
-Edge : Garis yang menghubungkan antar node.
-Predecesor : Node yang berada di atas Node tertentu.
-Successor : Node yang berada di bawah node tertentu.
-Subtree : Suatu node beserta Descendant-nya.
-Size : Banyak node dalam suatu Tree.
-Height : Banyaknya Level dalam suatu Tree.
Graphs Vs. Trees
Binary Tree.
Merupakan salah satu contoh dari beberapa Tree lainnya, Binary Tree Maksimal hanya memiliki 2 Children saja. 'Bi' yang ada dalam kata Binary artinya 2, begitupula dengan yang Unary (Uno, 1) dan Ternary, yang memiliki 3 Children. Dalam Binary Tree, Children dari suatu Node dibagi menjadi 2 kubu, yaitu kiri dan kanan saja.
Beberapa jenis Binary Tree :
1. Complete Tree.
*Internal Nodes : Node yang memiliki Child/Children.
*Terminal Nodes : Node yang tidak memiliki Chile/Children.
2. Perfect /Full Tree.
*Perfect/Full Tree Termasuk Perfect Tree
3. Skewed Tree.
*Setiap Node maksimal hanya memiliki 1 Child.
Binary Tree Insertion.
BST Disebut juga sebagai Ordered Binary Tree, meiliki Aturan dalam penggunaannya :
1. Child di sebelah kiri suatu Node Harus lebih kecil dari angka Parentnya sendiri.
2. Child di sebelah kanan suatu Node Harus Lebih besar atau samadengan dengan Parentnya sendiri.
Contoh :
1701327806
42PFT
Tidak ada komentar:
Posting Komentar