-SUMMARY-

Summary / Rangkuman

Stephanie Kezia // 2301895214
Nama dosen : Henry Chong (D4460) & Ferdinand Ariandy Luwinda (D4522)

Saat belajar Data Structure, hal pertama yang di pelajari adalah soal pointer. Pointer merupakan variabel yang berisikan alamat memori. Pointer berisi alamat dari variabel yang mempunyai nilai tertentu.

Selanjutnya adalah Linked List. Linked List adalah struktur data linear. Linked List yang dipelajari adalah Single Linked List dan Double Linked List.

Selanjutnya adalah mengenai Hashing & Tree.
Hashing merupakan teknik menyimpan dan mengambil kunci dengan cepat.Hashing berarti mengambil string input dengan panjang berapa pun dan memberikan output dengan panjang tetap.

Jenis-jenis tree antara lain:
- Binary Search Tree
- AVL Tree
- B-Tree
- Red Black Tree
dan lainnya.

Yang terakhir adalah Heap & Tries. Heap adalah suatu struktur binary tree yang lengkap dan memiliki beberapa sifat tertentu yang meingimplementasikan priority queue. Tries adalah pohon struktur data yang terurut dan menyimpan karakter.

Heap & Tries

Heap

Heap adalah suatu struktur binary tree yang lengkap dan memiliki beberapa sifat tertentu yang mengimplementasikan priority queue, diimplementasikan bisa menggunakan linked-list, namun lebih mudah menggunakan array.

Penggunaan heap dibagi menjadi 3 tipe yaitu :
1. Min Heap
2. Max Heap
3. Min-Max Heap

Masing-masing heap memiliki cara insertion dan delete yang berbeda-beda dan beberapa perbedaan logic yang terbalik-balik


1. Min Heap

Pada pohon Min Heap, elemen paling kecil terletak pada root, dan elemen paling besar terletak pada salah satu node leave yang ada.
Contoh Min Heap :

Parent akan lebih kecil daripada childrennya, serta tidak ada hubungannya dengan unclenya.

Insertion : Bila memasukkan sebuah angka baru, maka dimasukkan ke node paling akhir, lalu bandingkan dengan parentnya. Jika parent lebih besar bisa lakukan swap, jika parent lebih kecil maka sudah benar.
Delete : Root dihilangkan lalu diganti dengan angka dari node terakhir lalu bandingkan. Jika children lebih kecil maka tukar sampai root adalah angka terkecil.

2. Max Heap

Pada pohon Max Heap, elemen paling besar terletak pada root, dan elemen paling kecil terletak pada salah satu node leave yang ada.
Contoh Max Heap :

Parent akan lebih besar daripada childrennya, serta tidak ada hubungannya dengan unclenya.

Insertion : Bila memasukkan sebuah angka baru, maka dimasukkan ke node paling akhir, lalu bandingkan dengan parentnya. Jika parent lebih kecil bisa lakukan swap, jika parent lebih besar maka sudah benar.
Delete : Root dihilangkan lalu diganti dengan angka dari node terakhir lalu bandingkan. Jika children lebih besar maka tukar sampai root adalah angka terbesar.

3. Min-Max Heap

Merupakan gabungan dari Min Heap dan Max Heap menjadi suatu heap yang unik. Urutannya selalu Min, lalu Max, lalu Min dan seterusnya. Level genap adalah Min, level ganjil adalah Max.
Contoh Min-Max Heap :

Insertion dan Delete sama seperti Min Heap dan Max Heap, tapi harus memperhatikan levelnya mana yang harus Max dan mana yang harus Min.


Tries

Tries adalah pohon struktur data yang terurut dan menyimpan karakter. Di gunakan untuk auto complete, searching, bubble words dll.
Contoh tries :

Kata bisa menjadi:
ASSOC
ALGO
ALL
ALSO

TRIE
TREE

AVL Tree

AVL Tree adalah binary tree yang diseimbangkan, yang dimana perbedaan tinggi antara kanan dan kiri subtree tidak boleh lebih dari satu.

Misalkan T adalah node yang harus diseimbangkan kembali,

-Kasus 1 : node terletak pada subtree kiri dari anak kiri T (Left - Left) / LL

-Kasus 2 : node terletak pada subtree kanan dari anak kanan T (Right - Right) / RR

-Kasus 3 : node terletak pada subtree kanan dari anak kiri T (Right - Left) / RL

-Kasus 4 : node terletak pada subtree kiri dari anak kanan T (Left - Right) / LR

Kasus-kasus diatas dapat diselesaikan dengan cara rotasi.

Kasus 1 & Kasus 2 = Single rotation

Kasus 3 & Kasus 4 = Double rotation

1. Single Rotation

Single rotation adalah : pengubahan node yang dilakukan bila node terletak searah

2. Double Rotation

Double rotation adalah : pengubahan node yang dilakukan bila node terletak tidak searah

Penghapusan node dalam AVL Tree

Cara:

1. Jika node yang akan dihapus berasa di posisi leaf, maka langsung hapus

2. Jika node yang akan dihapus memiliki anak, maka harus dilakukan penyeimbangan, supaya perbedaan tinggi maksimal satu.

SUMMARY dan REVIEW

LINKED LIST

Linked List adalah sekumpulan data struktur linear yang disebut sebagai node yang tersimpan dalam suatu senarai supaya lebih efektif.

Head adalah elemen pertama linked list
Tail adalah elemen terakhir linked list

Tipe-tipe linked list:
-Single Linked List
-Double Linked List
-Circular Linked List
-Multiple Linked List

HASH

Hashing merupakan teknik menyimpan dan mengambil kunci dengan cepat.
Hashing berarti mengambil string input dengan panjang berapa pun dan memberikan output dengan panjang tetap.

Metode hash string menjadi key :
1. Mid-square
2. Division
3. Folding
4. Digit extraction
5. Rotating Hash

BINARY TREE

Binary tree adalah pohon struktur data yang dimana memiliki anak maksimal 2 atau 1 yang disebut daun.

Macam-macam binary tree:

- Binary tree penuh

- Binary tree lengkap

- Binary tree similer

- Binary tree miring

- Binary tree ekuivalen

BINARY SEARCH TREE

Binary search tree mirip dengan linked list. Binary search tree berbentuk pohon, linked list berbentuk linear.

Binary Tree dikelompokkan menjadi dua, yaitu :
- Binary Tree Terurut (Ordered Binary Tree)
- Binary Tree Tidak Berurut (Unordered Binary Tree)

References:

https://etherealflorescence.blogspot.com/2020/03/binary-search-tree.html

https://etherealflorescence.blogspot.com/2020/03/data-structure-hashing-tree.html

https://etherealflorescence.blogspot.com/2020/02/data-structure-linked-list.html

Binary Search Tree

Binary Tree

Binary Tree mirip dengan struktur data Linked List.
Yang membedakan antara Binary Tree dengan Linked List adalah Binary Tree berbentuk seperti pohon, sedangkan Linked List berbentuk seperti rantai yang linear.

Binary Tree dikelompokkan menjadi dua, yaitu :
- Binary Tree Terurut (Ordered Binary Tree)
- Binary Tree Tidak Berurut (Unordered Binary Tree)

Gambar binary tree berdasarkan kondisinya :

Gambaran binary tree yang terdiri dari 3 node :

Binary Search Tree

Binary Search Tree : Tree yang terurut (Ordered Binary Tree) yang memiliki kelebihan bila dibandingkan dengan struktur data lain.
Proses pengurutan dan pencarian dapat dilakukan bila data sudah tersusun dalam struktur data binary search tree.

Hashing & Tree

HASHING

Hashing merupakan teknik menyimpan dan mengambil kunci dengan cepat.
Hashing berarti mengambil string input dengan panjang berapa pun dan memberikan output dengan panjang tetap.

Metode hash string menjadi key :
1. Mid-square
2. Division
3. Folding
4. Digit extraction
5. Rotating Hash

1. Mid-square
Langkah :
1. Ambil nilai awal
2. Kuadratkan nilai awal
3. Beberapa digit angka ditengah setelah dikuadratkan, diambil dan diekstrak menjadi nilai baru
Contoh :
3121 dikuadratkan menjadi 9740641. Nilai tengahnya adalah 406.
Binarinya adalah 1001 0100 1010 0001 0110 0001‬.

2. Divison
Divison menggunakan modulus.
Contoh :
Nilai asli = 5
Ukuran tabel = 4
(5 % 4)+1 = 1+1 = 2. Simpan 5 di lokasi 2.

3. Folding
Langkah :
1. Nilai dibagi menjadi beberapa bagian, tiap bagian memiliki jumlah digit yang sama
2. Lipat seperti kertas, lalu dijumlah
Contoh :
- 1234 = 12 + 34 = 46. Hash valuenya adalah 46.
- 123654 = 123 + 654 = 777. Hash valuenya adalah 777.
- 321456 = 321 + 456 = 777. Hash valuenya adalah 777.

Terjadi collision antara 123654 dan 321456.
Collision adalah peristiwa dimana ada dua atau lebih nilai asli yang memiliki hash value yang sama. Penyelesaiannya adalah dengan cara probing dan chaining.

4. Digit extraction
Digit yang ditentukan sebelumnya dari nomor yang diberikan dianggap sebagai alamat hash.
Contoh : 14568
Digit ke 1 adalah 1
Digit ke 3 adalah 5
Digit ke 5 adalah 8
Maka disimpan di 158.

5. Rotating
Hanya membalikkan nilai asli
Contoh : 12345 menjadi 54321. Hash codenya adalah 54321.



TREE

Tree adalah node tanpa pengulangan/looping.

Konsep tree

DEGREE of TREE = 3

DEGREE of C = 2

HEIGHT = 3

PARENT of C = A

CHILDREN of  A = B, C, D

SIBILING of F = G

ANCESTOR of F = A, C

DESCENDANT of C = F, G

Konsep binary tree

ROOT = 18
LEAVE = 9, 12, 10, 23















Macam-macam pohon binari:
1. Pohon binari penuh

2. Pohon binari lengkap

3. Pohon binari similer

4. Pohon binari ekuivalen

5. Pohon binari miring

PREFIX, INFIX & POSTFIX

1. Prefix

Kunjungan secara preorder (Depth First Order), mempunyai urutan :

1. Cetak isi simpul yang dikunjungi (simpul akar)

2. Kunjungi cabang kiri

3. Kunjungi cabang kanan

2. Infix

Kunjungan secara inorder (symetric order), mempunyai urutan :
1. Kunjungi cabang kiri
2. Cetak isi simpul yang dikunjungi (simpul akar)
3. Kunjungi cabang kanan

 3. Postfix

Kunjungan secara postorder, mempunyai urutan :
1. Kunjungi cabang kanan
2. Kunjungi cabang kiri
3. Cetak isi simpul yang dikunjungi (simpul akar)

Single Linked List (Push & Pop)

• Push :

1. Push Depan : Menambahkan data baru di depan data lama.
2. Push Belakang : Menambahkan data baru di belakang data lama.

• Pop :

1. Pop Depan : Menghapus data mulai dari depan
2. Pop Belakang : Menghapus data mulai dari belakang

Pengimplementasian Push dapat dilakukan saat menambah daftar lagu, sedangkan Pop dilakukan saat menghapus daftar lagu.