Pohon Biner

Struktur Data - Pertemuan 14

"Pohon Biner"

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).

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

Karakteristik Pohon Binar (Binary Tree) :

• Setiap Simpul paling banyak hanya memiliki dua buah anak
• Derajat Tertinggi dari setiap Simpul adalah dua.
• Dibedakan antara Cabang Kiri dan Cabang Kanan.
• Dimungkinkan tidak mempunyai Simpul

Istilah

• Pohon :susunan dari satu atau lebih simpul (node) yang terdiri dari satu simpul khusus yang disebut akat (root) sedang sisanya membentuk subtree dari akar.
• Simpul/Vertex/Node : A, B,…, N
• Busur/Edge/Arc : garis yang menghubungkan antar simpul
• Superordinat/Father/Parent dan Subordinat/Son/Children.i. Simpul A merupakan superordinat bagi simpul B, C, D
  ii. Simpul B, C,D merupakan subordinat bagi simpul A
• Root/Akar : simpul yang tidak mempunyai superordinat. Pada gambar diatas : A.
• Leaf/Daun : simpul yang tidak mempunyai subordinat. Pada gambar diatas : C, E, G, I, J, K, L, M, N.
• Level/Tingkat : Simpul A berada pada level 0, simpul B, C, D berada pada level 1, dst.
• Depth/kedalaman : Level tertinggi dari suatu pohon. Pada gambar 1, depth = 3.
• Derajat/Degree sebuah simpul jumlah simpul subordinat dari simpul tersebut.
• Derajat/degree sebuah pohon adalah derajat tertinggi dari derajat simpul yang ada pada pohon tersebut.

M-ary atau K-ary. M atau K menyatakan derajat dari pohon.

Link 

 Link : Pointer yang digunakan untuk menunjuk simpul subordinat

Null-Link : link yang bernilai Null, yaitu link yang tidak menunjuk subordinat

Bukan Null-Link/Busur : link yang menunjuk simpul subordinat.

Jika ,

n : jumlah simpul

k : derajat pohon

maka berlaku hubungan :

Jumlah Link : n x k

Jumlah Null-Link : n(k-1)+1

Jumlah Bukan Null-Link : n-1

Dari gambar 4, diperoleh :

n = 7, k = 3

Jumlah Link : 7 x 3 = 21

Jumlah Null-Link : 7(2)+1 = 15

Jumlah Bukan Null-Link : 7-1 = 6

Full Binary Tree

Pada pohon Full Binary Tree berlaku :

1. Pada level k, jumlah simpul = 2k

2. Pohon dengan kedalaman d, jumlah simpul = 2(d+1)-1

3. Pohon dengan level k,

a. Jumlah simpul daun = 2k

b. Jumlah simpul bukan daun = 2k-1

4. Bila jumlah seluruh simpul = n,

a. Kedalaman pohon = log2(n+1)-1