TREE

  TREE adalah suatu graph yang acyclic, simple, connected yang tidak mengandung loop.

General TREE

  ROOT Tree A ; suatu vertex dengan derajat masuk = 0.

  LEAF Tree A ; suatu vertex dengan derajat keluar = 0.

Tree A atas vertex-vertex : V1, V2, V3, ....... , Vn harus mempunyai :

1.   Satu root A       Root (A) =  V1

2.   Sisanya (V2 , V3, ........,Vn) dipartisi menjadi Tm subtree ; di mana : 0 m n-1

  LEVEL dari suatu vertex A dalam Tree A adalah LENGTH Path(P) (Root(A),A)

Dari gambar Tree A ;

         Tentukan level A :

                Length P(Root(A),A)

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

         Tentukan level G :

                Length P(Root(A),G)

                Length P(B,G) = (B,I) (I,E) (E,G) = 3

  HIGH dari suatu tree A adalah level tertinggi ditambah 1.

  WEIGHT dari suatu tree A adalah jumlah leaf dalam tree A.

Contoh :   Dari Tree A ;  High Tree A = 3 + 1 = 4

                                          Weight Tree A = 5 (A,C,D,G,H)

BINARY TREE

     

  Binary Tree merupakan himpunan vertex-vertex yang terdiri dari 2 subtree (dengan disjoint) yaitu subtree kiri dan subtree kanan.

      Setiap vertex dalam binary tree mempunyai derajat keluar max = 2.

BINARY TREE TRANSVERSAL

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

3 aktivitas dalam Binary tree Transversal :

(1)       Visit the Root

(2)       Transverse the left subtree

(3)       Transverse the right subtree

Algoritma dalam Binary Tree Transversal :

1.         PRE-ORDER TRANSVERSAL

            a.         visit the root

            b.         tranverse the left subtree

            c.         tranverse the right subtree

2.         IN-ORDER TRANSVERSAL

            a.         tranverse the left subtree

            b.         visit the root

            c.         tranverse the right subtree

3.         POST-ORDER TRANSVERSAL

            a.         tranverse the left subtree

            b.         tranverse the right subtree

            c.         visit the root

Contoh :

BINARY SEARCH TREE

           

- suatu Binary Search Tree dari himpunan N record (N1, N2, N3 . . . Nn)

- adalah suatu Binary Tree yang setiap vertex-nya (sebut Ri) ditempati oleh Ni untuk i = 1,2,3 ... N.

Vertex-vertex dari Binary Tree tsb. diatur sedemikian rupa sehingga untuk setiap Ri harus memenuhi syarat sbb :

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

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

Contoh :

Diketahui key dari 7 record (K, M, L, N, P, O, Q)

Binary Search Tree dari 7 key diatas dapat dibentuk :

          

Operasi-operasi pada Binary Search Tree :

1.         Direct Search

2.         Sequential Search

3.         Insert Search

4.         Delete Search

ad.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) kemudia         kembali ke langkah 1.

4. jika k > Ni maka subtree kanan dari Ri ditelusuri dan Ri=right

    (Ri) kembali ke langkah 1.

Contoh :

Carilah Key M dalam Binary Tree berikut secara Direct Search.

Berapa langkah/perbandingan yang dibutuhkan untuk mencari Key M.

Bandingkan dengan rootnya, jika :

            - lebih besar maka cari ke kanan

            - lebih kecil maka cari ke kiri.

ad.2.   SEQUENTIAL SEARCH

untuk mencari vertex K dalam binary search tree dengan Root=Ri.

Algoritmanya menggunakan langkah-langkah : IN-ORDER Transversal (Left Visit Right)

Contoh :

Cari key M dalam Binary Tree berikut secara sequential.

            4 langkah :    K > A 

                                                F > A

                                                D > A

                                                A = A

ad. 4.  DELETE SEARCH

            dilihat dari  Link -list-nya.

BALANCED TREE

           

Suatu Binary Tree dimana untuk setiap Root Ri berlaku struktur subtree kiri = struktur subtree kanan.

Height Balanced tree belum tentu Balance Tree tapi Balance Tree sudah pasti height balance tree.