TREE

Rooted Tree ( Pohon Berakar )

Rooted tree adalah suatu tree yang mempunyai akar . Istilah-istilah / unsur - unsur yang ada pada pohon berakar :

1. Akar :dinyatakan dengan lingkar-aN

2. Daun

3. Cabang

4. Tinggi / level / dept / dalamnya suatu vertex

Contoh :

Sifat utama Pohon Berakar

1. Jika Pohon mempunyai Simpul sebanyak n, maka banyaknya ruas atau edge adalah (n-1).

2. Mempunyai Simpul Khusus yang disebut Root, jika Simpul tersebut memiliki derajat keluar >= 0, dan derajat masuk = 0.

3. Mempunyai Simpul yang disebut sebagai Daun / Leaf, jika Simpul tersebut berderajat keluar = 0, dan berderajat masuk = 1.

4. Setiap Simpul mempunyai Tingkatan / Level yang dimulai dari Root yang Levelnya = 1 sampai dengan Level ke - n pada daun paling bawah. Simpul yang mempunyai Level sama disebut Bersaudara atau Brother atau Stribling

5. Pohon mempunyai Ketinggian atau Kedalaman atau Height, yang merupakan Level tertinggi

6. Pohon mempunyai Weight atau Berat atau Bobot, yang banyaknya daun (leaf) pada Pohon.

7. Banyaknya Simpul Maksimum sampai Level N adalah :

2 (N) - 1

8. Banyaknya Simpul untuk setiap Level I adalah

∑ 2 ^{(I -1)}

(I-1)

Pohon Berurut Berakar (Ordered Rooted Tree) adalah pohon berakar yang diberi label berurut secara sistematis. Sistem itu disebut Universal Adress System.

Contoh : dengan memberi nomor urutan; NOL pada akar, kemudian memberikan nomor atas n gugus pada setiap titik simpul yang berjarak n dari akar.

Gambar pohon berurut berakar di atas disebut Lexicographic order.

Pernyataan arimetika (a-b) / [(cxd)+e] dapat digambar dalam Lexicographic.

Terminologi pada Pohon Berakar

Child atau children (Anak) dan parent (orangtua)
Path (lintasan)
Descendant (Keturunan) dan ancestor (leluhur)
Sibling (saudara kandung)
Subtree (subpohon)
Degree (derajat)
Leaf (daun)
Internal nodes (simpul dalam)
Level (tingkat)
Height (tinggi) atau depth (kedalaman)

Child atau children (Anak) dan parent (orangtua)

Simpul y dikatakan anak simpul x jika ada sisi dari simpul x ke y dan Orangtua dari simpul y adalah simpul x.
Pada gambar G1 :

Simpul b, c dan d à anak dari simpul a
Simpul e dan f à anak dari simpul b
Simpul a àorangtua dari simpul b, c dan d
Simpul b à orangtua dari simpul e dan f

Path (lintasan)

Lintasan dari simpul v_i ke simpul v_k adalah runtunan simpul-simpul v₁, v₂ ,…, v_k sedemikian hingga v_i adalah orangtua dari v_i+1 untuk 1 <= i <= K.
Panjang lintasan adalah jumlah sisi yang dilalui dalam suatu lintasan, yaitu k – 1.
Pada gambar G1 :

Lintasan dari a ke j adalah a, b, e dan j
Panjang lintasan dari a ke j adalah 3

Descendant (Keturunan) dan ancestor (leluhur)

x adalah leluhur dari simpul y jika terdapat lintasan dari simpul x ke simpul y di dalam pohon dan keturunan dari simpul x adalah simpul y.
Pada gambar G1 :

Simpul b adalah leluhur dari simpul h
Simpul h adalah keturunan dari simpul b

Sibling (saudara kandung)

Sibling atau saudara kandung adalah simpul yang berorangtua sama
Pada gambar G1 :

Simpul f saudara kandung dari e
Simpul g bukan saudara kandung dari e karena orangtua berbeda

Subtree (subpohon)

Subtree dengan x sebagai akarnya adalah subgraf T’ = (V’,E’) sedemikian hingga V’ mengandung x dan semua keturunannya dan E’ mengandung sisi-sisi dalam semua lintasan yang berasal dari x
Pada gambar G2 :

V’ = {b, e, f, h, i, j}
E’ = {(b, e), (b, f), (e, h), (e, i), (e, j)}
b adalah simpul akar

Degree (derajat)

Derajat sebuah simpul pohon berakar adalah jumlah subtree (jumlah anak) pada simpul tersebut. Derajat pohon berakar merupakan derajat keluar
Pada gambar G1 :

Derajat simpul a : 3, simpul b : 2, simpul c : 0 dan simpul d : 1
Derajat tertinggi (maksimum) : 3

Leaf (daun)

Adalah simpul yang berderajat nol (tidak mempunyai anak)
Pada gambar G1 :

Merupakan daun : simpul c, f, h, i, j, l dan m.

Internal nodes (simpul dalam)

Adalah simpul yang mempunyai anak
Pada gambar di samping :

Merupakan simpul dalam : simpul b, d, e, g dan k

Level (tingkat)

Akar mempunyai level = 0
Level simpul lainnya = 1 + panjang lintasan dari akar ke simpul tersebut (gambar G3).

Height (tinggi) atau depth (kedalaman)

Adalah level maksimum dari suatu pohon
Nama lain : panjang maksimum lintasan dari akar ke daun
Pada gambar di samping :

Pohon mempunyai tinggi atau kedalaman : 4

Ordered Tree (Pohon Berakar Terurut)

Adalah pohon berakar yang urutan anak-anaknya penting. Sistem universal dalam pengalamatan simpul-simpul pada pohon terurut adalah dengan memberi nomor setiap simpulnya seperti penomoran bab (beserta subbab) di dalam sebuah buku.

Pohon m-ary

Adalah pohon berakar yang setiap simpul cabangnya mempunyai banyak n buah anak. Jika m = 2 --> Pohon biner (binary tree).
Pohon m-ary dikatakan pohon penuh (full) atau pohon teratur jika setiap simpul cabangnya mempunyai tepat m buah anak.

Penggunaan pohon m-ary

Penurunan kalimat (dalam bidang bahasa)
Direktori arsip di dalam komputer
Struktur organisasi
Silsilah keluarga (dalam bidang genetika)
Struktur bab atau daftar isi di dalam buku
Bagan pertandingan antara beberapa tim sepak bola
Dll

Struktur direktori arsip di dalam sistem operasi Windows

Jumlah Daun pada Pohon m-ary Penuh

Pada pohon m-ary penuh dengan tinggi (height) h, jumlah daun (leaf) adalah : mh
Jika T bukan pohon m-ary penuh ? jumlah daun ? mh
Jumlah seluruh simpul pohon m-ary pada pohon m-ary penuh dengan tinggi h :
    level 0    --> jumlah simpul = m0 = 1
    level 1    --> jumlah simpul = m1
    level 2    --> jumlah simpul = m2
            …
    level h    --> jumlah simpul = mh
    sehingga jumlah seluruh simpul adalah :

Sehingga jumlah seluruh simpul untuk T bukan pohon m-ary penuh :

Hubungan Jumlah Daun dan Simpul Dalam pada Pohon m-ary Penuh

Misalkan :
i = banyaknya simpul dalam
t = banyaknya simpul daun di dalam pohon biner penuh
m = banyaknya simpul child
Sehingga : (m – 1) i = t – 1

Pohon biner

Dalam ilmu komputer, sebuah pohon biner (binary tree) adalah sebuah pohon struktur data di mana setiap simpul memiliki paling banyak dua anak. Secara khusus anaknya dinamakan kiri dan kanan. Penggunaan secara umum pohon biner adalah Pohon biner terurut, yang lainnnya adalah heap biner.

INFIX, POSTFIX, dan PREFIX

Ada tiga bentuk penulisan notasi matematis di komputer, satu bentuk adalah yang umum digunakan manusia (sebagai input di komputer) yaitu infix, dan dua yang digunakan oleh komputer (sebagai proses), yaitu postfix dan infix. Berikut contoh-contohnya:

1. Konversi Infix ke Postfix

Untuk mengetahui bentuk postfix dari notasi infix, ada tiga cara yang dapat dilakukan, yaitu (1) manual, (2) stack, dan (3) binary tree. Berikut contoh notasi infixnya:

A * ( B + C ) / D ^ E – F

1.a. Cara Manual

Caranya adalah dengan menyederhanakan notasi menjadi dua operand (variabel) dan satu operator, seperti A + B.

Langkah 1: tentukan (berdasarkan derajat operasi) mana yang akan diproses terlebih dulu.

Diperoleh ( B + C ). Jika ( B + C ) dianggap G, maka notasi infix tadi menjadi:

A * G/ D ^ E – F

Langkah 2: dari hasil langkah 1, disederhanakan lagi, kali ini ((berdasarkan derajat operasi)

akan disederhanakan D ^ E. Bila D ^ E dianggap H, maka notasi infix tadi menjadi:

A * G / H – F

Langkah 3: dari hasil langkah 2, disederhanakan lagi, kali ini ((berdasarkan derajat operasi)

akan disederhanakan A * G. Bila A* G dianggap I, maka notasi infix tadi menjadi:

I/ H – F

Langkah 4: dari hasil langkah 3, disederhanakan lagi, kali ini ((berdasarkan derajat operasi)

akan disederhanakan I / H. Bila I / H dianggap J, maka notasi infix tadi menjadi:

J – F

Setelah diperoleh bentuk seperti itu, maka satu per satu kita kembalikan ke notasi semula sambil mengubahnya menjadi notasi postfix.

Langkah 5: hasil akhir J – F, dibentuk postfixnya, menjadi J F –

Langkah 6: J sebenarnya adalah I / H yang jika ditulis dalam bentuk postfix menjadi I H /, lalu

kita gabung dengan hasil di langkah 5 tadi, diperoleh: I H / F –

Langkah 7: H sebenarnya adalah D ^ E yang jika ditulis dalam bentuk postfix menjadi D E ^,

lalu kita gabung dengan hasil di langkah 6 tadi, diperoleh: I D E ^ / F –

Langkah 8: I sebenarnya adalah A * G yang jika ditulis dalam bentuk postfix menjadi A G *, lalu

kita gabung dengan hasil di langkah 7 tadi, diperoleh: A G * D E ^ / F –

Langkah 9: G sebenarnya adalah B + C yang jika ditulis dalam bentuk postfix menjadi B C +, lalu

kita gabung dengan hasil di langkah 8 tadi, diperoleh: A B C + * D E ^ / F –

Dengan demikian, untuk notasi infix: A * ( B + C ) / D ^ E – F maka notasi postfixnya menjadi:

A B C + * D E ^ / F –

Postfix tidak memerlukan tanda kurung, prosesnya berjalan sebagai berikut:

Sama hasilnya pada infix: 2 * ( 3 + 5 ) / 4 ^ 2 – 3 = -2

1.b. Cara Stack

Stack adalah tumpukan (jadi, memori diibaratkan dengan tumpukan) yang memiliki cara kerja, “yang pertama masuk ke kotak, maka akan terakhir kali diambil kembali” atau “first in last out”, atau sebaliknya, “yang terakhir masuk ke kotak, akan diambil yang pertama kali,” atau “last in first out.”

Berikut ini langkah-langkahnya:

1. Proses akan dilakukan dari kiri ke kanan.

2. Bila yang diproses adalah operand, maka tulis di hasil. Di sini operand “A”:

3. Lanjutkan ke operator “*”, karena stack masih dalam keadaan kosong, maka masukkan operator tersebut ke dalam stack;

4. Lanjutkan ke operator “(“, operator ini masukkan (tumpuk) saja ke dalam stack;

5. Lanjutkan ke operand “B”, karena sebagai operand, maka “B” dijadikan hasil saja.

6. Lanjutkan ke operator “+”, operator ini masukkan (tumpuk) saja ke dalam stack;

Bila top stack (posisi teratas tumpukan) adalah “(“ maka apapun operator yang sedang diproses, masukkan saja ke dalam stack.

7. Lanjutkan ke operand “C”, karena sebagai operand, maka “C” dijadikan hasil saja.

8. Lanjutkan ke operator “)“, operator ini akan mengeluarkan seluruh isi stack (mulai dari atas) hingga bertemu operator “(“ yang menjadi pasangannya. Karena di antara “(“ dan “)” hanya ada “+” maka “+” saja yang dijadikan hasil. Tanda kurung dibuang saja.

9. Lanjutkan ke operator “/“, operator ini akan dimasukkan ke dalam stack. Karena di top stack sudah ada isinya, maka bandingkan keduanya. Bila yang akan masuk memiliki derajat yang lebih besar, maka tumpuk saja. Sebaliknya, bila yang akan masuk memiliki derajat yang sama atau lebih kecil, maka keluarkan top stack hingga operator yang berada di top stack berderajat lebih kecil dari operator yang akan masuk.

Karena “/” berderajat sama dengan “*” maka keluarkan top stack (“*”). Karena stack sudah hampa, maka operator “/” dimasukkan ke dalam stack sebagai top stacknya.

10. Lanjutkan ke operand “D”, karena sebagai operand, maka “D” dijadikan hasil saja.

11. Lanjutkan ke operator “^“, operator ini akan dimasukkan ke dalam stack. Karena di top stack sudah ada isinya, maka bandingkan keduanya. Karena “^” berderajat lebih besar dari top stacknya (“/”) maka masukkan (tumpuk) saja.

12. Lanjutkan ke operand “E”, karena sebagai operand, maka “E” dijadikan hasil saja.

13. Lanjutkan ke operator “-“, operator ini akan dimasukkan ke dalam stack. Karena di top stack sudah ada isinya, maka bandingkan keduanya. Karena “-“ berderajat lebih kecil dari “^” maka operator “^” dikeluarkan dari tumpukan dan dijadikan hasil.

Ketika “-“ akan masuk, di top stack kini ada “/” yang berderajat lebih besar dari “-“, akibatnya top stack (“/”) dikeluarkan juga dan dijadikan hasil. Kini “-“ menjadi top stacknya.

14. Lanjutkan ke operand “F”, karena sebagai operand, maka “F” dijadikan hasil saja.

15. Karena proses telah selesai, maka keluarkan seluruh isi stack mengikuti kaidahnya, last in first out. Karena hanya ada “-“ maka hasil akhirnya menjadi:

Hasil ini harus sama dengan postfix yang menggunakan cara manual. Terlihat langkahnya lebih panjang dari cara manual, namun jika telah terbiasa, cara ini dapat dilakukan dengan lebih mudah dari pada cara manual. Kalau dipersingkat, bentuknya menjadi:

1.c. Cara Binary Tree

1. Langkah pertama untuk mengkonversi notasi infix menjadi postfix adalah dengan membuat

struktur pohon binarnya. Langkah pertama untuk membuat struktur pohonnya adalah dengan

menyederhanakan notasi seperti yang pernah dilakukan di cara manual hingga langkah 4, yaitu:

J – F yang struktur pohon binarnya adalah:

2. Jabarkan J, yaitu I / H yang struktur pohon binarnya adalah:

Letakkan struktur pohon binar J ini ke struktur pohon binar yang sudah dibentuk di langkah 1 tadi, jadi, struktur pohon binarnya menjadi:

3. Jabarkan I, yaitu A * G. Sama dengan langkah 2, maka struktur pohon binarnya menjadi:

4. Jabarkan G, yaitu B + C. Sama caranya dengan langkah 2, maka struktur pohon binarnya menjadi:

5. Jabarkan H, yaitu D ^ E. Sama caranya dengan langkah 2, maka struktur pohon binarnya menjadi:

Inilah struktur pohon binar terakhir untuk notasi A * ( B + C ) / D ^ E – F

Lalu, bagaimana menentukan notasi postfixnya ?. Tinggal mengikuti gerakan perjalanan atau kunjungan (traversal) secara post-order saja, yaitu rekursif dari (left-right-root) atau ulangi(kiri, kanan, tengah).

a. Paling kiri adalah A, jadi hasil = A

b. Setelah kiri, kita ke kanan dari A, diperoleh +. Ulangi proses lagi, yang paling kiri adalah B, jadi hasil

= A B

c. Setelah kiri, kita ke kanan dari B, diperoleh C. Karena C merupakan ujung pohon (daun), maka

jadikan hasil. Jadi, hasil = A B C

d. Dari kanan (C) kita ke tengah, diperoleh tanda +. Karena di kiri dan kanan + sudah diproses, maka

jadikan + sebagai hasil. Jadi, hasil = A B C +

e. Kembali ke tengah dari struktur pohon A * +, kita peroleh *. Karena di kiri dan kanan lambang *

sudah diproses, maka jadikan * sebagai hasil. Jadi, hasilnya: A B C + *

f. Kembali ke tengah struktur dari * / ^, yaitu /. Di kiri lambang / sudah diproses, maka kita ke kanan,

sehingga diperoleh ^. Dari sini proses kembali diulang, kiri dari ^ adalah D yang merupakan daun

dari struktur pohon itu. Jadi, hasil = A B C + * D

g. Setelah kiri, kita ke kanan. Diperoleh E, jadi hasilnya = A B C + * D E h. Setelah kanan, kita kembali

ke tengah, diperoleh ^, sehingga hasilnya menjadi A B C + * D E ^

i. Kita kembali ke tengah sebelumnya, yaitu /. Karena di kiri dan kanan lambang / sudah diproses,

maka lambang / menjadi hasil. Jadi, hasil = A B C + * D E ^ /

j. Di kiri dan kanan lambang / sudah diproses, kita kembali ke root (akar, puncak struktur pohon

binar), yaitu -. Di kiri lambang – sudah diproses semua, maka kita ke kanan, diperoleh F yang

merupakan daun. Hasilnya menjadi A B C + * D E ^ / F

k. Terakhir, kita kembali ke puncak (yang merupakan lambang terakhir dalam postfix), hasilnya =

A B C + * D E ^ / F –

Berikut skema pergerakannya:

2. Konversi Infix ke Prefix

Cara mengonversi infix ke prefix dapat dilakukan dengan dua cara, yaitu (a) manual, dan (b) binary tree.

2.a. Cara Manual

Dengan soal yang sama, maka cara manual mengonversi notasi infix ke prefix dimulai sama dengan cara di sub-bab 1.a. proses 1 sampai 4, hingga diperoleh: J – F.

1. Langkah 1: J – F dalam notasi prefix ditulis dengan - J F

2. Langkah 2: J adalah I / H yang notasi prefixnya adalah / I H, sehingga ketika digabung akan menjadi - / I H F

3. Langkah 3: I adalah A * G yang notasi prefixnya adalah * A G, sehingga ketika digabung akan menjadi - / * A G H F

4. Langkah 4: G adalah (B + C) yang notasi prefixnya adalah + B C, sehingga ketika digabung akan menjadi - / * A + B C H F

5. Langkah 5: H adalah D ^ E yang notasi prefixnya adalah ^ D E, sehingga ketika digabung akan menjadi - / * A + B C ^ D E F

Jadi, untuk notasi infix: A * ( B + C ) / D ^ E – F, maka notasi postfix adalah: - / * A + B C ^ D E F

2.b. Cara Binary Tree

Caranya sama dengan cara binary tree sebelumnya. Singkatnya, setelah struktur pohonnya terbentuk, maka berikut ini traversalnya secara pre-order dengan rumus: rekursif(tengah, kiri, kanan), atau rekursif (root, left, right) sebagai berikut:

3. Konversi Prefix ke Infix dan/atau Postfix

Konversi dari prefix ke infix dan/atau postfix bisa dilakukan melalui bantuan manual atau pohon binar. Contoh: notasi prefix: - / * + A B C^ D E F, maka notasi infixnya adalah:

a. Langkah I: cari yang bentuknya: + A B (operator, operand, operand). Diperoleh:

- / * + A B C^ D E F

G H

b. Sederhanakan notasi tersebut menjadi: - / * G C H F

c. Ulangi langkah I hingga menjadi satu operator dan dua operand:

c.1. - / * G C H

c.2. - / I H F

c.3. - J F

d. Jadikan bentuk infix dan kembalikan ke notasi semula (setiap penjabaran diberi tanda kurung): d.1. J – F

d.2. J = (I / H), digabung menjadi: (I / H) – F

d.3. H = (D ^ E), digabung menjadi: (I / (D ^ E)) – F

d.4. I = (G * C), digabung menjadi: ((G * C) / (D ^ E)) – F

d.5. G = (A + B), digabung menjadi (((A + B) * C) / (D ^ E)) - F

Dengan cara yang sama, kita bisa mengalihkan notasi prefix tersebut ke notasi postfixnya, yaitu:

a. Langkah I: cari yang bentuknya: + A B (operator, operand, operand). Diperoleh:

- / * + A B C^ D E F

G H

b. Sederhanakan notasi tersebut menjadi: - / * G C H F

c. Ulangi langkah I hingga menjadi satu operator dan dua operand:

c.1. - / * G C H

c.2. - / I H F

c.3. - J F

d. Jadikan bentuk postfix dan kembalikan ke notasi semula:

d.1. – J F pada prefix menjadi J F - dalam postfix

d.2. J = I H / , digabung menjadi: I H / F -

d.3. H = D E ^, digabung menjadi: I D E ^ / F -

d.4. I = G C *, digabung menjadi: G C * D E ^ / F -

d.5. G = A B +, digabung menjadi A B + C * D E ^ / F -

Dengan cara yang sama pula, mari kita bentuk struktur pohon binarnya.

- JF, pohon binarnya adalah:

J = I H /, sehingga pohonnya menjadi:

H = D E ^, sehingga pohonnya menjadi:

I = G C *, sehingga pohonnya menjadi:

G = A B +, maka pohonnya menjadi:

(ikuti kunjungan/ traversal seperti sebelumnya)

4. Konversi Postfix ke Infix dan/atau Prefix

Sama caranya dengan konversi dari prefix ke infix dan/atau postfix, konversi postfix ke infix atau prefix bisa dilakukan melalui bantuan manual atau pohon binar. Contoh: notasi postfix: A B + C * D E ^ / F -, maka notasi infixnya adalah:

e. Langkah I: cari yang bentuknya: A B + (operand, operand, operator). Diperoleh:

A B + C * D E ^ / F -

G H

f. Sederhanakan notasi tersebut menjadi: G C * H / F –

g. Ulangi langkah I hingga menjadi satu operator dan dua operand:

c.1. G C * H/ F -

c.2. I H / F -

c.3. J F -

h. Jadikan bentuk infix dan kembalikan ke notasi semula (setiap penjabaran diberi tanda kurung):

d.1. J F – jadi ( J – F )

d.2. J = (I / H), digabung menjadi: (I / H) – F

d.3. H = (D ^ E), digabung menjadi: (I / (D ^ E)) – F

d.4. I = (G * C), digabung menjadi: ((G * C) / (D ^ E)) – F

d.5. G = (A + B), digabung menjadi (((A + B) * C) / (D ^ E)) - F

Dengan cara yang sama, kita bisa mengalihkan notasi postfix tersebut ke notasi prefixnya, yaitu:

e. Langkah I: cari yang bentuknya: A B + (operand, operand, operator). Diperoleh:

A B + C * D E ^ / F -

G H

f. Sederhanakan notasi tersebut menjadi: G C * H / F –

g. Ulangi langkah I hingga menjadi satu operator dan dua operand:

c.1. G C * H / F -

c.2. I H / F -

c.3. J F –

h. Jadikan bentuk prefix dan kembalikan ke notasi semula:

d.1. J F - pada postfix menjadi - J F dalam pretfix

d.2. J = / I H , digabung menjadi: - / I H F -

d.3. H = ^ D E, digabung menjadi: - / I ^ D E F -

d.4. I = G C *, digabung menjadi: - / * G C ^ D E F -

d.5. G = A B +, digabung menjadi - / * + A B C ^ D E F -

Dengan cara yang sama pula, mari kita bentuk struktur pohon binarnya.

J F -, pohon binarnya adalah:

J = / I H/, sehingga pohonnya menjadi:

H = ^ D E, sehingga pohonnya menjadi:

I = * G C, sehingga pohonnya menjadi:

G = + A B, maka pohonnya menjadi: