Summary

Nama : Catharina Zevania Neysa Soetanto

NIM : 2301887345

Kelas : CB01

Lecturer : Ferdinand Ariandy Luwinda (D4522) dan Henry Chong (D4460)

FINAL REVIEW OF DATA STRUCTURES

1. Circular Single Linked List

Single : field pointernya hanya satu buah dan satu arah

Linked List : node-node nya saling terhubung satu sama lain

Circular : pointer next-nya akan menunjuk pada dirinya sendiri sehingga berputar

Jadi, single linked list circular adalah single linked list yang pointer nextnya menunjuk kepada dirinya sendiri artinya linked list ini tidak memiliki nilai NULL untuk medan sambungannya.

Setiap nodenya memiliki field yang berisi pointer ke next node, dan juga memiliki field yang berisi data.

Deklarasi Single Linked List Circular:

Struct tnode {

int data;

tnode *next;

};

void main() {

head = new tnode;

head->next = head;

}

Node terakhir akan menunjuk ke node paling depan sehingga linked list akan terus berputar.

2. Double Linked List

Adalah linked list dengan node yang memiliki data dan dua buah pointer (biasanya disebut next dan prev) yang menunjuk ke node sebelum dan node sesudahnya. Pada implementasinya, terdapat dua variasi double linked list yaitu circular dan non-circular layaknya pada single linked list.

Deklarasi node dibuat dari struct berikut ini :

typedef struct TNode{

int data;

Tnode *next;

Tnode *prev;

};

Awalnya, pointer next dan prev akan menunjuk ke nilai NULL. Selanjutnya, pointer prev akan menunjuk ke node sebelumnya, dan pointer next akan menunjuk ke node selanjutnya pada list.

Pointer 1 akan menunjuk Head (node pertama).

Deklarasi pointer penunjuk head pada double linked list :

TNode *head;

Penambahan data di depan

Penambahan node baru akan dikaitkan di node paling depan, namun saat data masih kosong, maka penambahan data dilakukan pada head-nya. Jadi, kita mengkaitkan data baru dengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head akan tetap selalu menjadi data yang paling pertama. Kita juga membutuhkan pointer bantu untuk menghubungkan node terakhir dengan node terdepan.

Contoh code menambah data baru di depan :

int isEmpty(){ //untuk mengecek apakah double linked list nya kosong

if(head == NULL) return 1;

else return 0;

}

void insertDepan(int databaru){

TNode *baru;

baru = new TNode;

baru->data = databaru;

baru->next = NULL;

baru->prev = NULL;

if(isEmpty()==1){

head=baru;

head->next = NULL;

head->prev = NULL;

}

else {

baru->next = head;

head->prev = baru;

head = baru;

}

Printf(”Data masuk\n”);

}

Penambahan data di belakang

Penambahan data dilakukan di belakang, namun pada saat pertama kali data langsung ditunjuk pada head-nya. Penambahan di belakang lebih sulit karena kita membutuhkan pointer bantu untuk mengetahui data terbelakang, kemudian dikaitkan dengan data baru. Kita membutuhkan perulangan untuk mengetahui data terbelakang.

Contoh code menambah data baru di belakang :

Void insertBelakang (int databaru){

Tnode *baru, *bantu;

Baru = new Tnode;

baru->data = databaru;

baru->next = NULL;

baru->prev = NULL;

if(isEmpty()==1){

head=baru;

head->next = NULL;

head->prev = NULL;

}

else{

bantu=head;

while(bantu->next!=NULL){

bantu=bantu->next

}

bantu->next = baru;

baru->prev = bantu;

}

Printf(”Data masuk\n”);

}

Menghapus Node Double Linked List

Tidak diperlukan pointer karena pointer hapus sudah bisa menunjuk ke pointer sebelumnya dengan menggunakan elemen prev ke node sebelumnya, yang akan diset agar menunjuk ke NULL setelah penghapusan dilakukan.

Contoh code menghapus data di depan:

void hapusDepan (){

TNode *hapus;

int d;

if (isEmpty()==0){

if(head->next != NULL){

hapus = head;

d = hapus->data;

head = head->next;

head->prev = NULL;

delete hapus;

}

else {

d = head->data; head = NULL;

}

printf" terhapus\n";

}

else printf"Masih kosong\n";

}

Contoh code menghapus node terbelakang :

void hapusBelakang(){

TNode *hapus;

int d;

if (isEmpty()==0){

if(head->next != NULL){

hapus = head;

while(hapus->next!=NULL){

hapus = hapus->next;

}

d = hapus->data;

hapus->prev->next = NULL;

delete hapus;

}

else {

d = head->data;

head = NULL;

}

Printf “terhapus\n";

}

else printf"Masih kosong\n";

}

3. Double Linked List Circular

Double Linked List Circular (DLLC) adalah linked list dengan menggunakan pointer, dimana setiap node memiliki 3 field, yaitu 1 field pointer yang menunjuk next, 1 field menunjuk pointer prev, serta sebuah field yang berisi data untuk node tersebut dengan pointer next dan pre-nya menunjuk ke dirinya sendiri secara circular.

Deklarasi node di double linked list circular:

typedef struct TNode{

int data;

TNode *next;

Tnode *prev;

};

Topic : Linked List

Setelah minggu kemarin belajar apa itu linked list dan linked list dibagi menjadi berapa bagian. Maka sekarang membahas linked list itu terdiri dari apa saja. Pada linked list, terdapat istilah push, dan pop dimana push berarti insert data baru pada linked list tersebut, dimana kita bisa push dari depan(dimana data yang kita masukkan berada di paling depan linked list kita dan data yang kita masukkan tersebut menjadi head), belakang (dimana data yang kita masukkan akan berada di paling belakang linked list kita dan data yang kita masukkan tersebut menjadi tail). Sedangkan pop berarti mendelete data, data dari depan, tengah dan juga belakang. Pada linked list, head berarti yang paling depan pada linked list tersebut, sedangkan tail berarti data yang terakhir.
Pada linked list digunakan fungsi malloc, untuk memesan sebuah alamat memory. Pada saat penggunaan malloc itu sendiri, mungkin beberapa bertanya-tanya mengapa digunakan sizeof, tidak langsung saja misal int, langsung saja 4, tidak usah pake sizeof(int), jawabannya adalah agar dinamis, karena kita tidak pernah tau program kita akan dicompile di compiler apa, bisa saja 16 ataupun 32 bit, yang mengakibatkan jumlah byte nya berbeda-beda.

Berikut contoh code fungsi untuk push head / menambahkan data dari depan :

Berikut contoh code fungsi untuk push tail / menambahkan data dari belakang :

Berikut contoh code fungsi untuk pop head/ men delete data paling depan :

Berikut contoh code fungsi untuk pop tail / men delete data paling belakang :

Hashing

adalah proses menghasilkan data keluaran (output data) yang panjangnya tetap dan sama, dari data masukan (input data) yang panjangnya berbeda-beda. Hashing digunakan untuk mengindeks dan mengambil item dalam database karena lebih cepat menemukan item menggunakan kunci hash yang lebih pendek daripada menemukannya menggunakan nilai asli. Itu juga digunakan dalam banyak algoritma enkripsi.

Hash Table

sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel. Menyimpan data pada memori ke dalam baris-baris dan kolom-kolom sehingga membentuk table yang diakses dengan cepat.

Hash Function

• Mid-square

Mid-Square hashing adalah teknik hashing di mana kunci unik dihasilkan. Dalam teknik ini, nilai diambil dan dikuadratkan. Kemudian, beberapa digit dari tengah diekstraksi. Angka-angka yang diekstrak ini membentuk angka yang diambil sebagai nilai baru. Teknik ini dapat menghasilkan kunci dengan keacakan tinggi jika nilai yang cukup besar akan diambil. • Division (most common)

Jumlah lokasi memori yang tersedia dihitung, kemudian jumlah tersebut digunakan sebagai pembagi untuk membagi nilai yang asli dan menghasilkan sisa. Sisa tersebut adalah nilai hashnya. Secara umum, rumusnya h(k)= k mod m. Dalam hal ini m adalah jumlah lokasi memori yang tersedia pada array. Fungsi hash tersebut menempatkan record dengan kunci K pada suatu lokasi memori yang beralamat h(k). Metode ini sering menghasilkan nilai hash yang sama dari dua atau lebih nilai aslinya atau disebut dengan bentrokan. Karena itu, dibutuhkan mekanisme khusus untuk menangani bentrokan yang disebut kebijakan resolusi bentrokan.

Contoh: asumsikan ukuran tabel = 11 dan satu file dengan 8 record menggunakan nilai kunci sebagai berikut : 12,21,68.

Maka:

(12 mod 11) + 1 = 1 + 1 = 2 ; simpan 12 dilokasi 2

(21 mod 11) + 1 = 10 + 1 = 11 ; simpan 21 dilokasi 11

(68 mod 11) + 1 = 2 + 1 = 3 ; simpan 68 dilokasi 3

(38 mod 11) + 1 = 5 + 1 = 6 ; simpan 38 dilokasi 6

(52 mod 11) + 1 = 9 + 1 = 10 ; simpan 52 dilokasi 10

(70 mod 11) + 1 = 4 + 1 = 5 ; simpan 70 dilokasi 5

(44 mod 11) + 1 = 0 + 1 = 1 ; simpan 44 dilokasi 1

(18 mod 11) + 1 = 7 + 1 = 8 ; simpan 18 dilokasi 8

Sehingga :

Index 1 2 3 4 5 6 7 8 9 10 11

Nilai Key 44 12 68 – 70 38 – 18 52 – 21

• Folding

Untuk mendapatkan alamat relatif, nilai key dibagi menjadi beberapa bagian, setiap bagian (kecuali bagian terakhir) mempunyai jumlah digit yang sama dengan alamat relatif. Bagian-bagian ini kemudian dilipat (seperti kertas) dan dijumlah. Hasilnya, digit yang tertinggi dibuang (bila diperlukan).

Contoh :

Kunci 123456, 234351, 222456, 321654, dilipat menjadi 2 bagian, setiap 3 digit.
Maka :
123+654 = 777 ; simpan 123456 dilokasi 777
234+153 = 387 ; simpan 234351 dilokasi 387
222+654 = 876 ; simpan 222456 dilokasi 876
321+456 = 777; simpan 321654 dilokasi 777
Dari perhitungan terjadi kolisi untuk nomor 123456 dan 321654.

• Digit Extraction

Digit yang telah ditetapkan dari nomor yang diberikan dianggap sebagai alamat hash.

Contoh:

Misalkan x = 14.568

Jika kita mengekstrak digit pertama, ketiga, dan kelima, kita akan mendapatkan kode hash: 158.

• Rotating Hash

Gunakan metode hash (seperti metode division atau Mid-Square). Setelah mendapatkan kode hash/alamat dari metode hash, lakukan rotasi. Rotasi dilakukan dengan menggeser digit untuk mendapatkan alamat hash baru.

Contoh:

Misal alamat hash = 20021

Hasil rotasi: 12002 (membalik angka)

Trees & Binary Tree

Following are the important terms with respect to tree :

· Path − Path refers to the sequence of nodes along the edges of a tree.

· Root − The node at the top of the tree is called root. There is only one root per tree and one path from the root node to any node.

· Parent − Any node except the root node has one edge upward to a node called parent.

· Child − The node below a given node connected by its edge downward is called its child node.

· Leaf − The node which does not have any child node is called the leaf node.

· Subtree − Subtree represents the descendants of a node.

· Visiting − Visiting refers to checking the value of a node when control is on the node.

· Traversing − Traversing means passing through nodes in a specific order.

· Levels − Level of a node represents the generation of a node. If the root node is at level 0, then its next child node is at level 1, its grandchild is at level 2, and so on.

· keys − Key represents a value of a node based on which a search operation is to be carried out for a node.

Binary Tree

Binary Tree atau Pohon Biner adalah sebuah pohon dalam struktur data yang bersifat hirarkis (hubungan one to many). Tree bisa didefenisikan sebagai kumpulan simpul dengan setiap simpul mempunyai paling banyak dua anak. Secara khusus, anaknya dinamakan kiri dan kanan. Binary tree tidak memiliki lebih dari tiga level dari Root.
Binary tree adalah suatu tree dengan syarat bahawa tiap node (simpul) hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binary treee boleh memiliki paling banyak dua child (anak simpul), secara khusus anaknya dinamakan kiri dan kanan.
Pohon biner dapat juga disimpan sebagai struktur data implisit dalam array, dan jika pohon tersebut merupakan sebuah pohon biner lengkap, metode ini tidak boros tempat. Dalam penyusunan yang rapat ini, jika sebuah simpul memiliki indeks i, anaknya dapat ditemukan pada indeks ke-2i+1 dan 2i+2, meskipun ayahnya (jika ada) ditemukan pada indeks lantai ((i-1)/2) (asumsikan akarnya memiliki indeks kosong).

Di computer science, binary search trees (BST), disebut sebagai binary tree yang diurutkan, adalah sebuah data structure yang menyimpan "item" tertentu (biasanya angka, nama, dll) di memori. Binary search trees (BST) memungkinkan untuk pencarian cepat, penambahan dan penghapusan item. Pada binary search trees (BST) sendiri menggunakan konsep untuk angka lebih kecil berada di sebelah kiri dan angka lebih besar berada di sebelah kanan.

Binary search tree mempunyai operasi dasar yaitu:

- find(x) : mencari kunci x di binary search tree (BST)

Setiap kali data dicari, mulailah mencari dari simpul akar. Kemudian jika data kurang dari nilai kunci, cari elemen di subtree kiri. Jika tidak, cari elemen di subtree kanan. Ikuti algoritma yang sama untuk setiap node.

- insert(x) : menambahkan kunci baru x di binary searach tree (BST)

Setiap kali data baru dimasukkan, pertama-tama cari lokasi yang tepat. Mulai mencari darileaf node, kemudian jika data kurang dari nilai kunci, cari lokasi kosong di subtree kiri dan masukkan data. Jika tidak, cari lokasi kosong di subtree kanan dan masukkan data.

- remove(x) : menghapus key x dari BST

Ketika kita menghapus sebuah key, maka akan ada 3 kemungkinan :

- Node yang dihapus terletak pada leaf: Maka simple langsung hapus saja data tersebut.

- Node yang dihapus mempunyai satu anak: Maka salin value anak tersebut ke dalam node dan hapus value anak di tempat semula.

- Node yang akan dihapus memiliki dua anak: Temukan penerus inorder dari node. Salin penerus inorder ke node dan hapus penerus inorder. Perhatikan bahwa pendahulu inorder juga dapat digunakan.

Secara umum, insertion dalam AVL sama dengan BST yaitu node dengan key lebih kecil dari induknya akan disimpan di sebelah kiri, dan node dengan key yang lebih besar dari induknya akan disimpan di sebelah kanan induknya. AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.

Penambahan node di AVL Tree

Untuk menjaga tree tetap imbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru → root. Node pertama yang memiliki |balance factor| > 1 diseimbangkan. Proses penyeimbangan dilakukan dengan: Single rotation dan Double rotation

Single Rotation

Single rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar 2. T1, T2, dan T3 adalah subtree yang urutannya harus seperti demikian serta height- nya harus sama (≥ 0). Hal ini juga berlaku untuk AVL tree yang merupakan citra cermin (mirror image)

Double Rotation

Double rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar 3. T1, T2, T3, dan T4 adalah subtree yang urutannya harus seperti demikian. Tinggi subtree T1 harus sama dengan T4 (≥ 0), tinggi subtree T2 harus sama dengan T3 (≥ 0). Node yang ditambahkan akan menjadi child dari subtree T2 atau T3. Hal ini juga berlaku untuk AVL tree yang merupakan citra cermin (mirror image).

Menghapus node di AVL Tree

1. Menghapus node pada AVL Tree sama dengan menghapus binary search tree procedure dengan perbedaan pada penanganan kondisi tidak balance.

2. Apabila node yang dihapus adalah LEAF, sehingga penghapusan akan tetap membuat AVL Tree yang terurut. Bila yang terjadi adalah ini, maka operasi penghapusan dapat langsung dilakukan.

3. Apabila node yang dihapus adalah node yang memiliki node 1 child, sehingga child yang bersangkutan dapat langsung dipindahkan untuk menggantikan posisi node yang dihapus.

4. Apabila node yang akan dihapus memiliki 2 children (2 subtree), maka node yang diambil untuk menggantikan posisi node yang dihapus adalah :

a. Bisa berasal dari left sub tree, dimana node yang diambil adalah node yang mempunyai nilai paling besar (yang berada pada posisi paling kanan).

b. Bisa berasal dari Right Sub Tree, dimana node yang diambil adalah node yang mempunyai nilai paling kecil (yang berada pada posisi paling kiri).

Dengan menggunakan gambar AVL Tree berikut ini ,akan diilustrasikan operasi deletekey untuk masing-masing kondisi di atas.

Posisi 1: jika yang didelete adalah LEAF, maka tidak perlu dilakukan modifikasi terhadap lokasi contoh :

Posisi 2 : jika yang didelete adalah NODE yang hanya memilki 1 child, maka child tersebut langsung menggantikan parentnya contoh :

Posisi 3: jika yang didelete adalah NODE dengan 2 children ( 2 Subtree), maka node yang diambil untuk menggantikan posisi node yang dihapus adalah :

1. Berasal dari LEFT SUB TREE, yang diambil adalah node yang paling kanan (yang mempunyai nilai yang terbesar)

2. Atau dari RIGHT SUBTREE, yang diambil adalah node yang paling kiri ( yang mempunyai nilai yang terkecil).

HEAP

Ada 3 jenis :

a. Min Heap

Root yang paling atas mempunyai nilai paling minimum.

Contoh :

b. Max Heap

Root yang paling atas mempunyai nilai paling maximum.

Contoh :

c. Min-Max Heap

Level paling atas minimum sedangkan level berikutnya maximum.

Contoh :

Representasi array :

(Current node = n)

parent = n / 2
left child = 2 * n
right child = (2 * n) + 1

PS : jika terjadi bilangan koma/decimal, bulatkan kebawah

INSERTION

1. Min-Heap

Insert new node (20)

pada gambar diatas, kita akan memasukan node 20 pada tree yang sudah ada. sesuai aturan binary Tree, 20 akan dimasukan di sebelah node 32.
Namun, posisi 20 setelah di insert adalah melanggar aturan, karena 20 lebih kecil dibandingkan parent nya yaitu 28. oleh karena itu terjadi penukaran tempat antara 20 dengan 28.

2. Max-Heap
insertion pada Max-Heap sama dengan Min-Heap, hanya berbeda aturan. aturan pada Max-Heap adalah Value Child < Value Parent-nya

3. Min-Max Heap
pada Min-Max Heap, min pada level 0(root) adalah yang bilangan min terkecil, dan max pada level 1 adalah bilangan max yang terbesar.

- jika yang di insert pada level min, maka parent nya (max) harus lebih besar daripada node yang akan di insert
- jika yang di insert pada level max, maka parent nya (min) harus lebih kecil dibandingkan node yang akan di insert

- setiap insert yang memenuhi kedua syarat diatas, harus mengecek value nya masing-masing terhadap min pada level 0/max pada level 1(tergantung yang di insert), jika terjadi pelanggaran syarat(yang sudah disebutkan diatas), maka harus dilakukan reposisi(downheap/upheap)

Tries