Berapa height dari gambar tree tersebut

TREE

9.1 TREETree 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, yangdapat 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 diberikanmengenai tree ini. Seperti : hubungan orang – tua dengan anak ( satu ibu bisa mempunyai satu ataulebih 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 denganmempergunakan 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 pastimemiliki 1 PARENT yang unique.Contoh : TREE pada gambar 1 diatas, PERUSAHAAN merupakan PARENT dan BAGIANPEMBELIAN, 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 memiliki1 atau lebih CHILD.Contoh TREE pada gambar 1 diatas, BAGIAN PENJUALAN memiliki CHILD sebagai berikutSTAFF ( 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 terdapatpada 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 tertentuContoh TREE pada gambar 2 diatas, node C mempunyai 6 DESCENDAT, yaitu X, M, O, K, R,

> TREE memiliki sifat yang dinamakan RECURSIVE, yang dapat di definisikan bahwa untuksebuah node tertentu , node tersebut beserta semua descedantnya adalahSUBTREE 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, yangmana 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 dapatdidefinisikan memiliki level yang paling rendah yaitu 1 CHILD dari memiliki 1 level lebih tinggi dariPARENTnya, 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.

Gambar 9.4: TREE HEIGHT

9.2 BINARY TREEBinary Tree memiliki semua karakterisktik dari TREE, yang menjadi perbedaan adalah bahwamaksimum CHILD yang bisa dimiliki suatu node dalam BINARY TREE adalah 2 yang disebut LEFTCHILD dari RIGHT CHILD. Gambar memperlihatkan contoh dari Binary Tree. Seperti terlihat padagambar, bahwa node dalam Binary Tree dapat memiliki 0, 1 atau maksimum 2 CHILD, contoh node Wmemiliki 2 CHILD, node Y memiliki 1 CHILD ( yaitu LeftChild, berupa node T ) dan Node tidak memiliki

CHILD.

Gambar 9. 5 : Binary Tree

Binary Tree dapat memiliki beberapa bentuk yaitu :

> Complete Binary Tree atau juga disebut HEAP. Definisi Complete Binary Tree adalahsebuah 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 1child. Subtree dalam heap dapat mempunyai path length yang berbeda. Tree pada contoh 6ini 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 2Children 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 mempunyaichild, 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 Orderyang 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 TreeRumus 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 dijelaskandiatas, bahwa traverse adalah operasi untuk menelusuri node di dalam Binary Tree atau juga berlakuuntuk 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 sebelummelewati node lainnya di dlam subtreenya. Dengan melihat gambar 10 di atas, dapat dijelaskanbahwa 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 preorderPreOrder (ROOT n){If (n != NULL) {printf(n->info);PreOrder(n->Left);PreOrder(n->Right);}

}

> InOrderPenelusuran terhadap Tree secara InOrder akan melewati setiap node dalam Tree setelah melewatisubtree kirinya dan sebelum melewati subtree kanannya. Dengan melihat gambar 10 maka dapatdijelaskan 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 TREEBinary Tree dapat diimplemetasikan baik dengan menggunakan Array ( dengan Array 2 dimensi ,dimana satu berisi Parent, sedangakan dimensi lainnya berisi Nodenya sendiri ) seperti digambarkanpada tabel berikut ini, atau dengan menggunakan Link-List ( dengan Double Lik-List, dimana satupointer menunjuk ke LeftChild, sedangkan pointer lainnya menunjuk ke RightChild ) seperti

digambarkan pada Gambar 12.

Implementasi Binary Tree dengan ArrayDidalam array, indexnya menyatakan nomor node dari tree. Pada node root nomor index array adalah0. 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: