Struktur Data - Pertemuan 14
Tree merupakan struktur data yang mempunyai hubungan One – to- Many, atau juga di sebut Nested /
Hirarki. Hubungan One-to-Many ini meliputi juga hubungan One- to – One, atau One-to-Zero, yang
dapat dijelaskan bahwa satu parent ( orang – tua ) bisa memiliki satu, atau nol atau lebih child (
anak ). Elemen dalam TREE disebut dengan NODE. Banyak sekali contoh yang bisa diberikan
mengenai tree ini. Seperti : hubungan orang – tua dengan anak ( satu ibu bisa mempunyai satu atau
lebih anak atau tidak memiliki anak ) hubungan bagian kerja dengan pekerjanya ( misal bagian
Penjualan memiliki lebih dari satu pekerja ) dan seterusnya.
Gambar 9.1 : Contoh TREE
Karakteristik dari Tree adalah :
> Terdapat 1 node yang unique, yang tidak memiliki predecessor. Node ini disebut ROOT.
Kalau melihat ke contoh di atas, maka PERUSAHAAN merupakan ROOT.
> Terdapat satu atau beberapa node yang tidak mempunyai successor. Node ini disebut LEAF.
BAGIAN PEMBELIAN. BAGIAN LAINNYA, STAFF ( A ) , STAFF ( B ) dan STAFF ( C )
merupakan LEAF pada contoh di atas.
> Setiap node, kecuali ROOT, pasti memiliki 1 predecessor yang unique. Kembali dengan
mempergunakan contoh di atas, maka predecessor dari STAFF ( B ) PENJUALAN adalah
BAGIAN PENJUALAN, predescessor dari BAGIAN PEMBELIAN adalah PERUAHAAN.
> Setiap node, kecuali LEAF, pasti memiliki 1 atau lebih successor. Contoh successor dari
BAGIAN PENJUALAN adalah STAFF ( A ) , STAFF ( B ) dan STAFF ( C ).
Dibawah ini akan dijelaskan bebrapa istilah yang akan dipergunakan untuk menjelaskan tentang
TREE ( pembahasan di bawah akan mempergunakan TREE berikut sebagai contoh).
HUBUNGAN PARENT CHILD
> PARENT adalah predecessor langsung dari suatu node, Semua node kecuali ROOT pasti
memiliki 1 PARENT yang unique.
Contoh : TREE pada gambar 1 diatas, PERUSAHAAN merupakan PARENT dan BAGIAN
PEMBELIAN, BAGIAN PENJUALAN dan BAGIAN LAINNYA.contoh TREE pada gambar 2
diatas B merupakan PARENT dari E, F.
> CHILD adalah Successor langsung dari suatu node, semua node kecuali LEAF pasti memiliki
1 atau lebih CHILD.
Contoh TREE pada gambar 1 diatas, BAGIAN PENJUALAN memiliki CHILD sebagai berikut
STAFF ( A ), STAFF ( B ) dan STAFF ( C ). Contoh TREE pada gambar 2 diatas, CHILD dari
node O adalah node R, T
> Node-node yang memiliki PARENT yangs sama disebut SIBLING.
Contoh TREE pada gambar 1 diatas STAFF ( A ) mempunyai SIBLING sebagai berikut TREE
( B ) dan staff ( C ) . contoh TREE pada gambar 2 di atas, node O mempunyai SIBLING K
HUBUNGAN ANCESTOR – DESCENDENT
> ANCESTOR adalah semua node yang berada di atas / sebelum node tertentu yang terdapat
pada path yang sama.
Contoh TREE pada gambar 2 diatas , node R mempunyai 4 buah ANCESTOR yaitu node O,
X, C, A.
> DESCENDAT adalah semua node yang berada di bawah / setelah node tertentu
Contoh TREE pada gambar 2 diatas, node C mempunyai 6 DESCENDAT, yaitu X, M, O, K, R,
T.
> TREE memiliki sifat yang dinamakan RECURSIVE, yang dapat di definisikan bahwa untuk
sebuah node tertentu , node tersebut beserta semua descedantnya adalah
SUBTREE dari parentnya. SUBTREE tersebut memiliki semua karakteristik dari suatu TREE.
Definisi lain yang berhubungan dengan height adalah TREE PATH-LENGTH, yaitu :
> Untuk SIMPLE TREE, path length adalah sama dengan JUMLAH NODE dikurangi 1.
> Secara umum, path length diambil dari path length dari subtree yang terpanjang ( atau tree
height dikurangi 1 ).
Gambar 9.3 : RECURSIVE
Pada gambar di atas, terlihat bahwa A mempunyai 2 Subtree, yaitu Sub Tree 1 dan SubTree 2, yang
mana masing-masing subtree mempunyai karakteristik yang sama dengan tree keseluruhan, misalnya
tersebut ada ROOT, LEAF dll.
Setiap node dalam TREE pasti akan berada pada suatu level tertentu. Dimana ROOT dapat
didefinisikan memiliki level yang paling rendah yaitu 1 CHILD dari memiliki 1 level lebih tinggi dari
PARENTnya, sehingga CHILD dari ROOT dapat didefinisikan berada pada level 2 dstnya. Dengan
mengetahui level dari suatu node, maka TREE HEIGHT ( tinggi pohon ) dapat ditentukan , yaitu :
merupakan level paling tinggi dari nodenya sebagai contoh, tree pada gambar dibawah ini memiliki 11
node dan memiliki TREE HEIGHT 4.
BINARY TREE
Binary Tree memiliki semua karakterisktik dari TREE, yang menjadi perbedaan adalah bahwa
maksimum CHILD yang bisa dimiliki suatu node dalam BINARY TREE adalah 2 yang disebut LEFT
CHILD dari RIGHT CHILD. Gambar memperlihatkan contoh dari Binary Tree. Seperti terlihat pada
gambar, bahwa node dalam Binary Tree dapat memiliki 0, 1 atau maksimum 2 CHILD, contoh node W
memiliki 2 CHILD, node Y memiliki 1 CHILD ( yaitu LeftChild, berupa node T ) dan Node tidak memiliki
CHILD.
Binary Tree dapat memiliki beberapa bentuk yaitu :
> Complete Binary Tree atau juga disebut HEAP. Definisi Complete Binary Tree adalah
sebuah Binary Tree yang bila semua nodenya memiliki 0 ( berarti LEAF ) atau 2 children .
berarti di dalam Completer Binary Tree, node tidak diperkenankan untuk memiliki hanya 1
child. Subtree dalam heap dapat mempunyai path length yang berbeda. Tree pada contoh 6
ini bukan merupakan Complete Binary Tree karena ada node yang memiliki hanya 1 child.
Gambar 7 menggambarkan contoh dari Complete Binary Tree.
Gambar 9.6 : Complete Binary Tree
> Skewed Binary Tree, atau disebut Binary Tree Miring. Adalah Binary Tree yang bila semua
node, kecuali LEAF pasti memiliki hanya 1 child.
Gambar 9.7 : Skewed Binary Tree
> Full Binary Tree adalah Binary Tree yang semua nodenya, kecuali LEAF harus memiliki 2
Children dan semua subtree harus memiliki path length yang sama. Gambar 9 menunjukan
contoh dari Full Binary Tree.
Gambar 9.8 : Full Binary Tree
Berikut akan dibahas tentang operasi dalam Binary Tree.
Elemen : Elemen dalam Binary Tree disebut dengan node.
Struktur : Binary Tree akan memiliki struktur hirarki, yaitu disbut ROOT dan bila mempunyai
child, maka maksimum child yang dapat dimiliki adalah 2 ( left dan right child )
Operasi :
Traverse ( Ord : Order )
{ Operasi yang melakukan traversal / penelusuran terhadap node-node di dalam TREE.
Parameter pada operasi Traversal adalah Ord, yang menunjukan cara traversal yang
diinginkan , yaitu PreOrder, InOrder, atau PostOrder }.
- Pre – Binary Tree tidak boleh EMPTY.
- Post – Semua node dalam Tree akan dilewati, dan akan menghasilkan list sesuai dengan Order
yang disebutkan dalam parameter Operasi traverse tidak akan mempengaruhi Tree dan posisi
penunjuk Current tidak akan berubah.)
Case Ord of
- PreOrder : Setiap node akan dilewati sebelum melewati node lainnya di dalam subtreenya.
- InOreder : Setiap node akan dilewati setelah melewati subtree kirinya dan sebelum melewati
subtree kanannya. - PostOrder : Setiap node akan dilewati setelah melewati subtree kiri dan subtree kanannya.
Insert ( e:Elemen Type ; Rel : Relative Position, Var fail : BOOLEAN )
{ Operasi untuk menambahkan 1 elemen ke dalam tree, berdasarkan posisi yang diinginkan,
seperti yang ditunjukkan oleh parameter Rel }
- Pre – Jika rel = ROOT maka Binary TREE harus Empty
Jika rel <> ROOT maka TREE harus tidak EMPTY - Post – e akan ditambah kedalam TREE pada posisi tergantung pada rel. Setelah di insert posisi
current akan pindah ke ke e.
Case Rel of
- ROOTV : Insert pada posisi ROOT
- LeftChild : Insert sebagai LeftChild.
- RightChild : Insert sebagai RightChild.
- Parent ; Insert sebagai Parent akan selalu FALSE.
Delete Sub
{ Operasi menghapus subtree yang ditunjuk oleh posisi Current }
- Pre – Binary Tree tidak EMPTY
- Post – Subtree yang ditunjuk oleh posisi current akan dihapus dan Posisi current akan pindah ke
node parent dari node yang dihapus.
Find ( rel : RelPosition; var fail : BOOLEAN )
- Pre – Binary Tree tidak EMPTY
- Post – Current akan pindah ke posisi Rel ( bisa ROOT, PARENT ) LEFTCHILD atau RIGHTCHILD ).
Empty : BOOLEAN
{ Operasi untuk mengetes apakah Binary Tree sudah ada nodenya atau masih kosong }
- pre – Tidak ada
- Post – Jika TREE belum berisi node maka EMPTY akan TRUE
Jika TREE sudah berisi node mnaka EMPTY akan FALSE
Create
{ Operasi untuk menciptakan Binary Tree yang baru dan kosong }
- pre – tidak ada
- post – Binary Tree yang baru dan kosong akan terbentuk
CLEAR
{ Operasi untuk menghapus semua node yang ada di dalam Binary Tree }
- pre – tidak ada
- post – semua node akan terhapus dan binary tree menjadi kosong
Update ( e: Elemen Type )
{ Operasi untuk mengubah isi dari node yang ditunjuk oleh Current , posisi Current setelah operasi
ini tidak berubah }
- pre – Binary Tree tidak EMPTY
- post – isi node yang ditunjuk current akan di update dengan isi dari e
Retrieve ( Var e : Elemen Type )
{ Operasi untuk mengambil isi dari node yang ditunjuk oleh Current }
- pre – tidak ada
- post – e akan berisi data yang pada node ditunjuk oleh Current.
Characteristics ( Var St : status )
{ Operasi untuk menghitung size, tree height dan average length dari Binary Tree }
- Pre – Binary Tree tidak EMPTY
- Post – ST akan berisi informasi mengenai size ( banyak node ), tree height dan average length dari
Binary Tree
Rumus Average Length :
JmlNodeLevel1*1 + JumlNode Level 2*2 + …. + JmlNOde Level n*n
Average : Size
9.2.1 Operasi TRAVERSE ( Ord : Order )
pada bagian ini akan dijelaskan mngenai Operasi Traverse secara lebih rinci. Seperti telah dijelaskan
diatas, bahwa traverse adalah operasi untuk menelusuri node di dalam Binary Tree atau juga berlaku
untuk tree pada umumnya, sesuai dengan order yang diinginkan . order dapat berupa PreOrder,
InOrder, dan PostOrder. Untuk menjelaskan tentang operasi traverse , akan dipergunakan gambar
9.9, yang menggambarkan sebuah Tree ( yang dipergunakan di sini bukan Binary Tree )
Gambar 9.9 : Tree dengan Sub Tree
PreOrder
Penelusuran terhadap Tree secara PreOrder akan melewati setiap node dalam tree sebelum
melewati node lainnya di dlam subtreenya. Dengan melihat gambar 10 di atas, dapat dijelaskan
bahwa PreOrder dari Tree T adalah Root n, kemudian diikuti oleh Sub Tree T1 dalam bentuk
PreOrder, kemudian diikuti oleh SubTree T2 dalam bentuk PreOrder, dstnya sampai Tn.
Untuk memberikan contoh yang lebih nyata, maka Traversal PreOrder terhadap Tree pada gambar 11
akan menghasilkan : B, N, L, G, Q, P, D, X
Gambar 9.10: Contoh Tree untuk Traverse
Berikut algortima untuk penelusuran preorder
PreOrder (ROOT n)
{
If (n != NULL) {
printf(n->info);
PreOrder(n->Left);
PreOrder(n->Right);
}
}
> InOrder
Penelusuran terhadap Tree secara InOrder akan melewati setiap node dalam Tree setelah melewati
subtree kirinya dan sebelum melewati subtree kanannya. Dengan melihat gambar 10 maka dapat
dijelaskan bahwa InOrder dari TREE T adalah sub-tree T1, dalam bentuk InOrder, diikuti oleh Root n,
diikuti T2 dalam bentuk InOrder, sampai Tn.
Gambar 9.11 : Expression Tree
InOrder : 7 + 5 * 6 ( INFIX )
PreOrder : +7 * 5 6 ( PREFIX )
PostOrder : 7 5 6 * + ( POSTFIX)
9.2.2 Implemetasi BINARY TREE
Binary Tree dapat diimplemetasikan baik dengan menggunakan Array ( dengan Array 2 dimensi ,
dimana satu berisi Parent, sedangakan dimensi lainnya berisi Nodenya sendiri ) seperti digambarkan
pada tabel berikut ini, atau dengan menggunakan Link-List ( dengan Double Lik-List, dimana satu
pointer menunjuk ke LeftChild, sedangkan pointer lainnya menunjuk ke RightChild ) seperti
digambarkan pada Gambar 12.
Implementasi Binary Tree dengan Array
Didalam array, indexnya menyatakan nomor node dari tree. Pada node root nomor index array adalah
0. Pada bahasa C, array di-index mulai dari nomor 0, maka binary tree dengan n-node akan diberi
nomor node mulai dari 0 sampai dengan n-1., dengan ketentuan sebagai berikut:
- LeftChild dari suatu node dengan nomor p adalah 2p + 1
- RightChild dari suatu node dengan nomor p adalah 2p + 2
Parent dari suatu node dengan nomor p adalah p-1/2. dalam bahasa C integer dibagi integer
hasilnya adalah integer. Contoh: 1 dibagi 2 hasilnya 0.
Binary tree-nya:
Posisi node dalam array
Implementasi Binary Tree dengan Link-List
- Double Linked List
struct nodetype{
int info; //misal informasi bertipe integer
struct nodetype *left;
struct nodetype *right
};
LC = LEFT CHILD
RC = RIGHT CHILD
0 komentar: