TREE (POHON)
A. Definisi
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. Tingkat yang tertinggi disebut juga sebagai root.
B. Istilah istilah
dalam tree
1)
Predecessor : 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 : predecessor 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 successor.
13) Degree : banyaknya child yang dimiliki suatu
node.
C. 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. 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.
D. Operasi Dasar Binary Tree
Operasi-operasi
pada Binary Tree :
v Create : Membentuk binary tree baru yang masih
kosong.
v Clear : Mengosongkan binary tree yang sudah
ada.
v Empty : Function untuk memeriksa apakah binary
tree masih kosong.
v 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.
v Find : Mencari root, parent, left child,
atau right child dari suatu node. (Tree tak boleh kosong)
v Update : Mengubah isi dari node yang ditunjuk
oleh pointer current. (Tree tidak boleh kosong)
v Retrieve : Mengetahui isi dari node yang ditunjuk
pointer current. (Tree tidak boleh kosong)
v 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.
v 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)
v 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.
0 komentar: