< Tree >

TREE >>

Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hierarkis antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan elemen khusus yang disebut Root. Node lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungan satu sama lain.

Istilah Istilah dalam Tree >>

a) Prodecessor : node yang berada diatas node tertentu.
b) Successor : node yang berada di bawah node tertentu.
c) Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.
d) Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.
e) Parent : predecssor satu level di atas suatu node.
f) Child : successor satu level di bawah suatu node.
g) Sibling : node-node yang memiliki parent yang sama dengan suatu node.
h) Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
i) Size : banyaknya node dalam suatu tree.
j) Height : banyaknya tingkatan/level dalam suatu tree.
k) Root : satu-satunya node khusus dalam tree yang tak punya predecssor.
l) Leaf : node-node dalam tree yang tak memiliki seccessor.
m) Degree : banyaknya child yang dimiliki suatu node.

JENIS-JENIS TREE >>

1) Binary tree
Binary tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut tiap node dalam binary tree hanya boleh memiliki paling banyak 2 child.


JENIS-JENIS BINARY TREE:

Ø FULL BINARY TREE
Jenis binary tree ini tiap nodenya (kecuali leaf) memiliki 2 child dan tiap subtree harus mempunyai panjang path yang sama.

Ø COMPLETE BINARY TREE
Jenis ini mirip dengan full binary tree, namun tiap subtree boleh memiliki panjang path yang berbeda dan stiap node kecuali leaf hanya boleh memiliki 2 child.

Ø SKEWED BINARY TREE
Skewed binary tree adalah binary tree yang semua nodenya (kecuali leaf)  Hanya memiliki 1 child

Ø IMPLEMENTASI BINARY TREE
Binary tree dapat diimplementasikan dalam c++ dengan menggunakan double linked list.
Akar (Root nodes)
Simpul yang paling atas dalam pohon adalah akar (root node). Menjadi simpul teratas, simpul akar tidak akan memiliki orang tua. Ini merupakan simpul di mana biasanya merupakan tempat untuk memulai operasi dalam pohon (walaupun beberapa algoritma dimulai dengan daun dan berakhir pada akar). Semua simpul yang lain dapat dicapai dari akar dengan menelusuri pinggiran atau pranala. (Dalam definisi resmi, setiap jalan adalah khas). Dalam diagram, ini secara khusus di gambar paling atas. Di beberapa pohon, seperti heap, akar memiliki sifat khusus. Setiap simpul dalam sebuah pohon dapat dilihat sebagai akar dari sub pohon yang berakar pada simpul tersebut.

Daun (Leaf nodes)
Semua simpul yang berada pada tingkat terendah dari pohon dinamakan daun (leaf node). Sejak mereka terletak pada tingkat paling bawah, mereka tidak memiliki anak satupun. Seringkali, daun merupakan simpul terjauh dari akar. Dalam teori grafik, sebuah daun adalah sebuah sudut dengan tingkat 1 selain akar (kecuali jika pohonnya hanya memiliki satu sudut; maka akarnya adalah daunnya juga). Setiap pohon memiliki setidaknya satu daun.
Dalam pohon berdasarkan genetic programming sebuah daun (juga dibilang terminal) adalah bagian terluar dari sebuah program pohon. Jika dibandingkan dengan fungsinya atau simpul dalam, daun tidak memiliki argumen. Di banyak kasus dalam daun-GP input ke programnya.



BINARY SEARCH TREE

Binary tree ini memiliki sifat dimana semua left child harus lebih kecil dari pada right child dan parentnya. Semua right child juga harus lebih besar dari left child serta parentnya. Binary search tree dibuat untuk mengatasi kelemahan pada binary tree biasa, yaitu kesulitan dalam searching/pencarian node tertentu dalam binary tree.

Implementasi Binary Search Tree

Ketentuan :

a. Semua left child harus lebih kecil dari parent

b. Semua right child harus lebih besar dari parent

Keuntungan : Pencarian node target menjadi lebih efisien dan cepat

Operasi-Operasi Standar BST :

- Mengosongkan BST

- Mencek apakah BST kosong

- Mencari Tree Minimum

- Mencari Tree Maksimum

- Memasukkan data baru ke dalam BST

- Mencari elemen tertentu dalam BST

- Menghapus data tertentu dari dalam BST

- Menampilkan semua elemen dalam BST

Tree Traversal

      Teknik menyusuri tiap node dalam sebuah tree secara sistematis, sehingga semua node dapat dan  hanya satu kali saja dikunjungi

Ada tiga cara traversal :

- preorder

- inorder

- postorder

       Untuk tree yang kosong, traversal tidak perlu dilakukan 

    1. PREORDER

          Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :

      - Cetak isi simpul yang dikunjungi.

      - Kunjungi cabang kiri.

      - Kunjungi cabang kanan.


Procedure PREORDER(Temp : Tree);

Begin

If Temp <> NIL Then

Begin

Write(Temp^.Info,’ ‘); {Cetak isi simpul}

PREORDER(Temp^.Kiri); {Kunjungi cabang kiri}

PREORDER(Temp^.Kanan); {Kunjungi cabang kanan}

End;

End;


2. INORDER

           Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :

     - Kunjungi cabang kiri.

     - Cetak isi simpul yang dikunjungi.

     - Kunjungi cabang kanan.

    Prosedur untuk melakukan traversal secara INORDER adalah sebagai berikut:


Procedure INORDER(Temp : Tree);
Begin
If Temp <> NIL Then
Begin
INORDER(Temp^.Kiri); {Kunjungi cabang kiri}
Write(Temp^.Info,’ ‘); {Cetak isi simpul}
INORDER(Temp^.Kanan); {Kunjungi cabang kanan}
End;
End;


 3. POSTORDER 

             Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :

         - Kunjungi cabang kiri.

        - Kunjungi cabang kanan.

        - Cetak isi simpul yang dikunjungi.


Procedure POSTORDER(Temp : Tree);
Begin
If Temp <> NIL Then
Begin
POSTORDER(Temp^.Kiri); {Kunjungi cabang kiri}
POSTORDER(Temp^.Kanan); {Kunjungi cabang kanan}
Write(Temp^.Info,’ ‘); {Cetak isi simpul}
End;
End;