Pertemuan ke - 4 - Introduce Tree, Binary Tree - 2101691676 - Handi Putra Tjioe

TREE

Tree adalah bentuk struktur data non-linear, dengan bentuk 2 dimensi yang mempunyai properti yang berbeda dari struktur data linear lainnya, seperti: 

- Linked list

- Queue

- Stack.

Sama seperti struktur data lainnya tree juga mengandung node yang juga dihubungkan dengan pointer-pointer lainnya untuk mengakses data yang ada pada tree.

Umumnya, dapat dikategorikan bahwa tree adalah kumpulan dari subtree-subtree yang digabungkan menjadi sebuah tree. sementara ada juga istilah forest yang merupakan kumpulan dari tree.

Bagian-bagian yang ada pada tree:

1. Node

    Pada tree sendiri banyak istilah node yang berbeda yakni:

- Root node : node pertama (puncak) dari sebuah tree

- Terminal node/Leaf node : node yang tidak memiliki child, sehingga memiliki degree 0

2. Root/root node

Akar dari sebuah tree dimana akan diturunkan kepada child nodenya sendiri

3. Children

Turunan dari parent/anchestor sehingga menghasilkan node yang baru pada sebuah tree

4. Siblings

Node yang memiliki children yang sama, dari sebuah parent

di bawah akan diuraikan istilah-istilah umum dalam tree :

1. 1. Prodecessor : node yang berada diatas node tertentu.
   2. Successor : node yang berada di bawah node tertentu.
   3. Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.
   4. Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.
   5. Parent : predecssor satu level di atas suatu node.
   6. Child : successor satu level di bawah suatu node.
   7. Sibling : node-node yang memiliki parent yang sama dengan suatu node.
   8. Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
   9. Size : banyaknya node dalam suatu tree.
   10. Height : banyaknya tingkatan/level dalam suatu tree.
   11. Root : satu-satunya node khusus dalam tree yang tak punya predecssor.
   12. Leaf : node-node dalam tree yang tak memiliki seccessor.
   13. Degree : banyaknya child yang dimiliki suatu node

BINARY TREE

Binary tree adalah sejenis tree yang dimana pada setiap node hanya bisa mengandung/memiliki 2 node saja untuk diturunkan ke node selanjutnya.

Jenis-jenis binary tree :

1. Perfect binary tree

Jenis binary tree yang semua level atau depth sama.

2.Completed binary tree

  

3.Skewed binary tree

4. Balanced binary tree

Operasi-operasi pada Binary Tree :

1. Create : Membentuk binary tree baru yang masih kosong.
2. Clear : Mengosongkan binary tree yang sudah ada.
3. Empty : Function untuk memeriksa apakah binary tree masih kosong.
4. Insert : Memasukkan sebuah node ke dalam tree. Ada tiga pilihan insert: sebagai root, left child, atau right child. Khusus insert sebagai root, tree harus dalam keadaan kosong.
5. Find : Mencari root, parent, left child, atau right child dari suatu node. (Tree tak boleh kosong)
6. Update : Mengubah isi dari node yang ditunjuk oleh pointer current. (Tree tidak boleh kosong)
7. Retrieve : Mengetahui isi dari node yang ditunjuk pointer current. (Tree tidak boleh kosong)
8. DeleteSub : Menghapus sebuah subtree (node beserta seluruh descendantnya) yang ditunjuk current. Tree tak boleh kosong. Setelah itu pointer current akan berpindah ke parent dari node yang dihapus.
9. Characteristic : Mengetahui karakteristik dari suatu tree, yakni : size, height, serta average lengthnya. Tree tidak boleh kosong. (Average Length = [jumlahNodeLvl1*1+jmlNodeLvl2*2+…+jmlNodeLvln*n]/Size)
10. Traverse : Mengunjungi seluruh node-node pada tree, masing-masing sekali. Hasilnya adalah urutan informasi secara linier yang tersimpan dalam tree. Ada tiga cara traverse : Pre Order, In Order, dan Post Order.