TREE & BINARY TREE (Pohon dan Pohon Biner)

Posted by : Panji Maulana Putra Monday, November 27, 2017

TREE

Pohon (Tree) adalah graf terhubung yang tidak mengandung sirkuit. Karena merupakan graf terhubung maka pada pohon selalu terdapat path atau jalur yang menghubungkan kedua simpul di dalam pohon. Pohon dilengkapi dengan Root (akar).

Contoh : Pohon berakar T

Sifat utama pohon berakar :

1. Jika pohon mempunyai simpul sebanyak n, maka banyaknya ruas adalah (n-1). Pada contoh : banyak simpul adalah 8 maka banyaknya ruas adalah 7.

2. Mempunyai simpul khusus yang disebut Root (Akar), jika simpul tersebut memiliki derajat keluar ³ 0 dan derajat masuk = 0. Simpul P merupakan root.

3. Mempunyai simpul yang disebut Leaf (Daun), jika simpul tersebut memiliki derajat keluar = 0 dan derajat masuk = 1. Simpul R, S, V, W merupakan daun pada pohon T.

4. Setiap simpul mempunyai tingkatan (level), dimulai dari root dengan level 0 sampai dengan level n pada daun yang paling bawah.

Pada contoh :

P mempunyai level 0

Q, T mempunyai level 1

R, S, U mempunyai level 2

V, W mempunyai level 3

Simpul yang mempunyai level yang sama disebut Bersaudara (Brother)

5. Pohon mempunyai ketinggian (kedalaman / height) yaitu level tertinggi +1. Ketinggian pohon T adalah 3+1 = 3

6. Pohon mempunyai berat (bobot / weight) yaitu banyaknya daun pada pohon. Berat pohon T adalah 4

POHON BINER (BINARY TREE)

Pohon binar adalah himpunan simpul yang terdiri dari 2 subpohon (yang disjoint / saling lepas) yaitu subpohon kiri dan subpohon kanan.

Setiap simpul dari pohon binar mempunyai derajat keluar maksimum = 2.

Pendefinisian pohon binar bersifat rekursif. Pohon binar acapkali disajikan dalam bentuk diagram.

Untuk menggambarkan suksesor kiri dan suksesor kanan, dibuat garis ke kiri bawah dan ke kanan bawah. B adalah suksesor kiri dari A, sedangkan C adalah suksesor kanan dari A. Subpohon kiri dari A mengandung simpul B, D, E dan F, sedangkan subpohon kanan mengandung simpul C, G, H, J, K dan L.

Pada contoh di atas :

Root adalah A

Simpul yang mempunyai 2 anak adalah simpul A, B, C dan H.

Simpul yang mempunyai 1 anak adalah simpul E dan J.

Simpul yang tidak mempunyai anak disebut daun (terminal) adalah D, F, G, K dan L.

Perhatikan pohon T1 dan T2 dan T3 ini :

Dua pohon binar disebut similar jika mempunyai struktur (bangun/susunan) pohon yang sama.

Contoh : Pohon binar T1 dan T2 adalah similar.

Kedua pohon binar disebut Salinan (Ekivalen/Copy) jika :

1. Mempunyai struktur pohon yang sama (similar)

2. Elemen yang sama pada simpul yang bersesuaian.

Contoh : Pohon binar T1 dan T3 adalah ekivalen

TERMINOLOGI PADA POHON BINAR

Terminologi hubungan keluarga banyak digunakan dalam terminologi pada pohon binar. Misalnya istilah anak kiri dan anak kanan, untuk menggantikan suksesor kiri dan suksesor kanan, serta istilah ayah untuk pengganti predesesor.

K misalnya adalah keturunan kanan dari D, tetapi bukan keturunan dari F, E ataupun M. Simpul G adalah ayah dari K dan L. Di sini K dan L adalah bersaudara, masing-masing anak kiri dan anak kanan dari G.

Garis yang ditarik dari Simpul N ke suksesor disebut Ruas dan sederetan ruas yang berturutan disebut Jalur atau path. Sebuah jalur yang berakhir pada daun (terminal) disebut Cabang.

Garis AD maupun GL adalah contoh ruas. Barisan ruas (AD, DG, GL) adalah jalur dari simpul A ke simpul L, jalur tersebut merupakan cabang, karena berakhir di simpul terminal (daun ) L.

Dari contoh pohon binar di atas :

Root : A

Simpul Daun adalah : F, K, L dan M

Level 0 adalah simpul A

Level 1 adalah simpul D dan E

Level 2 adalah simpul F, G dan M

Level 3 adalah simpul K dan L

Ketinggian (kedalaman) = 3 + 1 = 4

Berat (bobot) = 4

Cabang (AD, DG, GK) ataupun (AD, DG, GL) mengandung simpul dengan jumlah maksimum, yakni = 4, sedangkan cabang (AE, EM) serta (AD, DF) hanya mengandung 3 simpul.

KETINGGIAN MINIMUM DAN MAKSIMUM POHON BINAR

Jika banyaknya simpul = N, maka :

1. Ketinggian Minimum adalah : H_min= INT(²log N) + 1

2. Ketinggian Maksimum adalah : N

Contoh : untuk N = 8

Ketinggian Minimum adalah : H_min= INT(²log N) + 1

= INT(²log 8) + 1

= INT(²log 2³) + 1

= INT(3) + 1

= 3 + 1

= 4

Ketinggian Maksimum adalah : 8

PENYAJIAN POHON BINAR DALAM MEMORI

Penyajian pohon binar dalam memori dengan dua cara, yaitu :

1. Penyajian Kait (link)

2. Penyajian Sequential.

1. PENYAJIAN KAIT

Kalau tidak dinyatakan lain, suatu pohon binar T akan disimpan dalam memori secara penyajian kait.

Penyajian ini menggunakan tiga array sejajar INFO, LEFT dan RIGHT, serta variabel penuding ROOT.

Masing-masing simpul N dari pohon T berkorespondensi dengan suatu lokasi K, sedemikan sehingga :

(1) INFO(K) berisi data pada simpul N.

(2) LEFT(K) berisi lokasi dari anak kiri simpul N.

(3) RIGHT(K) berisi lokasi dari anak kanan simpul N.

Skema Penyajian Kait dari Pohon T

1. PENYAJIAN SEQUENTIAL

Penyajian pada pohon binar T ini hanya menggunakan sebuah array linear tunggal TREE sebagai berikut :

1. Akar R dari pohon T tersimpan sebagai TREE[1]

2. Jika simpul N menduduki TREE[K] maka anak kirinya tersimpan dalam TREE[2*K] dan anak kanannya dalam TREE[2*K+1]

Dapat dilihat bahwa penyajian membutuhkan 14 lokasi dalam array TREE, meskipun T hanya mempunyai 9 simpul. Kenyataannya, bila kita memasukkan elemen nol sebagai suksesor dari simpul terminal, dibutuhkan TREE[29] untuk suksesor kanan dari TREE[14].

PENYAJIAN POHON UMUM SECARA POHON BINAR

Kita dapat menyajikan pohon umum secara pohon binar dengan algoritma sebagai berikut :

1. Tambahkan ruas baru yang menghubungkan 2 simpul bersaudara yang berdampingan, lalu kita hapus ruas dari simpul ayah ke anak, kecuali ruas ke simpul anak paling kiri.

2. Rotasikan sebesar 45° , searah putaran jarum jam terhadap pohon hasil langkah pertama.