Postingan pertama ini iseng- iseng aja sih, karena ada tugas matematika diskret.. yaa siapa tau ada yang nyari juga,, yuk marii :)
Tree
Tree merupakan salah satu bentuk struktur data bukan linier yang menggambarkan bentuk hierarki antara elemen-elemen. Tree biasanya terdiri dari root (akar) dan node-node (simpul-simpul) yang berada di bawah root. Struktur seperti tree sangat banyak sekali dgunakan dalam dunia nyata, misalnya: struktur organisasi suatu perusahaan, pengaturan filesystem, daftar isi sebuah buku, dan masih banyak lagi.
Ilustrasi struktur data tree:
Degree (derajat) =>adalah jumlah edge yang keluar dan masuk dari sebuah node.
Contoh : node E memiliki in degree 1 dan out degree 2
Root (akar) =>adalah node yang memiliki derajat keluar >=0 dan derajat masuk = 0.
Contoh : node A adalah root
Subtree / child =>adalah bagian salah satu node dibawah root sampai ke bawah.
Contoh : tree C adalah right subtree dan tree B merupakan left subtree dari A
Contoh : node E memiliki in degree 1 dan out degree 2
Root (akar) =>adalah node yang memiliki derajat keluar >=0 dan derajat masuk = 0.
Contoh : node A adalah root
Subtree / child =>adalah bagian salah satu node dibawah root sampai ke bawah.
Contoh : tree C adalah right subtree dan tree B merupakan left subtree dari A
node G dan F merupakan child dari node C
node F merupakan parent dari node J dan K
Ancestor =>adalah Node yang berada di atas node lain.
Contoh : node B adalah ancestor dari node E
Descendant =>adalah node yang berada di bawah node lain.
Contoh : node E adalah descendant dari node A.
Leaf (daun) =>adalah semua node yang derajat masuknya 1 dan derajat keluarnya 0.
Contoh : node D, H, I, J, K, dan G adalah leaf
Sibling =>adalah node yang mempunyai level yang sama dan parent yang sama.
Contoh : node D adalah sibling dari node A
Height => adalah level tertinggi dari tree ditambah 1.
Contoh : height dari tree A adalah 3 + 1 = 4
Weight (bobot) =>adalah jumlah leaf(daun) pada tree.
Contoh : weight dari tree A adalah 6
node F merupakan parent dari node J dan K
Ancestor =>adalah Node yang berada di atas node lain.
Contoh : node B adalah ancestor dari node E
Descendant =>adalah node yang berada di bawah node lain.
Contoh : node E adalah descendant dari node A.
Leaf (daun) =>adalah semua node yang derajat masuknya 1 dan derajat keluarnya 0.
Contoh : node D, H, I, J, K, dan G adalah leaf
Sibling =>adalah node yang mempunyai level yang sama dan parent yang sama.
Contoh : node D adalah sibling dari node A
Height => adalah level tertinggi dari tree ditambah 1.
Contoh : height dari tree A adalah 3 + 1 = 4
Weight (bobot) =>adalah jumlah leaf(daun) pada tree.
Contoh : weight dari tree A adalah 6
BINARY TREE
Sebuah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal 2 subtree yang disebut sebagai subpohon kiri(left subtree) dan subpohon kanan (right subtree) dan kedua subtree tersebut harus terpisah, atau dengan kata lain tiap node dalam binary tree hanya boleh memiliki paling banyak 2 child.
Sebuah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal 2 subtree yang disebut sebagai subpohon kiri(left subtree) dan subpohon kanan (right subtree) dan kedua subtree tersebut harus terpisah, atau dengan kata lain tiap node dalam binary tree hanya boleh memiliki paling banyak 2 child.
Binary tree terdiri dari :
- Full Binary Tree : semua node (kecuali leaf pasti memiliki 2 anak dan tiap subtree memiliki panjang path yang sama)
- Complete Binary Tree : mirip dengan full binary tree, tetapi tiap subtree boleh memiliki panjang path yang berbeda dan tiap node (kecuali leaf memiliki 2 anak)
- Skewed Binary Tree : binary tree yang semua nodenya (kecuali leaf) hanya memiliki satu anak