[kuliah] Tree Struktur data

Definisi Tree
Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hierarkis (hubungan one to many) antara elemen-elemen. Tree bias didefinisikan sebagai kumpulan simpul/node dengan elemen khusus yang disebut Root. Notde lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungan satu sama lain (disebut Subtree). Untuk lebih jelasnya, di bawah akan diuraikan istilah¬istilah umum dalam tree.
Predecessor Node yang berada di atas node tertentu
Successor Node yang berada dibawah node tertentu
Ancestor Seluruh node yang terletak sebelum node tertentu dan terletak
pada jalur yang sama
Descendant Seluruh node yang terletak sebelum node tertentu dan terletak
pada jalur yang sama
Parent Predecessor 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 punyak
predecessor
Leaf Node-node dalam tree yang tak memiliki successor
Degree Banyaknya child yang dimiliki suatu node

Jenis-Jenis Tree 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 dua child. Jenis-Jenis Binary Tree :
Full Binary Tree
Jenis binary tree ini tiap nodenya (kecuali leaf) memiliki dua 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 setiap node kecuali leaf hanya boleh memiliki 2 child.

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

Implementasi Binary Tree
Binary tree dapat diimplementasikan dalam C++ dengan menggunakan double linkedlist.

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 tidak boleh kosong).
Update Mengubah isi dari node yang ditunjuk oleh pointer curret
(Tree tidak boleh kosong)
Retrieve Mengetahui isi dari node yang ditunjuk oleh pointer current
(Tree tidak boleh kosong)
DeleteSub Menghapus sebuah subtree (node beserta seluruh descendant¬
nya) yang ditunjuk current. Tree tidak boleh kosong. Setelah
itu, pointer current dakan berpindah ke parent dari node yang
dihapus.
Characteristic Mengetahui karakteristik dari suatu tree, yakni: size, height,
serta average length. Tree tidak boleh kosong.
Traverse Mengunjungi seluruh node-node pada tree, masing-masing
sekali. Hasilnya adalah urutan informasi secara linear yang
tersimpan dalam tree. Ada tiga cara traverse,yaitu PreOrder,
InOrder, dan PostOrder.

Langkah-langkah Tranverse :
. • PreOrder : cetak isi node yang dikunjungi, kunjungi Left Child, kunjungi Right Child
. • InOrder : kunjungi Left Child, cetak isi node yang dikunjungi, kunjungi Right Child
. • PostOrder : kunjungi Left Child, kunjungi Right Child cetak isi node yang dikunjungi.


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 parent-nya. Binary search tree dibuat untuk mengatasi kelemahan pada binary tree biasa, yaitu kesulitan dalam searching / pendarian node tertentu dalam binary tree. Pada dasarnya operasi dalam Binary Search Tree sama dengan Binary Tree biasa, kecuali pada operasi insert, update, dan delete.
Insert
Pada Binary Search Tree insert dilakukan setelah lokasi yang tepat ditemukan (lokasi tidak ditentukan oleh user sendiri ).

Update
Update ini seperti yang ada pada Binary Tree biasa, namun di sini update akan berpengaruh pada posisi node tersebut selanjutnya. Bila update mengakibatkan tree tersebut bukan Binary Search Tree lagi, harus dilakukan perubahan pada tree dengan melakukan rotasi supaya tetap menjadi Binary Search Tree.

Delete
Seperti halnya update, delete dalam Binary Search Tree juga turut mempengaruhi struktur dari tree tersebut.

AVL Tree
AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan. Selain AVL Tree, terdapat pula Height Balanced n Tree, yakni Binary Search Tree yang memiliki perbedaan level antara subtree kiri dan subtree kanan maksimal adalah n sehingga dengan kata lain AVL Tree adalah Height Balanced 1 Tree. Untuk memudahkan dalam menyeimbangkan tree, digunakan simbol-simbol Bantu :
-(tanda minus) : digunakan apabila Subtree kiri lebih panjang dari Subtree kanan.
+ (tanda plus) : digunakan apabila Subtree kanan lebih panjang dari Subtree kiri.
0 (nol) : digunakan apabila Subtree kiri dan Subtree kanan mempunyai
height yang sama.

contoh program donlot disini
tree.cpp

credit http://ypraptomo.files.wordpress.com/2009/01/struktur-data-c.doc