TEKNIK INFORMATIKA: June 2020

Selamat pagi, siang, dan malam. Pada hari ini, tanggal 09/06/2020 saya Tommy Cendana (2301902674) mahasiswa Bina Nusantara ingin membuat rangkuman materi perkuliahan Computer Science pada Semester 2 ini. Saya ucapkan terima kasih kepada dosen kelas besar (CB01) saya, pak Henry Chong (D4460) dan juga pak Ferdinand Ariandy Luwinda (D4522) karena telah mengajari kami di masa pandemi ini dengan baik. Saya berterima kasih juga kepada dosen kelas kecil (LB08) saya bu Diana (D4458) juga. Semoga semester 2 ini menjadi pelajaran yang tidak terlupakan. Terima kasih 😉

________________________________________________________________________________________________________________________________________________________

1. AVL TREE

AVL Tree

AVL adalah balanced binary search tree dimana ia memiliki perbedaan jumlah tinggi/level pada subtree kiri dan subtree kanannya maksimal 1 (atau dapat dikatakan antara tingginya sama atau selisih satu).

Berikut gambarannya :

AVL Tree, karena factor tertingginya 1

Not AVL Tree, karena balance factor tertingginya 2, sedangkan syarat AVL adalah selisihnya maksimal 1

Note :

Cara menentukan Height dengan Balance Factor :

Height :
- Jika node (root) tidak memiliki subtree heightnya, maka = 0
- Jika node adalah leaf, height = 1
- Jika internal node, maka height = height tertinggi dari anak + 1

Balance Factor :
-selisih height antara anak kiri dengan kanan, jika tidak memiliki anak, maka dianggap 0.

AVL Tree Operations : Insertion

Insert suatu node pada AVL sama halnya pada insert node pada binary search tree, dimana node baru diposisikan sebagai leaf. Setelah memasukkan node baru, maka harus dilakukan penyeimbangan kembali pada path dari node yang baru di insert atau path terdalam. Namun biasanya, path terdalam adalah path dari node yang baru saja di insert.

Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu :

anggap O adalah node yang harus diseimbangkan kembali

- Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri O (kiri-kiri)
- Kasus 2 : node terdalam terletak pada subtree kiri dari anak kanan O (kiri-kanan)
- Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri O (kanan-kiri)
- Kasus 4 : node terdalam terletak pada subtree kanan dari anak kanan O (kanan-kanan)
Ke-4 kasus tersebut dapat diselesaikan dengan melakukan rotasi

- Kasus 1 dan 4 dengan single rotation
- Kasus 2 dan 3 dengan double rotation

Single Rotation

Single rotasi (rotasi 1x) dilakukan apabila satu arah (jika arah nya kiri ya kiri terus, begitu pula sebaliknya).

Gambaran Single Rotation :

Single Rotation
pada contoh diatas, left-left karena dari 30 ke 22 ke kiri, dan dari 22 ke 15 ke kiri juga

Double Rotation

Double rotasi (rotasi 2x) dilakukan apabila satu arah tapi turunannya beda arah seperti contohnya, kiri kekanan atau kanan ke kiri.

Gambaran Double Rotation :

Step 1 (Rotasi pertama)
kasus diatas adalah left-right

Step 2 (Rotasi kedua)

kasus diatas, left-left

AVL Tree Operations : Deletion

Operasi penghapusan node sama seperti pada Binary Search Tree, yaitu node yang dihapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree di kanan. Jika yang dihapus adalah leaf, maka langsung hapus saja. Namun jika node yang dihapus memiliki child maka childnya yang menggantikannya. Namun setelah operasi penghapusan dilakukan, cek kembali apakah tree sudah seimbang atau belum, jika belum maka harus diseimbangkan kembali agar imbang. Cara seimbangnya pun sama seperti cara insertion.

delete node 60

node 55 tidak seimbang, karena anak kiri 0 dan anak kanan 2, selisih 2.
diseimbangkan dengan single rotation (left-left) karena 55 ke 65 kiri dan 65 ke 70 kiri
akan tetapi, node 50 menjadi tidak seimbang, di subtree kiri 4 dan subtree kanan 2

diseimbangkan dengan double rotation (left-right) karena dari 50 ke 25 kiri dan 25 ke 40 kanan

AVL yang sudah balance

2. RED BLACK TREE

Red Black Tree atau yang disebut sebagai RBT itu terdapat dua node yang berwarna, yaitu merah dan hitam.

Ilustrasi Red Black Tree (RBT)

Aturan pada Red Black Tree atau RBT adalah sebagai berikut;

1. Root selalu berwarna hitam

2. External node selalu berwarna hitam

3. Node yang baru di insert selalu berwarna merah

4. Node merah tidak boleh bertemu merah (child merah)

5. Jumlah node hitam sama dari root ke external node

RBT terdapat dua metode, Insertion dan Deletion.

Berikut penjelasan tentang keduanya;

A. Insertion

 Pada proses pertama insert, aturannya sama dengan melakukan insert di materi sebelumnya, Binary Search Tree

 Node yang baru di insert selalu berwarna merah

 Ketika pelanggaran aturan terjadi, maka pada saat itu juga segera diperbaiki agar tree sesuai aturan pada Red Black Tree.

Ilustrasi pada Red Black Tree yang disesuaikan

B. Deletion

 Berlangsung seperti Binary Tree biasanya, tetapi dilakukan pengecekan dulu sebelum melakukan delete.

Ilustrasi dimana S dari warna hitam, diubah maka S menjadi warna merah kemudian lakukan rotasi, lalu delete node N.

3. 2-3 TREE

A. Pengertian 2-3 Tree

2-3 Tree adalah pohon/tree di data struct, dimana setiap node dengan anaknya memiliki 2 node dan 1 data elemen atau 3 node dan 2 data elemen. 2-3 Tree ditemukan oleh John Hopcroft pada tahun 1970.

Aturan dalam 2-3 tree :

· 2-3 tree harus selalu hold, sehingga pohon tetap seimbang (nilai wajib 1 setelah kanan dikurang kiri jadi nilainya 1). Jadi, kita harus memastikan bahwa dua key node memiliki tiga anak, node satu key memiliki dua anak, dan kita tidak bisa memiliki 3 key di satu node.

· Semua insert dan removal dalam search tree biasanya (dan pasti selama 2-3 Trees) terjadi pada leaf,itu jauh lebih mudah untuk menangani dengan mengubah hal-hal di internal node.

· Biasanya, pre-processing (untuk removal) ataupun pasca-processing (untuk mengembalikan properti) diperlukan, selain untuk menanbahkan dan menghapus key.

B. Insertion

Setiap kali kita memasukkan key (atau, lebih tepatnya, sepasang key) menjadi tree,hal pertama yang kita lakukan adalah search, kemudian kita masukkan ke dalam simpul leaf di mana pencarian dihentikan. Jika leaf node hanya memiliki satu key sebelumnya, maka ia memiliki dua key.Tetapi jika simpul leaf sudah dua key, maka sekarang memiliki tiga key, jadi kita harus memperbaikinya.

Misalkan saya memiliki 10 angka (50 60 70 40 30 20 10 80 90 100) untuk kita input ke tree yang kosong.

I.
Input 50

Inputan pertaa dalam tree

II. Input 60

50 60

Inputan kedua, dimana angka 60 masuk ke node yang sudah ada, yaitu di dalam node angka 50

III. Input 70

50 70

Karena sudah tidak muat di node sebelum input angka 70, maka dibuatklah root baru di tree tersebut dengan angka 60 di tengah, 50 tetap di kiri dan 70 di kanan.

IV. Input 40

40 50 70

Angka 40 kita input di sebelah kiri node 50 karena 40<60, jadi posisinya di sebelah kirinya.

V. Input 30

40 60

30 50 70

Angka 30 lebih kecil dari 60, maka kita masukkan ke sebelah kiri. Karena itu, maka kita pindahkan angka 40 ke induk nya. Karena di induk memiliki dua data, maka boleh memiliki 3 subtree, maka dibuatkan node/anak baru di sebelah kiri bawah dengan angka 30.

VI. Input 20

40 60

20 30 50 70

Angka 20<30, maka kita masukkan ke dalam angka 30 (nodenya)

VII. Input 10

20 60

10 30 50 70

Karena 10<20, maka kita masukkan di node angka 20 30. Namun karena sudah tidak muat, maka kita naikkan angka 20 ke atas. Nah, otomatis angka 40 juga naik dikarenakan node angka 40 60 juga sudah tidak muat untuk menampung angka 20. Jadi angka 40 keangkat ke atas dengan angka 60 turun ke sebelah kanan.

VIII. Input 80

20 60

10 30 50 70 80

Karena 80>70, maka kita masukkan angka 80 ke node angka 70 karena masih ada ruang untuk diisi.

IX. Input 90

20 60 80

10 30 50 70 90

Dikarenakan angka 90 sudah tidak muat di node angka 70 80, maka kita naikkan angka 80 ke node angka 60. Dikarenakan node angka 60 80, maka sub nya bisa membentuk 3 sub nodenya, jadi angka 70 terpisah menjadi satuan dan angka 90 membentuk node nya sendiri.

X. Input 100

20 60 80

10 30 50 70 90 100

Seperti biasa, karena 100>90, maka kita input angka 100 ke node angka 90.

Jadi, begitulah proses insertion dalam 2-3 Tree

C. Deletion

Proses deletion ini kebalikan dari proses insertion, dimana leaf yang memiliki 3 node, kita akan menhapusnya untuk jadi 2 node saja. Sebelum itu kita lakukan search juga seperti tahapan insertion.

Aturan Deletion :

· Misalnya node yang dihapus adalah key

· Delete sama seperti BST, yaitu digantikan oleh leafnya

· Jika leaf 3-node, maka ambil salah satu data untuk menggantikan key, seperti BST, terbesar dari subtree kiri atau terkecil dari subtree kanan

· Jika leaf 2-node, maka :

jika parent dari leaf adalah 3-node, maka ambil satu data dari parent. kemudian kita perhatikan kembali siblingnya.

a) jika sibling 3-node, maka ambil satu data kemudian push pada parent, agar parent kembali menjadi 3-node

b) jika sibling 2-node, maka biarkan parent menjadi 2-node, dan satukan node tersebut dengan siblingnya

· Jika parent dari leaf adalah 2-node, kita perhatikan siblingnya.

a) jika sibling 3-node, ambil satu data dari parent dan push satu nilai dari sibling ke parent.

b) jika sibling 2-node, maka satukan sibling dengan parent.

Contohnya, kita ambil data dari insertion untuk di deletion kan;

I. Hapus angka 90

20 60 80

10 30 50 70 100

Angka 90 tinggal dihapus saja

II. Hapus angka 100, lalu turun angka 80 untuk ke node angka 100

20 60

10 30 50 70 80 100

III. Hapus angka 60, lalu ganti dengan naikkan angka 80 ke node angka sebelumnya yang dihapus

20 80

10 30 50 70 100

IV. Hapus angka 80, lalu ganti dengan naikkan angka 70 ke node angka sebelumnya yang dihapus

20 70

10 30 50 100

V. Hilangkan angka 40 dengan naikkan angka 30 ke untuk dimasukkan ke angka yang dihapus, angka 70 naik ke atas dengan bergabung dengan angka 30. Lalu angka 10 dan 20 digabungkan menjadi 1 node (10 20). Angka 50 membentuk node sendiri, berikut juga angka 100 tetap disitu.

30 70

10 20 50 100

VI. Hilangkan angka 50, dengan begitu maka angka 20 bisa membentuk node sendiri.

30 70

10 20 100

VII. Tukar angka 20 ke angka 30 untuk membetulkan arah/arus agar sesuai

20 70

10 30 100

VIII.
Hapus angka 20, lalu gabungkan angka 10 dan 30 untuk sesuai aturan tree

10 30 100

Jadi, begitulah proses deletion di 2-3 Tree.

4. HEAP & TRIES

Heap adalah sebuah struktur data yang terdapat pohon/tree. Disebut juga sebagai Complete Binary Tree yang memenuhi persyaratannya.

Terdapat 3 tipe dalam Heap;

A. Min Heap

Nilai parent < nilai children

25 7

26 35 15 20

Ilustrasi Min Heap

Penjelasan : Jadi dilihat dari bentuk tree, nilai terkecil adalah di bagian root/pucuk tree sesuai dengan Namanya (min heap) dimana dari level 1/root itu terkecil hingga level terbawah/children nya memiliki nilai terbesar.

B. Max Heap

Nilai parent > nilai children

25 26

3 7 15 20

Ilustrasi Max Heap

Penjelasan : Jadi dilihat dari bentuk tree, nilai terbesar adalah di bagian root/pucuk tree sesuai dengan Namanya (max heap) dimana dari level 1/root itu terbesar hingga level terbawah/children nya memiliki nilai terkecil.

C. Min-Max Heap

Terjadi selang-seling pada tree, dimana pada root/pucuk tree itu min lalu baris kedua itu max dan selanjutnya terus minmax sesuai banyak level treenya.

25 26

5 7 4 20

Ilustrasi Min-Max Heap

Penjelasan : Jadi dilihat dari bentuk tree, terjadi selang seling / min-max dimana root memiliki nilai min lalu parent nya nilai max berikut juga dengan children nya yang nilainya min dari nilai parentnya.

Operasi dalam Heap itu dilakukan dari masing-masing jenisnya ( Min Heap, Max Heap, dan Min-Max Heap)

A. Operasi Min Heap

• Find-Min = mencari nilai terkecil pada root/pucuk tree

• Insertion

I. Masukkan nilai baru pada tree

II. Lakukan Up-Heap Min

(Up-Heap Min adalah suatu cara membandingkan nilai data yang di insert dengan parent nya. Jika nilai yang baru dimasukkan itu lebih besar, maka tidak usah ditukar dengan parentnya. Tetapi apabila lebih kecil, maka tukar nilai dengan parent nya )

III. Proses Up-Heap Min dihentikan jika nilai baru sudah diinput semua dan juga nilai dari root sampai ke leaf nilainya dari kecil hingga besar

Contoh operasi Insertion Min Heap;

25 7

26 35 15 20

2 Masukkan angka 2 dalam tree, lalu lanjut proses Up-Heap Min

25 7

2 35 15 20

26 Tukar angka 2 dengan parentnya (Angka 26)

2 7

25 35 15 20

26 Tukar angka 2 dengan parentnya (Angka 25)

3 7

25 35 15 20

26 Tukar angka 2 dengan parentnya/root (Angka 3)

Selesai, proses operasi Min Heap.

• Deletion

I. Tukarkan data yang terakhir dimasukkan dengan root

II. Jika data yang ingin dihapus berada di posisi leaf, maka tinggal dihapus

III. Lakukan Down-Heap Min

(Down-Heap Min adalah suatu cara membandingkan nilai root dari langkah awal dengan parentnya/ kedua anaknya, jika ada salah satu yang lebih kecil dari root, maka tukar posisinya. Jika keduanya lebih kecil, maka cari nilai dari anak tersebut yang terkecil untuk ditukar ke posisi root)

IV. Proses Down-Heap Min dihentikan apabila root/pucuk tree itu nilai terkecil dari tree dan nilai tree dari atas kebawah itu kecil hingga besar

Contoh operasi Deletion Min Heap;

3 7

25 35 15 20

26 Delete angka 2

3 7

25 35 15 20

Tukar angka 26 dengan parentnya/root yang didelete tadi

25 7

26 35 15 20

Setelah ditukar-tukar, selesailah proses deletion

B. Operasi Max Heap

• Find-Max = mencari nilai terbesar pada root/pucuk tree

• Insertion

I. Masukkan nilai baru pada tree

II. Lakukan Up-Heap Max

(Up-Heap Max adalah suatu cara membandingkan nilai data yang di insert dengan parent nya. Jika nilai yang baru dimasukkan itu lebih kecil, maka tidak usah ditukar dengan parentnya. Tetapi apabila lebih besar, maka tukar nilai dengan parent nya )

III. Proses Up-Heap Max dihentikan jika nilai baru sudah diinput semua dan juga nilai dari root sampai ke leaf nilainya dari besar hingga kecil

Contoh operasi Insertion Max Heap;

25 27

3 7 23 21

26 Insert angka 26

25 27

26 7 15 20

3 Tukar angka 3 dengan parentnya (angka 26)

26 27

25 7 15 20

3 Tukar angka 26 dengan parentnya (angka 25); Selesai

• Deletion

I. Tukarkan data yang terakhir dimasukkan dengan root

II. Jika data yang ingin dihapus berada di posisi leaf, maka tinggal dihapus

III. Lakukan Down-Heap Max

(Down-Heap Max adalah suatu cara membandingkan nilai root dari langkah awal dengan parentnya/ kedua anaknya, jika ada salah satu yang lebih besar dari root, maka tukar posisinya. Jika keduanya lebih besar, maka cari nilai dari anak tersebut yang terbesar untuk ditukar ke posisi root)

IV. Proses Down-Heap Max dihentikan apabila root/pucuk tree itu nilai terbesar dari tree dan nilai tree dari atas kebawah itu besar hingga kecil

Contoh operasi Deletion Max Heap;

26 27

25 7 15 20

3 Delete angka 26

25 27

3 7 15 20

Selesai karena sudah sesuai dengan aturannya

C. Operasi Min-Max Heap

• Tree selang-seling nilainya dengan min di root, parent max dan seterusnya

• Insertion

I. Masukkan nilai baru pada tree

II. Lakukan Up-Heap Min-Max

 Apabila nilai baru terdapat pada level Min, tukar nilai dengan parentnya apabila parent dari nilai baru itu lebih kecil. Lakukan juga Up-Heap Min dari parent dan Up-Heap Max dari nilai baru tersebut

 Apabila nilai baru terdapat pada level Max, tukar nilai dengan parentnya apabila parent dari nilai baru itu lebih besar. Lakukan juga Up-Heap Min dari parent dan Up-Heap Max dari nilai baru tersebut

 Definisi mengenai Up-Heap Min dan Up-Heap Max dapat dilihat di bagian A dan B dimana terdapat operasi Heap Min dan Max

III. Proses Up-Heap Min-Max dihentikan apabila tree selang-seling nilainya dengan min di root, parent max dan seterusnya

Contoh operasi Insertion pada Min-Max Heap;

25 26

5 2 4 20

Insert angka 1

25 26

1 2 4 20

Tukar angka 5 dengan parentnya (angka 1); Selesai

• Deletion

I. Apabila proses dilakukan dari data min/terkecil, maka tukar root dengan nilai terkecil tersebut, lalu hapus data terakhirnya dan lakukan proses Down-Heap Min dari root

II. Apabila proses dilakukan dari data max/terbesar, maka tukar nilai anak yang terbesar dari root dengan nilai dari data terakhir, lalu hapus data terakhirnya dan lakukan proses Down-Heap Max dari node nya.

III. Definisi mengenai Down-Heap Min dan Down-Heap Max dapat dilihat di bagian A dan B dimana terdapat operasi Heap Min dan Max

Contoh operasi Deletion pada Min-Max Heap;

25 26

1 2 4 20

Delete angka 1

25 26

5 2 4 20

Angka 5 di naikkan ke atas karena parentnya telah didelete,

lalu cek apakah sudah sesuai. Selesai

Demikian materi tentang Heap ini dibuat, mohon maaf apabila terjadi kesalahan kata dari penjelasan penulis.

TEKNIK INFORMATIKA

Tuesday, June 9, 2020

RANGKUMAN MATERI DATA STRUCTURES (SEMESTER 2)

AVL Tree Operations : Insertion

Single Rotation

Double Rotation

AVL Tree Operations : Deletion