5-tree & Binary Tree-2101652195-Anisa Rahmawati

Tree & Binary Tree

1.    Pengertian tree

Tree Merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungan satu sama lainnya (disebut subtree)

2.    Pengertian 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, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.

Perbedaan binary dengan graph, graph looping/mengulang.

Jenis-jenis Binary Tree :

a.     Full Binary Tree

Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.

b.     Complete Binary Tree

Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.

c.     Skewed Binary Tree

yakni Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.

3.    Binary Search Tree

Binary Search Tree adalah struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap clild node sebelah kiri selalu lebih kecil nilainya dari pada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node. Fungsi binary search tree yaitu untuk mempermudah searching.

Aturan binary search tree :

1. Node yang paling atas disebut root

2.Node yang tidak punya cabang disebut leaf.

3.Angka yang lebih kecil selalu ada di seblah kiri

4.Angka yang lebih besar selalu ada di sebelah kanan

 38 = root

13 lebih kecil dari 38 maka disimpan diseblah kiri dari 38

51 lebih besar dari 38 maka disimpan di samping kanan 58

10 lebih kecil dari 58 maka di simpan di samping kiri dan dibandingan kembali dengan 13, 10 lebih kecil dari 13 maka disimpan di samping kiri 13.

25 lebih kecil dari 38 maka disimpan disamping kiri 38, dan di bandingkan kembali dengan 13, 25 lebih besar dari 13 maka disimpang di samping kanan 13. dst.