POHON ( TREE ) Pengertian Pohon Pohon atau tree adalah salah satu bentuk konsep struktur data yang terdiri dari akar dan simpul-simpul yang berada dibawah akar. tingkat I tingkat 2 tingkat 3 tingkat 4 Gambar Tingkat Pohon Tree Selain istilah tingkat juga ada yang disebut dengan derajat ( degree ). Derajat merupakan banyak tingkat simpul turunan dari satu simpul tertentu, misalkan simpul tertentu, misalkan simpul “ Ketua Umum” memiliki derajat 3, simpul “ wakil Ketua I “ memiliki derajat 2 dan seterusnya. Simpul yang memiliki derajat 0 disebut dengan daun ( leaf), pada struktur data pohon dikenal istilah yang disebut kedalaman ( depth ). Sedangkan sebuah simpul yang ada diatas sebuah simpul lain disebut sebagai ancestor. Kumpulan pohon disebut dengan hutan ( forest ). Ada beberapa cara untuk menggambarkan sebuah pohon yaitu : Keterangan Representasi Pohon Menggunakan graph Menggunakan diagram venn Menggunakan notasi kurung ( A, ( B ( E, F ), c ( G), D( H, I ) ) Pohon biner lengkap ( complete binary tree ) yaitu pohon bier yang setiap simpulnya mempunyai dua buah simpul turunan. Pohon biner condong kiri ( leaft skewed binary tree ) Pohon biner condong kanan ( right skewed binary tree ) Pohon biner sembarang Operasi Pada Pohon Biner Operasi pada pohon biner : - Operasi yang dapat dilakukan pada pohon biner antara lain kunjungan terhadap simpul simpulnya. Jenis-jenis kunjunfan pada pohon biner antara lain : - Preorder - Inorder - Postorder - Level order Pre Order Kunjungan preorder merupakan kunjungan pada pohon biner yang dimulai dari akar kemudian ke subpohon kiri, setelah subpohon kiri dikunjungi baru subpohon kanan dikunjungi. Maka dengan kunjungan preorder akan menghasilkan urutan simpul yang dikunjungi A – B – D – E – C – F – G – H In Order Kunjungan inorder merupakan kunjungan pada pohon biner yang dimulai dari simpul-simpul turunan subpohon kiri, akar, baru kemudian simpul-simpul turunan pada subpohon kanan. Maka kunjungan inoeder akan menghasilkan urutan simpul : D – B – E – A – F – C – H – G Post Order Kunjungan post order merupakan kunjungan pada pohon biner yang dimulai dari simpul-simpul turunan subpohon kiri, baru kemudian simpul-simpul turunan pada subpohon kanan, Kemudian akar, misalkan terdapat sebuah pohon biner seperti pada gambar Post Order akan menghasilkan urutan simpul yang dikunjungi : D – E – B – F – H – G – C – A Level Order Kunjungan level order merupakan kunjungan pada pohon biner yang dimulai dari simpul pada tingkat 1 kemudian simpul-simpul pada tingkat 2 dan seterusnya., dimulai dari simpul paling kiri ke kanan. Kunjungan level order akan menghasilkan urutan simpul A- B- C – D – E – F – G – H Implementasi Pohon Biner Pointer sub pohon kanan pointer subpohon kiri sehingga jika di implementasikan sebagai pohon , simpul-simpul itu akan menjadi seperti : Null Null Null Null Null Null Null ( Representasi Pohon Biner ) Pohon Tree Struktur data berbentuk Tree dapat diartikan bahwa relasi antar elemen adalah hierarkis. Selalu terdapat satu elemen sebagai akar ( roots ) dan diikuti oleh elemen-elemen sebagai cabang-cabang. Record mahasiswa dengan atribut : Nomorpokok, Nama, Alamat, Jurusan, Hierarki mahasiswa dapat ditulis dalam bentuk Record terstruktur : 01 Mahasiswa 02 Nomorpokok 02 Nama 03 Depan 03 Famili 03 Alias 02 Jurusan 02 Alamat 03 Jalan 03 Area 04 Kota 04 Negara 04 Kodepos Contoh : Hierarki dipergunakan juga untuk menggambarkan formulasi aljabar : f(x) = ( 2x + y ) ( a – 7b )3 seperti : level 0 v0 e2 e0 e1 Level 1 V1 v2 v3 Level 2 Level 3 Tree atau Pohon Termasuk struktur data non linear. Tree , M-Ary tree dan Binary Tree Contoh sebuah Tree : Level 0 V0 e2 e0 e1 Level 1 v3 v1 v2 level 2 Level 3 Ada banyak nama, istilah dan pengertian yang digunakan untuk mengilustrasikan atau menyatakan ataupun yang dikaitkan dengan pohon , antara lain : a. Tree ( pohon ) dan Graph ( Grafik ) b. Simpul ( Vertex, Node ), dan Busur ( Edge, Arch ) c. Superordinat dan Subordinat, father dan son, parent dan children d. Root ( akar ) dan Leap ( Daun ) e. Level ( Tingkat ) dan Depth ( kedalaman ) f. Degree ( derajat simpul dan Degree pohon g. M- ary tree dan Binary tree. h. Link dan Null- Link. Istilah-istilah diatas dapat diuraikan sebagai : a. Tree dan graph Tree merupakan bagian dari Graph T =  G b. Simpul dan Busur Pohon merupakan kumpulan dari simpul dan busur, dimana salah satu simpul merupakan akar ( Root ) dan simpul – simpul lain membentuk suatu subpohon atau subtree yang dapat disimbolkan sebagai berikut : T = ( V, E ) Dimana : V = Vertex, atau Node atau titik atau simpul. E = Edge, atau Arc atau Busur. Simpul Disini digunakan istilah vertex, yang disimbolkan dengan huruf besar. Tree terdiri dari 14 buah simpul ( n = 14 ) yaitu simpul A sampai dengan simpul N, atau V0 sampai dengan v13, yang disimbolkan sebagai berikut : V = { v0 , v1 , v2 , ………., v13 } Yang maksudnya v terdiri dari atau merupakan kumpulan dari v0 , v1, ….. Busur Disini digunakan istilah Edge yang disimbolkan dengan huruf E besar, Tree terdiri dari 13 buah busur ( m = 12 ) yaitu e 0 sampai dengan e13 yang disimbolkan sebagai berikut : E = { e0 , e1, e2, ………, e12 } Yang maksudnya E teridiri dari atau merupakan kumpulan dari e0 , e1, e2, ………, e12. Bila jumlah simpul dinyatakan dengan : n Dan jumlah busur dinyatakan dengan : m Maka selalu berlaku hubungan : m = n -1 c. Superordinat Untuk contoh pohon diatas : - Simpul B merupakan superordinat simpul E dan F. - Simpul E dan F mempunyai superordinat simpul B Superordinat diistilahkan dengan Father ( Bapak ) dan Subordinat diistilahkan dengan Son ( Anak ). Ada yang mengistilahkan dengan Parent dan Children. d. Root ( Akar ) dan Leaf ( Daun ) Root ( Akar ) adalah simpul yang tak mempunyai superordinat. Untuk pohon yang dicontohkan diatas maka akar adalah simpul A. Leaf ( Daun ) adalah simpul yang tak mempunyai subordinat. Untuk pohon yang dicontohkan diatas, maka daun adalah : simpul C, E, G, I, J, K, L, M, N e. Level ( Tingkat ) dan Depth ( Kedalaman ) Akar dinyatakan berada pada level 0, atau disebut level 1. Setiap turun satu subordinat, level bertambah 1. Depth ( Kedalaman ) disebut ketinggian ( height ) Suatu pohon yang mempunyai level teratas atau level tertinggi = k , maka disebut kedalamannya = k. Untuk pohon yang dicontohkan diatas, karena level tertinggi adalah 3, maka depth = 3 f. Degree ( derajat ) sebuah simpul Degree sebuah simpul menyatakan jumlah simpul subordinat dari simpul tersebut: Untuk pohon yang dicontohkan pada gambar dibawah ini : Simpul A : degree = 3 Simpul B : degree = 2 Simpul C : degree = 0 Degree sebuah pohon Degree sebuah pohon adalah degree tertinggi ( yang mungkin ada ) dari degree simpul yang ada. Untuk pohon yang dicontohkan : Contoh sebuah pohon TREE Derajat = 3 Link, Null- Link dan Bukan Null – Link Link, adalah pointer yang digunakan untuk menunjuk simpul subordinat. Untuk pohon biner yang dicontohkan pada Gambar dibawah ini, maka setiap simpul mempunyai 2 link, sehingga jumlah link = 9 * 2 = 18 pada gambar 3a. Null- Link Null- Link adalah Link yang bernilai Null, yaitu link yang tidak menunjuk simpul subordinat. Untuk pohon biner yang dicontohkan pada gambar 3b, maka jumlah Null- Link ada sebanyak 10 buah. Bukan Null – Link atau Busur Bukan Null-link adalah Link yang menunjuk simpul subordinat atau link yang menghubungkan dua buah simpul yang biasanya disebut busur. Untuk pohon biner yang dicontohkan pada Gambar 3° tersebut, jumlah link yang bukan Null-Link yang disebut busur, ada 8 buah. Gambar 3a Gambar 3b Gambar 3c Contoh : Soal-1. Sebuah pohon M-ary dengan 10 buah simpul. Bila M = 3, maka Ditanya berapa jumlah Null-Link: Beberapa contoh Gambar Pohon 3- ary dengan 10 simpul : Gambar 4a Gambar 4b Pohon 3- ary Skewed Right ( Skewed to the right ) Jawab : Pohon dengan M = 3 Jumlah simpul 10, jadi : n = 10 Jumlah Null - Link = n * ( M – 1 ) + 1 = 10 * ( 3 – 1 ) + 1 = 10 * 2 + 1 = 21 Contoh Soal : Beberapa contoh gambar pohon biner dengan 10 simpul. Gambar 5a Gambar 5b Pohon Biner Skewed Right (Skewed to the right ) Jawab : Pohon Biner, berarti M = 2 Jumlah simpul 10, Jadi : n = 10 Jumlah Null – Link = n * ( M – 1 ) + 1 = 10 * ( 2 – 1) + 1 = 10 * 1 + 1 = 11 Jumlah Null – Link = n * ( M – 1 ) + 1 Jumlah Ditambah 1 Simpul karena simpul terakhir ada tambah 1 Terlihat jelas pada gambar Bahwa setiap simpul ada 1 null link, kecuali simpul terakhir ada 2 link jadi 10 * 1 + 1 = 11 Contoh Soal : Pada sebuah pohon biner, salah satu simpulnya bernomor = 75. Ditanya nomor simpul superordinat simpul tersebut. Jawab : Dari gambar terlihat bahwa nomor simpul superordinat ( parent ) nya = 37 n ? 37 Dengan matematika : 2n +1 = 75 2n = 74 n = 37 2n 2n + 1 75 74 75 Gambar 6a Gambar 6b Gambar 6c Contoh Soal : Diketahui sebuah Phon Biner kedalaman d = 3 Ditanya : a. Maksimum jumlah simpul pada level 3. .............................. Jawab : 8 b. Minimum jumlah simpul pada level 3. ............................. Jawab : 1 c. Maksimum jumlah seluruh simpul sampai dengan level 3. ... Jawab : 15 d. Minimum jumlah seluruh simpul sampai dengan level 3. .... Jawab : 4 Keterangan : Ada banyak sekali bentuk pohon biner yang mempunyai kedalaman = 3 Beberapa diantaranya diperlihatkan pada gambar : Gambar 6a Gambar 6b Gambar 6c Gambar 6d Gambar 6e Gambar 6f Gambar 6g Gambar gh Gambar 6i Dari gambar diatas, dapat dilihat jawaban untuk masing-masing pertanyaan sebagai berikut : a. Maksimum jumlah simpul pada level 3 adalah = 8 ( lihat gambar 6a) b. Minimum jumlah simpul pada level 3 adalah = 1 ( lihat gambar 6d, e, f, g, h, i ) c. Maksimum jumlah seluruh simpul sampai dengan level 3 adalah = 15 ( gambar 6a ) d. Minimum jumlah seluruh simpul sampai dengan level 3 adalah = ( lihat gambar 6g, h, i ). Level Maksimum jumlah simpul pada level Maksimum jumlah seluruh simpul sampai dengan level 0 1 1 1 2 3 2 4 7 3 8 15 4 16 31 5 32 63 6 64 127 7 128 255 8 256 511 9 512 1023 10 1024 2047 11 2048 4095 12 4096 8191 13 8196 16383 14 16394 32767 . . . . . . . . . k 2^k 2^(k+1)-1 Dari tabel diatas dapat dijawab : a. Maksimum jumlah simpul pada level 9 = 512 b. Maksimum jumlah seluruh simpul sampai dengan level 9 = 1023 Sedangkan : c. Minimum jumlah simpul pada level 9 = 1 d. Minimum jumlah seluruh simpul sampai dengan level 9 = 10 Sampai level 14 jumlah simpul maksimum = 32767. Ingat batas maksimal bilangan signed integer 16 bit.

Pohon  atau tree adalah salah satu bentuk konsep struktur data yang terdiri dari akar dan simpul-simpul yang berada dibawah akar.

                  Selain istilah tingkat juga ada yang disebut dengan derajat ( degree ).

                  Derajat merupakan banyak tingkat simpul turunan dari satu simpul tertentu, misalkan  simpul tertentu, misalkan simpul “ Ketua Umum” memiliki derajat 3, simpul “ wakil Ketua I “ memiliki derajat 2 dan seterusnya.

                  Simpul yang memiliki derajat 0 disebut dengan daun ( leaf), pada struktur data pohon dikenal istilah yang disebut  kedalaman  ( depth ).

                  Sedangkan sebuah simpul yang ada diatas sebuah simpul lain disebut sebagai ancestor.

Operasi pada pohon biner :

-          Operasi yang dapat dilakukan pada pohon biner antara lain kunjungan terhadap simpul simpulnya.

Jenis-jenis kunjunfan pada pohon biner antara lain :

-          Preorder

-          Inorder

-          Postorder

-          Level order

            Kunjungan preorder merupakan kunjungan pada pohon biner yang dimulai dari akar kemudian ke subpohon kiri, setelah subpohon  kiri  dikunjungi  baru  subpohon  kanan dikunjungi.

A – B – D – E – C – F – G – H

          Kunjungan inorder merupakan kunjungan pada pohon biner yang dimulai dari simpul-simpul turunan subpohon kiri, akar, baru kemudian simpul-simpul turunan pada subpohon kanan.

 

                                            v₀

 

                                         e₂

                    e₀                              e₁                     

C

                                                                                         Level 1

                    V₁                    v₂                                  v₃

                                                                                            Level 2

                                                                                                     Level 3

                                                                                         Level 0

                                           V₀                           e₂                                

                                e₀                    e₁                                                                            Level 1

                                                                                                                    v₃

                                   v₁                    v₂                                                                              level 2

                                                                                                                             Level 3

Ada banyak nama, istilah dan pengertian yang digunakan untuk mengilustrasikan atau menyatakan  ataupun yang dikaitkan dengan pohon , antara lain :

c.       Superordinat dan Subordinat, father dan son, parent dan children

g.      M- ary tree dan Binary tree.

h.      Link  dan  Null- Link.

Tree  merupakan  bagian  dari Graph

 

      T = Î G

Pohon merupakan kumpulan dari simpul dan busur, dimana salah satu simpul merupakan akar  ( Root )  dan simpul – simpul  lain  membentuk  suatu subpohon  atau  subtree yang dapat disimbolkan sebagai berikut :

      T =  ( V, E )

Dimana :

              V = Vertex,  atau  Node  atau titik  atau  simpul.

              E =  Edge,  atau  Arc  atau Busur.

Disini  digunakan istilah vertex, yang disimbolkan dengan huruf  besar.   Tree terdiri  dari 14  buah  simpul  ( n = 14 ) yaitu simpul A sampai dengan simpul N, atau V₀  sampai dengan  v₁₃, yang disimbolkan sebagai berikut :

        V  =  { v₀ , v₁ , v₂ , ……….,  v₁₃ }

Yang maksudnya  v  terdiri dari atau merupakan kumpulan  dari  v₀ , v₁, …..

Disini digunakan istilah Edge yang disimbolkan dengan huruf  E  besar, Tree terdiri dari 13 buah busur ( m = 12 )  yaitu  e ₀  sampai dengan  e₁₃  yang disimbolkan sebagai berikut :

                  E =  {  e₀ , e₁,  e₂,  ………, e₁₂ }