Struktur Pohon ( TREE )
Modul Kuliah Struktur Data
TREE (Struktur Pohon) TREE merupakan struktur data yang menyatakan simpul-simpul data sebagai hubungan hirarki (parent and child structured), dimana simpul yang mempuyai derajat/hirarki lebih tinggi berada di atas, contoh : • Silsilah keluarga • Struktur organisasi
A B D
0 C
E G
1 F
H
2 I
KLASIFIKASI TREE
3
Istilah-istilah dalam TREE • A merupakan simpul AKAR/ROOT • D, G, H, & I disebut simpul luar/DAUN • B, C, E, F disebut simpul dalam • 0, 1, 2, 3 merupakan level/tingkatan kedalaman setiap simpul • Level yang sama merupakan generasi yang sama • Edge/sisi merupakan garis yang menghubungkan simpul yang satu dengan yang lain. • A – B – E – G atau A – C – F – I, disebut lintasan (PATH) • Tinggi simpul : panjang lintasan dari simpul tersebut ke daun keturunannya yang paling jauh • Kedalaman (level) simpul : panjang lintasan dari simpul tersebut ke AKAR
1. TREE UMUM Tree umum adalah tree dimana jumlah anak/keturunan masing-masing simpulnya 0, 1, 2,…, N. 2. BINARY TREE Binary Tree adalah tree dimana jumlah anak/keturunan masing-masing simpulnya 0, 1 atau 2. KLASIFIKASI BINARY TREE 1. Strictly Binary Tree / 2-Tree / Extended B-Tree : Pohon Biner yang setiap simpulnya mempunyai ANAK 0 atau 2. Jika Jumlah daun = N, maka jumlah keseluruhan simpul dalam tree tersebut adalah 2N – 1 simpul. 2. Pohon Biner Komplit : Merupakan pohon seimbang komplit, dimana setiap DAUN-nya memiliki level/kedalaman yang sama (misalkan d) dan setiap simpul yang bukan DAUN memiliki ANAK 2. ∑(DAUN) = 2d, dan ∑(Simpul dalam) = 2d – 1.
[email protected]
Halaman
1
Struktur Pohon ( TREE )
Modul Kuliah Struktur Data
A
A
B
C
B E
D
C
D
Extended B-Tree
E
G
F
Pohon Biner Komplit
3. Pohon Biner Hampir Komplit : Pohon Biner yang mempunyai DAUN pada level d atau d – 1, dan jika setiap simpul keturunan kanan berada pada level d, maka setiap simpul keturunan kiri yang merupakan daun juga memiliki level d atau d + 1. A B
C
D
E I
H
G
F
Pohon Biner Hampir Komplit
TRAVERSING BINARY TREE Metode pembacaan/kunjungan pada sebuah Tree dapat dilakukan dengan beberapa cara, yaitu : 1. PREORDER
:R
T1
T2
2. INORDER
: T1
R
T2
T2
R
3. POSTORDER : T1 A
R
T1
T2
Informasi yang diperoleh dari operasi travesing thd tree di samping adalah:
B D
C E
[email protected]
F
G
PREORDER
:
ABDECFG
INORDER
:
DBEAFCG
POSTORDER :
DEBFGCA
Halaman
2
Struktur Pohon ( TREE )
Modul Kuliah Struktur Data
APLIKASI TREE 1. Mengubah Notasi Infix Menjadi PreFix dan PostFix Bila model 2-Tree digunakan untuk mempresentasikan ekspresi aritmatika dalam notasi Infix, maka pohon dibentuk dengan ketentuan sebagai berikut : • Simpul dalam tempat meyimpan operator • Simpul luar (daun) tempat meyimpan operand • Operand kiri menjadi anak kiri dan Operand kanan jadi anak kanan dari Operatornya • Evaluasi ekspresi dilakukan mulai Operator yang mempunyai derajat kedalaman tertinggi hingga terendah, dengan mengoperasikan dua Operand terhadap Operator orang tuanya. Contoh : Notasi Infix
: A*B–C
Notasi Infix
: A + B * C – (D / E * F + G)
Notasi Postfix : A B * C –
Notasi Postfix : A B C * + D E / F * G + –
–
–
*
C B
A Keterangan :
+ A
+ *
B
G
* C
/
F
Simpul Luar (DAUN) Simpul Dalam
D
E
Latihan : Buatlah Pohon Biner dari ekspresi aritmatika berikut ini, • P*Q/R–S*T+U/V • A * (B – C) / (D + E) * F * G • V * (W / (X – (Y + Z))) • (2 * 3 / 2 – 7) * (9 + 5 / 3)
.
[email protected]
Halaman
3
Struktur Pohon ( TREE )
Modul Kuliah Struktur Data
PANJANG LINTASAN Panjang Lintasan Luar (LE) adalah jumlah panjang lintasan dari akar sampai ke semua simpul luar (DAUN) Panjang Lintasan Dalam (LI) adalah jumlah panjang lintasan dari akar sampai kesemua simpul dalam Panjang Lintasan Luar berbobot (P) adalah jumlah panjang lintasan dari akar sampai ke semua simpul luar (DAUN) dikalikan dengan bobot masingmasing DAUN P = ∑ (bobot masing-masing DAUN * Level daun tersebut ) Contoh: – *
3
LE
= =
2+2+1 5
LI
=
1
P
= = =
8*2+2*2+3*1 16 + 4 + 3 23
2
8
Latihan: Hitunglah:
– +
a. LE = …. ?
+
b. LI = …. ? 2
*
7
*
c. P 1
3
/ 2
= …. ?
4 3
Tree Dengan Panjang Lintasan Luar Berbobotnya (P) Minimum Untuk membentuk 2-Tree dengan P minimum dapat dilakukan dengan menerapkan algoritma HUFFMAN.
Contoh: Bentuklah 2-tree dengan bobot masing-masing daunya dalah: 6, 5, 3, 7, 10. Sehingga P-nya minimum.
[email protected]
Halaman
4
Struktur Pohon ( TREE )
Modul Kuliah Struktur Data
Algoritma HUFFMAN Digunakan untuk mebentuk 2-tree dengan Panjang Lintasan Luar Berbobotnya minimum, dengan langkah-langkah sebagai berikut : 1. Pilih 2 DAUN (Child) atau AKAR (Parent) dengan nilai terkecil 2. Padukan kedua DAUN atau AKAR tersebut menjadi sebuah Sub Tree dengan nilai AKAR (Parent) hasil penjumlahan kedua DAUN atau AKAR tersebut 3. Ulangi langkah ke 1 sampai terbentuk sebuah 2-tree yang utuh.
Step 0:
6
Step 1:
5 8
3
3
7
10
6
7
10
5 8
Step 2:
13
3
5
Step 3:
6
7
18 8
3
10
13 10
6
7
5
Step 4:: 31 18 8 3
13 6
10 5
[email protected]
7
P
= 3 * 3 + 5 * 3 + 10 * 2 + 6 * 2 + 7 * 2
P
= 9 + 15 + 20 + 12 + 14
P
= 70
Halaman
5
Struktur Pohon ( TREE )
Modul Kuliah Struktur Data
BINARY SEARCH TREE (BST) Binary Search Tree (BST) merupakan suatu Pohon Biner yang mempunyai aturan sebagai berikut : T1 < R < T2. Fungsi dari BST adalah: 1. Pencarian data 2. Menghilangkan duplikasi data 3. Sorting Data
Searching dan Inserting Contoh: bentuklah BST dari data berikut : 60, 80, 30, 50, 65, 20, 10, 90, 25. Untuk membentuk BST dapat dilakukan dengan langkah-langkah sebagai berikut: 1. Data pertama sebagai Root 2. Untuk penyisipan data berikutnya ikuti aturan : T1 < R < T2
R
Left < Root < Right T1
T2
Tree yang terbentuk sebagai berikut :
60 30 20 10
[email protected]
80 50
65
90
25
Halaman
6
