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 :
- Prodecessor : node yang berada diatas node tertentu.
- Successor : node yang berada di bawah node tertentu.
- Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.
- Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.
- Parent : predecssor satu level di atas suatu node.
- Child : successor satu level di bawah suatu node.
- Sibling : node-node yang memiliki parent yang sama dengan suatu node.
- Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
- Size : banyaknya node dalam suatu tree.
- Height : banyaknya tingkatan/level dalam suatu tree.
- Root : satu-satunya node khusus dalam tree yang tak punya predecssor.
- Leaf : node-node dalam tree yang tak memiliki seccessor.
- 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 :
- Create : Membentuk binary tree baru yang masih kosong.
- Clear : Mengosongkan binary tree yang sudah ada.
- Empty : Function untuk memeriksa apakah binary tree masih kosong.
- 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.
- Find : Mencari root, parent, left child, atau right child dari suatu node. (Tree tak boleh kosong)
- Update : Mengubah isi dari node yang ditunjuk oleh pointer current. (Tree tidak boleh kosong)
- Retrieve : Mengetahui isi dari node yang ditunjuk pointer current. (Tree tidak boleh kosong)
- 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.
- 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)
- 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.
