Tree

          Tree merupakan salah satu bentuk struktur data bukan linier yang menggambarkan bentuk hierarki antara elemen-elemen. Tree adalah suatu graph yang acyclic, simple, connected yang tidak mengandung loop.

          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.

1.        Degree (derajat) adalah jumlah edge yang keluar dan masuk dari sebuah node.

       Contoh : node E memiliki in degree 1 dan out degree 2 

2.        Root (akar) adalah node yang memiliki derajat keluar >=0 dan derajat masuk=0.

       Contoh : node A adalah root Subtree

3.        Child adalah bagian salah satu node dibawah root sampai ke bawah.

       Contoh :

tree C adalah right subtree dari A 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 

4.        Ancestor adalah Node yang berada di atas node lain.

       Contoh : node B adalah ancestor dari node E 

5.        Descendant adalah node yang berada di bawah node lain.

       Contoh : node E adalah descendant dari node A. 

6.        Leaf(daun) adalah semua node yang derajat masuk 1 dan derajat keluar 0.

       Contoh : node D, H, I, J, K, dan G adalah leaf. 

7.      Sibling adalah node yang mempunyai level yang sama dan parent yang sama.

       Contoh : node D dan node E adalah sibling dari node B

8.   Level dari suatu vertex B dalam Tree X adalah Length Path(P) (Root(X),B).

      Contoh : Dari gambar Tree X

         Tentukan level B :

          Length P(Root(X),B)

          Length P(A,B) = (A,B) = 1

         Tentukan level J :

          Length P(Root(X),J)

          Length P(A,J) = (A,C) (C,F) (F,J) = 3

9.    Height (ketinggian) adalah level tertinggi dari tree ditambah 1.

       Contoh : height dari tree A adalah 3 + 1 = 4

10. Weight (bobot) adalah jumlah leaf(daun) pada tree.

       Contoh : weight dari tree A adalah 6

11. Forest merupakan koleksi-koleksi dari Tree

       Contoh :

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.

Contoh :

         (1)                                (2)                                  (3)

                          







Derajat keluar = 2      A adalah subtree kanan     A adalah subtree kiri

      (4)                                                          (5)

                             











 Bukan Binary Tree tapi                   Bukan Binary Tree tapi General Tree

 General Tree karena bukan             karena mempunyai derajat keluar > 2.

 merupakan Subtree Kiri/Kanan

Binary tree terdiri dari :

1.    Full Binary Tree : semua node (kecuali leaf pasti memiliki 2 anak dan tiap subtree memiliki panjang path yang sama)

2. 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)

3. Skewed Binary Tree : binary tree yang semua nodenya (kecuali leaf) hanya memiliki satu anak

 

Binary Tree Transversal adalah proses menelusuri suatu Binary Tree sehingga sedemikian rupa setiap vertex dikunjungi hanya 1 kali.

Algoritma dalam Binary Tree Transversal :

1.  Pre – Order (Mid, Left, Right)

2.  In – Order (Left, Mid, Right)

3.  Post – Order (Left, Right, Mid)

Binary Search Tree (BST)

BST adalah suatu Binary Tree yang setiap vertex-nya (Ri) yang ditempati oleh Ni, i = 1,2,3,... N dan diatur sedemikian rupa sehingga untuk setiap Vertex harus memenuhi syarat berikut :

1.  Jika Rj = left (Ri) maka Nj < Ni

2.  Jika Rj = right (Ri) maka Nj > Ni

Operasi-operasi pada Binary Search Tree :

1.  Direct Search untuk mencari vertex k dalam binary search tree dengan root=Ri , algoritmanya         adalah sbb :

1. Jika tree kosong maka search tidak sukses  (k tidak ada dalam binary search tree)

2. Jika k = Ni maka search sukses (k ada dalam binary search tree)

3. Jika k < Ni maka subtree kiri dari Ri ditelusuri dan Ri = left  (Ri) kemudian kembali ke langkah 1.

4. jika k > Ni maka subtree kanan dari Ri ditelusuri dan Ri=right  (Ri) kembali ke langkah 1.

2.  Sequential Search untuk mencari vertex K dalam binary search tree dengan Root=Ri. Algoritmanya menggunakan langkah-langkah : IN-ORDER Transversal (Left Visit Right).

3.  Insert Search (Prinsip hampir sama dengan direct search, tetapi fungsi ini, menambahkan vertex          pada tree)

4.  Delete Search

Contoh BST :    

          Insert   44, 77, 20, 15, 5, 35, 40, 37, 90, 95, 60, 65, 58

               Pre – Order     = 44, 20, 15, 5, 35, 40, 37, 77, 60, 58, 65, 90, 95

               In – Order       = 5, 15, 20, 35, 37, 40, 44, 58, 60, 65, 77, 90, 95

               Post-Order      = 5, 15, 37, 40, 35, 20, 58, 65, 60, 95, 90, 77, 44

AVL Tree dapat di pelajari sendiri pada web ini, http://www.site.uottawa.ca/~stan/csi2514/applets/avl/BT.html