Final Review

Halo, Selamat datang di blog aku, hari ini kita akan mengulang pembahasan beberapa materi tentang data structure, yang pertama adalah Linked List

Linked List

Linked List adalah kumpulan elemen data, yang setiap data nya menunjuk ke data berikutnya, dan di diakhiri oleh null.

Tipe - tipe linked list yaitu :

• Simple Linked List - hanya bisa bergerak maju.
• Doubly Linked List - bisa bergerak maju dan mundur.
• Circular Linked List - data terakhir bisa bergerak maju ke data pertama, dan data pertama                                              bergerak mundur ke data terakhir.

Doubly Linked List

Doubly Linked List hampir mirip dengan simple linked list, bedanya dia memiliki 2 pointer, yaitu next dan previous.

• next - bergerak maju ke data selanjutnya
• previous - bergerak mundur ke data sebelumnya

Circular Single Linked List

Circulat Single Linked List adalah Simple Linked List yang bisa berulang, bedanya kalau di Simple Linked List diakhiri dengan null, kalau di Circular Single Linked List tidak diakhiri dengan null, dia diakhiri dengan pointer di data paling terakhir yang menunjuk ke data pertama.

Circular Doubly Linked List

Circulat Doubly Linked List adalah gabungan antara Doubly Linked List dengan Circular Linked List. Linked List jenis ini memiliki 2 buah pointer yaitu next dan previous. Pointer next berfungsi untuk bergerak maju dan pointer previous berfungsi untuk bergerak mundur. Bedanya dengan Doubly Linked List adalah Circular Doubly Linked List apabila sudah berada di akhir data, maka apabila di next akan bergerak kembalik ke data pertama.

yang kedua adalah Stack and Queue

Stack and Queue

Stack adalah Struktur Data yang penting karena dia menyimpan elemen-elemennya dengan tersusun rapih. Data disimpan dengan cara Last In First Out (LIFO). Stack bisa diimplementasikan menggunakan array ataupun linked list. Elemen-elemen di dalam stack yang di add atau remove hanya bisa dari satu ujung, yang disebut dengan top.
Stack memiliki operasi-operasi yaitu :

• push (x): Add item x ke atas Stack.
• pop (): Delete item dari atas Stack.
• top (): reveal or return item teratas dari Stack.

Queue hampir sama dengan stack, perbedaannya adalah cara menyimpannya, kalau Stack menyimpan data dengan cara Last in First Out (LIFO), Queue menyimpan data dengan cara First in First Out (FIFO). Elemen-elemen dalam Queue ditambahkan di satu ujung yang disebut bagian Rear dan dihapus dari ujung yang lain yang disebut Front.

Queue juga memiliki operasi yang sama dengan Stack, yaitu :

• push (x): add item x ke rear queue
• pop (): delete item dari front queue.
• front (): reveal or return item paling depan dari queue.

berikutnya kita akan membahas tentang Hashing & Tree

1. Hashing

Hashing adalah metode atau cara untuk mengambil data dengan cepat, cara ini mengubah String Character nya menjadi value yang panjangnya lebih kecil dari aslinya yang berfungsi untuk menunjukan bahwa nilai itu adalah nilai string tersebut.
Hashing biasanya digunakan untuk mengambil suatu item di dalam database karena menggunakan metode hashing mempercepat kita dalam mencari value yang kita inginkan karena value dari original string sendiri diperkecil dengan cara metode hashing.
Hashing juga dapat didefinisikan sebagai konsep mendistribusikan kunci dalam array yang disebut Hash Tabel menggunakan fungsi yang telah ditentukan yang disebut Hash Function.

2. Tree

Tree adalah struktur data non-linear yang mewakili hubungan hierarchy antara data-data yang ada di dalam list. Beberapa relation antara tree dapat diamati dalam struktur directory. Node dalam tree tidak perlu disimpan secara berdekatan, Node bisa disimpan dimana saja asal masih bisa dihubungkan dengan pointer.

contoh

dari contoh diatas :

Degree of Tree = 4

Degree of T = 3

height = 4

Parent of Z = X

Childern of T = U, V, W

Siblings of Y = Z

Ancestor of Z = X, S, R

Descendant of S = X, Y, Z

Selanjutnya kita akan membahas tentang BST atau Binary Search tree

Binary Search Tree

Binary Search Tree (BST) adalah sebuah konsep penyimpanan data, dimana data disimpan dalam sebuah tree yang memungkinkan untuk melakukan searching dan sorting secara lebih cepat dan insert dan delete yang lebih mudah.

Dalam Binary Search Tree terdapat maksimal 2 anak node dalam setiap nodenya, dan Binary Search Tree memiliki aturan :

• Left Subtree dari X, berisi elemen yang lebih kecil dari elemen yang disimpan di dalam X.
• Right Subtree dari X, berisi elemen yang lebih besar dari elemen yang disimpan di dalam X.

Binary Search Tree memiliki beberapa operasi dasar seperti berikut :

1. Find (x)

Find adalah operasi untuk mencari elemen X yang diinginkan. Searching dimulai dari root (akarnya), apabila root mengandung X didalamnya maka search dihentikan. apabila X lebih kecil dari root, maka search akan berlanjut secara rekursif ke Left Subtree. apabila X lebih besar dari root, maka search akan berlanjut secara rekursif ke Right Subtree.

2. Insertion (x)

Insertion adalah operasi untuk insert atau memasukkan sebuah elemen kedalam data. Sama seperti Searching, Insertion juga dimulai dari root. apabila X lebih kecil value didalam root, maka x akan dimasukkan ke Left Subtree, apabila lebih besar maka akan dimasukkan kedalam Right Subtree.

3. Deletion (x)

Deletion adalah operasi untuk menghapus sebuah data dalam node. ada 3 case dalam deletion yaitu :

• jika data berada di leaf (ujung tree) : hapus saja nodenya
• jika data berada di node yang memiliki 1 anak : hapus node dan sambungkan node anak dengan parent
• jika data berada di node yang memiliki 2 anak : temukan anak paling kanan dari Left Subtree (simpul P), ganti kuncinya dengan kunci P dan hapus P secara rekursif.

Setelah BST ada yang namanya AVL Tree, apa itu AVL tree?

AVL Tree

AVL Tree yang dinamakan dari pembuatnya yaitu Adelson-Velsky and Landis’ tree, adalah self-balancing binary search tree. Dalam AVL Tree, ketinggian anak anak di setiap simpul berbeda paling banyak 1. Kapan saja jika perbedaan ketinggian menjadi lebih besar dari 1 maka penyeimbangan pohon dilakukan untuk memulihkan propertinya.

dalam AVL Tree ada 2 basic operation yaitu Right Rotation and Left Rotation.

Cara Rotasi ini berfungsi untuk menyeimbangkan Tree:

1. Biarkan  node A menjadi node baru yang di add ke tree.
2. Setelah node A di add, dari node A ke root untuk menemukan node yang tidak seimbang.
3. apabila ketemu node yang tidak seimbang maka akan diseimbangkan dan terus mengecek apabila masih ada node pada tree yang tidak seimbang.

Jka Anda telah menemukan simpul z yang tidak seimbang, Node y adalah anak dari z dan x menjadi cucu dari z maka akan ada empat kemungkinan, yaitu 

• Case Left - Left: - x adalah left child dari node y dan y adalah left child dari node z.

• Case Left - Right: - x adalah right child dari node y dan y adalah left child dari node z.

• Case Right - Left: - x adalah left child dari node y dan y adalah right child dari node z.

• Kasus Right - Right: - x adalah right child dari node y dan y adalah right child dari node z.

Operasi Insertion:

• Insert node baru menggunakan rekursi agar saat melacak kembali Anda akan men-check semua parent node untuk memeriksa apakah mereka masih seimbang atau tidak.
• Setiap node memiliki height dengan nilai default sebagai 1.
• Ketika node baru ditambahkan, height dari parent node akan bertambah 1.
• Jadi seperti yang disebutkan pada langkah 1, setiap height dari ancestors nya akan diperbarui saat kembali melacak dari atas sampai ke root.
• Di setiap node, Balance Factor juga akan diperiksa. faktor keseimbangan = (height left tree - height right tree).
• Jika Balance Factor = 1 berarti tree sudah seimbang pada node tersebut.
• Jika Balance Factor > 1 berarti tree tidak seimbang pada node tersebut, height left tree lebih tinggi daripada height right tree sehingga itu berarti kita perlu rotasi. (Baik Left - Left atau Left - Right).
• Jika node saat ini yang kita periksa adalah X dan Jika node baru kurang dari X.left maka itu akan menjadi case Left - Left, dan jika node baru lebih besar dari X.left maka itu akan menjadi Case Left - Right. 
• Jika Balance Factor < -1 berarti tree tidak seimbang pada node tersebut, height right tree lebih tinggi dari height left tree sehingga itu berarti kita perlu rotasi. (Baik Case Right - Right atau RIght - Left)
• Katakanlah node saat ini yang kita periksa adalah X dan Jika node baru kurang dari X.right maka itu akan menjadi Case Right - Right, dan jika node baru lebih besar dari X.right maka itu akan menjadi Case Right - Left. 

Yang terakhir adalah tentang Heap & Tries

Heap

heap adalah struktur data yang bisa dibilang sama atau mirip dengan Binary Search Tree (BST), namun bedanya adalah heap merupakan Complete Binary Tree yang memiliki persyaratannya sendiri. Heap dibagi menjadi 3 yaitu :

• Min Heap 
• Max Heap
• Min-Max Heap

1. Min Heap

Setiap node dalam Min Heap lebih kecil dari masing-masing child nya dan root merupakan node paling kecil.

Insertion : 

• Insert Node baru
• Check parent
• Jika nilai node baru tersebut lebih kecil dibandingkan parent, tukar posisinya dengan parent.

Deletion : 

• Yang dihapus merupakan rootnya (elemen terkecil).
• Root yang dihapus tersebut kemudian digantikan oleh data terakhir di nodenya, kemudian data tersebut di downheapmin(jika anak < data tsb, maka tukar,dst sampai mentok dibawah atau node tsb<anaknya).

2. Max Heap

Setiap node dalam Max Heap lebih besar dari masing-masing child nya dan root merupakan node paling besar

Insertion : 

• Insert Node baru
• Check parent
• Jika node baru bernilai lebih besar dibandingkan parent, tukar posisinya dengan parent.

Deletion : 

• Yang dihapus merupakan rootnya (elemen terbesar).
• Root yang dihapus tersebut kemudian digantikan oleh data terakhir di nodenya, kemudian data tersebut di downheapmax(jika anak > data tsb, maka tukar,dst), sampai mentok dibawah atau node tsb>anaknya).

3. Min-Max Heap

Pada Min-Max Heap, root akan bernilai minimum, selanjutnya child dari root akan bernilai maksimum, dan seterusnya. Nilai terkecil berada di root dan nilai terbesar berada di salah satu node pada level setelah root. Level min hanya dapat dibandingkan dengan level min, dan sebaliknya.

Insertion dan Deletion sama seperti Min Heap atau Max Heap namun, pengecekan kondisi hanya dapat dilakukan di level sesama min atau max

Tries

Tries merupakan tree yang berfungsi untuk menyimpan array

• root mempresentasikan karakter kosong/null
• node lainnya mempresentasikan satu huruf

Sekian untuk pembahasan saya pada hari ini, mohon maaf jika ada kekurangan, terima kasih.


Nama : Muhammad Rifqi Zhafar
NIM : 2301899490Kelas : CB01Lecturer : Ferdinand Ariandy Luwinda -D4522 dan Henry Chong -D4460