PENGERTIAN
Tree bisa
didefinisikan sebagai suatu kumpulan elemen salah satu elemennya disebut dengan
akar (root), dan sisa elemen lainnya (yang disebut simpul) terpecah menjadi
sejumlah himpunan yang paling tidak berhubungan satu sama lain, yang disebut
dengan subpohon (subtree), atau disebut juga cabang.
Jika kita melihat pada subpohon, maka subpohon
inipun juga mempunyai akar
dan sub-subpohonnya masing-masing.
Dalam kehidupan sehari-hari, tree dapat dilihat
dari pohon silsilah keluarga.
Untuk jelasnya, 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.Tingkat yang tertinggi disebut juga sebagai root.
- Degree : banyaknya child yang dimiliki suatu node.
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.
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.
Langkah-Langkahnya Traverse :
- 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 TREES
(POHON CARI BINER)
Pohon cari biner adalah pohon biner yang
dirancang untuk menskemakan urutan data yang akan dimasukkan ke dalam memori
agar proses pencarian, penghapusan dan penambahan data dapat berjalan secara
efisien dibanding dengan pemasukan data secara array maupun link.
Sifat dari skema pohon cari biner adalah : (1)
setiap elemen yang berada di left substrees selalu lebih kecil dari elemen yang
ada di right substrees, (2) setiap elemen yang berada di right substrees selalu
lebih besar atau sama dengan elemen yang berada di left substrees.
Contoh : diketahui sekumpulan elemen sebagai
berikut :
60, 75, 25, 50, 15, 66, 33, 44
Pembentukan awal skema pohon binernya
berturut-turut sebagai berikut :
Dan, hasil akhirnya sebagai berikut :
Komentar
Posting Komentar