Kumpulan Rangkuman Data Structure 2019-2020

Linked List

Jadi ini adalah rangkuman dari pertemuan ke 3 mata kuliah Data Structures yang kelasnya tercancel karena bencana alam yang terjadi pada hari ini. Semoga kita semua baik – baik saja ya dan bisa belajar di universitas tercinta kita besoknya. Jadi tanpa basa – basi, ini adalah linked list.

Hal Hal yang kita pelajari pada pertemuan ke 3 ini adalah sebagai berikut:

Circular Single Linked list
Single Linked List
Doubly Linked List
Circular Doubly Linked List

Kenapa namanya susah – susah ya? Tapi gapapa, mungkin semakin susah dilafalkan. Maka semakin bagus!

Single linked list dan Circular single linked list

Linked List (geeksforgeeks)

Linked list adalah data structure linear. Nah tidak seperti array, linked list itu elemennya tidak disimpan bersebelahan. Elemen – elemen dari linked list disambung dengan pointer. Dalam kata lain, linked list adalah sekumpulan data yang dihubungkan dengan pointer data sebelumnya. Nah, apa itu circular single linked list? Untung dapat mengerti, kita butuh bantuan dari gambar dibawah ini.

Circular Single Linked List (geeksforgeeks)

Nah, bisa kita lihat, tidak seperti linked list biasanya, circular single linked list tidak mempunyai null di akhir. Circular linked list sendiri pengertiannya adalah linked list yang setiap nodusnya terkoneksi sehingga membuat bentuknya seperti melingkar. Nodus terakhirnya mengandung pointer dari nodus pertama. Implementasi dari circular linked list adalah pada pembuatan antrian.

Doubly Linked List

Doubly Linked List (DLL) mengandung pointer ekstra yang biasanya disebut previous pointer. Selebihnya sama dengan linked list yang biasa.

Doubly Linked List dalam bahasa C (geeksforgeeks)

Karena ada pointer ekstra yang bernama previous, maka pada doubly linked list, operasi dapat dilakukan secara dua arah. Nah keuntungannya dapat dirasakan ketika kita ingin menghapus nodus sebelumnya. Pada single linked list, kita tidak dapat melakukannya karena arahnya hanya next, tidak dapat ke belakang lagi. Nah ternyata doubly linked list ini juga mempunyai kekurangan. Mempunyai pointer dengan dua arah membuat Doubly Linked List ini mempunyai ukuran data yang besar. Jika kita tidak membutuhkan pointer dengan dua arah, sebaiknya permudah hidup dengan hanya menggunakan single linked list.

Circular Doubly Linked List

Ternyata selain ada circular single linked list, circular double linked list juga ada loh! Gimana kalo ada triple linked list ya? Daripada dipikirin yaudah nih arti dari double linked list. Double linked list adalah linked list yang mempunyai karakterisitik dari doubly linked list dan circular linked list. Circular Doubly Linked List mempunyai pointer next dan previous dan bentuknya melingkar, sehingga tidak ada null di akhir.

Circular Doubly Linked List (geeksforgeeks)

Referensi untuk rangkuman:

Stack & Queue

Jadi ini adalah rangkuman dari pertemuan keempat tepatnya pada tanggal 3 Maret 2020. Nah pada post kali ini, saya akan merangkum tentang stack & queue pada data structure. Mari kita bahas mereka satu persatu.

Stack

Kita semua pasti familiar dengan game yang bernama DoTA kan? Sebenernya ngga terlalu berhubungan sih, tapi dalam DoTA ada teknik yang bernama stack. Teknik ini membuat monster jungle dapat spawn meskipun seharusnya tidak bisa spawn karena masih ada monster jungle. Nah, stack membuat monster jungle itu lebih banyak. Bisa kita simpulkan bahwa stack itu jika di data structure akan menyimpan elemennya dalam urut. Nah, kalo di dalam DoTA, kita harus membuat monster jungle pergi dari spawn box agar monster lainnya bisa spawn lagi. Hal ini mirip dengan data structure, yaitu ketika kita mau menambah elemen ditengah misalnya, kita harus membongkar elemennya dari paling atas, lalu kita bisa menghapus atau menambah elemen di dalamnya. Nah, dalam stack ini, ada dua urutan yaitu LIFO (last in first out) atau FILO (first in last out). Untuk lebih jelas, sebaiknya lihat gambar yang saya akan lampirkan dibawah.

Ilustrasi Stack dari geeksforgeeks

Biasanya, operasi dari stack ada 3, yaitu push, pop, dan top. Push adalah operasi untuk menambah sesuatu dari atas dari stack paling atas (top). Pop adalah operasi untuk menghapus sesuatu dari stack paling atas (top). Sedangkan, top adalah operasi untuk menampilkan siapa yang ada di posisi top sekarang. Contoh dari operasi - operasi tersebut dapat dilihat dibawah.

Ilustrasi operasi yang ada di Stack dari BinusMaya

Queue

Nah sekarang kita akan membahas tentang queue atau antrian. Jika dalam stack kita menambah data dari paling atas (top), dalam queue kita menambah data dari paling belakang. Ilustrasi yang paling gampang adalah ketika kita mengantri untuk masuk ke dalam restoran yang ramai. Nah jika kita datang paling lama dari yang lain, maka dalam waiting list, kita akan ada di paling bawah kan? Nah, orang yang ada di waiting list nomor pertama pasti akan mendapatkan tempat duduk duluan. Ketika ada yang ingin masuk ke dalam waiting list lagi, maka orang itu akan mendapatkan tempat di waiting list paling bawah. Nah, di dalam queue di data structure cara kerjanya mirip seperti itu. Jadi, data yang paling awal dimasukkan yang dihapus dan data yang baru ditambahkan yang ditambah. Untuk lebih jelasnya dapat dilihat pada gambar dibawah. Urutan dari queue adalah FIFO (first in, first out). Bukan merk hape yang itu ya...

Ilustrasi queue dari geeksforgeeks

Dalam queue, data yang masuk dimasukkan ke dalam rear dan data yang keluar dikeluarkan dari front. Operasi - operasi yang dapat digunakan pada queue adalah push, pop, dan queue. Operasi push digunakan untuk menambah data dari paling belakang dari queue. Operasi pop digunakan untuk menghapus data dari paling depan dari queue. Sedangkan fungsi front digunakan untuk melihat data apakah yang ada di front. Operasi - operasi ini lebih jelasnya dapat dijelaskan dengan gambar dibawah.

Ilustrasi operasi pada Queue dari BinusMaya

Perbedaan pada Stack dan Queue

Perbedaan yang sangat mendasar antara Stack dan Queue terletak pada penghapusan data. Jika di dalam Stack data yang dihapus adalah data yang baru ditambahkan, dalam Queue data yang dihapus adalah data yang paling pertama ditambahkan.

Sumber:

Hashing & Hash Tables, Trees & Binary Trees

Halo ges!! Pada post kali ini untuk pertemuan kelima, kita akan membahas tentang Hashing & Hash Tables, Trees & Binary Trees yang merupakan topik dari GSLC pada hari ini. Sebelumnya jangan lupa untuk jaga diri kita masing - masing ya. Soalnya, semakin banyak korban dari wabah itu sehinga kita semua malah harus belajar sendiri di rumah deh. Nah, tanpa basa basi mari kita bahas topik pada pertemuan kelima ini satu persatu.

Hashing

Hashing adalah sebuah fungsi yang dapat mengubah sebuah string menjadi bentuk yang lebih simpel yang dapat merepresentasi string tersebut. Contohnya adalah ketika kita menyimpan nomor telepon. Nomor telepon itu kan panjang, sekitar 12 digit. Nah dengan hashing, kita hanya perlu mengambil 3 angka belakang. Kenapa tidak 3 angka depannya aja? Karena jika kita mengambil 3 digit terdepan, pasti banyak nomor yang sama ketika nomor itu dihash.

Hash Tables

Hash table adalah sebuah tabel dalam bentuk array yang menyimpan string. Index dari tabel itu adalah data yang dihash dan nilainya merupakan string itu sendiri. Untuk lebih jelasnya, mari kita lihat ilustrasi dibawah.

Ilustrasi Hashing dari geeksforgeeks

Nah, ilustrasi tersebut menjelaskan kita tentang hash table yang dibuat berdasarkan operasi x%10. Kita ambil angka pertama yaitu 11. 11%10 adalah 1, sehingga dalam hash table, index ke 1 dimasukkan angka 11. Begitu juga berlaku terhadap 12 yang dimodulus 10. Hasilnya kan 2, sehingga pada indeks ke 2 kita masukkan value 12.

Jika dibuat tabelnya, lebih jelas seperti ini

Contoh lainnya adalah ketika kita ingin membuat hash table dari 6 String yaitu: Dem, Mezquito, Budi, Chandra, Zidan. Tabelnya akan kita buat dengan ukuran 26 maksimalnya.

Pembuatan Hash tablenya adalah seperti diatas

Fungsi dari Hash

Hash mempunyai beberapa fungsi yaitu:

Mid-square, Division (yang biasa dipakai), Folding, Digit Extraction, dan Rotating Hash.

Mid-Square

Mid-square merupakan fungsi yang mengambil nilai string dari tengah. Jika keynya merupakan string, string tersebut akan diubah nilainya menjadi angka. Contohnya adalah ketika kita mempunyai key 5010, 5011, 5012, 5013, dan 5015. Kita harus memangkatkan nilai tersebut dan mengambil string ditengahnya.

Tabel dari Mid-Square

Division

Division merupakan fungsi yang membagi nilai dari string dengan operator modulus. Biasanya bentuk dari fungsi ini adalah sebagai berikut.

Fungsi: h(z) = z mod M

z = keynya

M = nilai yang digunakan untuk memodulus z. Biasanya berupa ukuran dari tabelnya atau ukuran dari memori yang terpakai.

Contoh:

Kita mempunyai Budi, Abah, dan Caca. Kita akan menambahkan masing masing ASCIInya dan memodulusnya dengan ukuran tabelnya. Anggap saja ukurannya adalah 98.

"Budi" akan disimpan pada lokasi (66+117+100+105) % 98 = 14

"Abah" akan disimpan pada lokasi (65+98+97+104) % 98 = 70

"Caca" akan disimpan pada lokasi (96+97+99+97) % 98 = 95

Folding

Folding merupakan fungsi yang memisahkan string lalu menambahkan bagiannya menjadi sebuah hash key.

Contohnya sebagai berikut:

Tabel dari Folding

Digit Extraction

Digit extraction adalah fungsi yang mengambil digit dari angka yang diberikan.

Contoh: 15.987.654

Jika kita menggunakan fungsi digit extraction untuk mengambil digit 1, 3, dan 5, Maka kita akan mendapatkan kode hashnya yaitu 197.

Rotating Hash

Fungsi rotating hash dapat dilakukan ketika kita melakukan fungsi hash apapun. Ketika kita mendapatkan hash codenya, selanjutnya kita akan mengacaknya atau bisa disebut rotation.

Contoh:

Nilai hashnya: 857

Hasil Rotasi: 785

Collision

Ini akan terjadi jika kita mempunyai string yang sama. Misalnya kita akan memasukkan data dari string "Budi", "Caca", "Danang" "Bambang". Untuk masalah ini kita dapat mengatasinya dengan Linear Probing dan Chaining.

Linear Probing

"Budi" dan "Bambang" mempunyai huruf depan yang sama kan, makanya kita akan menaruh Bambang di 1, Caca di 2, Danang di 3, dan Budi di 4. Itu adalah cara Linear Probing bekerja, yaitu menaruh datanya di tempat manapun yang kosong. Tapi cara ini mempunyai kerugian yaitu jika terjadi banyak data yang sama yang menyebabkan collision, waktu untuk mencarinya akan lebih kompleks.

Tabel dengan teknik Linear Probing

Chain

Nah, dengan chain, kita dapat menyimpan data setiap string dalam sebuah rantai atau linked list. Contohnya Bambang->Budi di 1, Caca di 2, Danang di 3, Bambang di 4.

Tabel dengan teknik Chain

Aplikasi dari Hash Table

Hash table masih digunakan sampai sekarang. Contoh paling gampangnya adalah ketika kita memasukkan email dan password untuk login di BinusMaya. Email dan password kita akan diubah menjadi hash code dan akan dibandingkan dengan hash code yang ada di dalam database BinusMaya. Jika kodenya sesuai dan tabelnya sesuai, maka email dan password berhasil diverifikasi dan kita dapat masuk ke dalam dashboard BinusMaya. Jika email dan password tidak diubah menajadi kode hash, maka akun kita akan lebih rentan untuk diretas orang.

Trees

Trees adalah kumpulan dari satu atau lebih nodus.

Contoh Tree dari BinusMaya

Derajat dari pohon tersebut adalah 3

Derajat C adalah 2

Derajat F adalah 0

Parent dari C adalah A

Parent dari E adalah B

Leluhur dari F dan G adalah C dan A

Tingginya dalah 3

Saudara dari F adalah G

Binary Tree

Binary tree adalah sebuah pohon yang anaknya mempunyai paling banyak 2 anak (atau bisa disebut juga dengan cabang). Biasanya anak atau cabangnya dapat disebut dengan anak kiri dan kana karena hanya berjumlah 2.

Contoh Binary Tree dari geeksforgeeks

Pengaplikasian dari Binary Tree

Contoh paling gampangnya adalah system file dari sebuah komputer.

  /   <-- root
  /      \
...        home
      /          \
   ugrad        course
    /          /    |    \
  ...        cs101 cs112 cs113

System file komputer dari geeksforgeeks

Jika kita menggunakan tree, maka waktu yang diperlukan untuk mencari dan mengakses sebuah key akan lebih cepat dari linked list, namun lebih lambat dari array. Bisa kita katakan bahwa kecepatan dari tree untuk mengakses data adalah rata - rata dari linked list dan array. Kita juga dapat menambah atau menghapus data dengan kecepatan rata - rata dari array dan unordered linked list. Menambah atau menghapus data menggunakan tree lebih cepat dari array tapi lebih lambar dari unordered linked list. Terakhir, tree itu mirip seperti linked list, yaitu tidak mempunyai batas data. Array kan mempunyai batasnya, nah dengan tree kita dapat menyimpan data tanpa takut terbatasi seperti ketika menggunakan sebuah array. Kesimpulannya, gunakanlah tree jika ingin akses data yang tidak terlalu cepat atau lambat dan tanpa ketakutan untuk menggunakannya terus menerus karena tidak dibatasi.

Sumber:

Binary Search Tree

Pengertian Binary Search Tree

Binary search tree adalah sebuah metode dari data structure yang mempunyai ciri sebagai berikut:

Bagian kiri dari subtree adalah nodus yang mempunyai nilai yang lebih kecil
Bagian kanan dari subtree adalah nodus yang mempunyai nilai yang lebih besar
Bagian kiri dan kanan dari subtree harus berupa binary search tree juga

Mencari Sebuah Angka (searching)

Ilustrasi Binary Search Tree dari geeksforgeeks

Bisa kita lihat dari contoh diatas, bagian kiri dari binary search tree merupakan nilai yang kecil sedangkan bagian kanannya adalah nilai-nilai yang besar.

Kita bisa mengambil contoh angka 7. Ketika angka 7 ingin dicari pada binary search tree diatas, maka dia akan mengecek. Apakah 8 lebih kecil atau besar dari 7? Karena lebih kecil, maka 7 akan dicari di bagian kiri. Kemudian, akan dicek lagi. Apakah 7 lebih kecil daripada 3? Jawabannya adalah tidak, sehingga 7 dicari dibagian kanan. Lalu ketika sampai di 6, karena 7 lebih besar daripada 6, maka lokasi 7 pasti di kanan dari cabang si 6. Begitulah kira - kira cara kerja dari binary search tree.

Memasukkan Sebuah Angka pada BST (insertion)

         100                               100
        /   \        Insert 5            /    \
      20     500    --------->          20     500 
     /  \                              /  \  
    10   30                           10   30
                                     / 
                                    5

Coba kita lihat illustrasi ketika kita akan melakukan insertion pada binary search tree. Nah, pada contoh diatas, saya ingin memasukkan 5 pada binary search tree tersebut. Karena angka 5 lebih kecil daripada 100, maka saya akan menaronya di bagian kiri dari cabang 100. Lalu karena lebih kecil dari 20, saya taro lagi di bagian kiri dari 20. Nah ketika bertemu 10. otomatis 5 akan ditaro di kiri cabang dari 10 karena nilainya lebih kecil daripada 10.

Menghapus Sebuah Angka pada BST (delete)

Setelah kita mempelajari insertion, sekarang kita akan membahas tentang delete. Seperti namanya sendiri, kita akan menghapus angka yang ada di binary search tree sesuai dengan angka yang ingin dihapus. Kemungkinan dan cara dalam melakukan delete pada binary search tree adalah sebagai berikut:

1) Nodus yang ingin di hapus ada pada daun: Yaudah hapus aja langsung, gampang kan?

              50                            50
           /     \         delete(20)      /   \
          30      70       --------->    30     70 
         /  \    /  \                     \    /  \ 
       20   40  60   80                   40  60   80

2) Nodus yang ingin di hapus hanya mempunyai satu cabang atau keturunan: Salin keturunannya lalu taro di tempat di mana angka tersebut di hapus.

              50                            50
           /     \         delete(30)      /   \
          30      70       --------->    40     70 
            \    /  \                          /  \ 
            40  60   80                       60   80

3) Nodus yang ingin di hapus hanya mempunyai dua cabang atau keturunan: Cari keturunan di bagian kanan yang mempunyai nilai paling kecil. Dalam contoh ini, karena 60 lebih besar dari 50 dan kebetulan paling kecil di bagian kanan 50, maka angka ini naik jadi paling atas dan angka 50 dihapus.

             50                            60
           /     \         delete(50)      /   \
          40      70       --------->    40    70 
                 /  \                            \ 
                60   80                           80

Sumber:

https://www.geeksforgeeks.org/binary-search-tree-data-structure/

https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/

https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/

Aplikasi Sederhana Double Linked List

Pada kesempatan kali ini, saya diberi tugas membuat sebuah aplikasi dengan syarat berikut:

aplikasi dibuat menggunakan linked list
aplikasi dibuat menggunakan double linked list.
aplikasi dibuat bisa input barang (nama dan qty), bs edit qty dan bisa menghapus item yang salah.
ketika checkout anda akan ditampilkan hasil total dari perhitungan qty (seperti struk minimarket)
harga yang tertera random, namun hasil penjumlahan benar (totalnya benar)
setelah tahap mau bayar, di bawah tulisan total, tuliskan gratis, “kindness is free”

Nah langsung saja kita lihat kodingnya seperti apa!

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node{
char barang[101];
int quantity;
int harga;
struct node *next,*prev;
} *head = NULL , *tail = NULL , *curr, *temp;
void push (char *item, int x)
{
curr = (struct node*) malloc(sizeof(struct node));
strcpy(curr->barang, item); //nama barangnya masuk ke barang[101]
curr->quantity = x;
curr->harga = (rand()%(30000-1000 + 1) + 1000); //(rand()%(rangepalingtinggi - rangepalingrendah + 1) + rangepalingrendah)
curr->next = curr->prev = NULL;
if(head == NULL)
{
head = tail = curr;
}
else if(strcmp(item,head->barang) < 0) //input A sedangkan C udah di dll, maka A masuk dluan
{ //Buba di Head, Abdi mau dimasukkin
curr->next = head;
head->prev = curr;
head = curr;
}
else if(strcmp(item,tail->barang) > 0) //push dari blkg
{
tail->next = curr;
curr->prev = tail;
tail = curr;
}
else
{
temp = head;
while(strcmp(item, temp->next->barang) < 0) //temp ke next lbh kecil qty nya
{
temp = temp->next;
}
curr->next = temp->next;
temp->next->prev = curr;
temp->next = curr;
curr->prev = temp;
}
}
void pop(const char *hapus)
{
if(head == NULL)
{
printf("There is no item to be removed...\n");
}
else if(head == tail)
{
free(head);
head = tail = NULL;
}
else if(strcmp(head->barang,hapus) == 0)
{
curr = head;
head = head->next;
free(curr);
head->prev = NULL;
}
else if(strcmp(tail->barang,hapus) == 0)
{
curr = tail;
tail = tail->prev;
free(curr);
tail->next =NULL;
}
else
{
curr = head;
while(curr != NULL && strcmp(curr->barang,hapus) != 0) // ke next kalo ga ketemu
{
curr = curr->next;
}
if(curr == NULL)
{
printf("There is no item with name ""%s"" entered!\n", hapus);
}
else
{
curr->next->prev = curr->prev;
curr->prev->next = curr->next;
free(curr);
}
}
}
void edit(const char *editbarang , int editqty)
{
struct node *temp = head;
while(temp != NULL && strcmp(temp->barang,editbarang)!=0)
{
temp = temp->next;
}
if(temp != NULL)
{
temp->quantity = editqty;
}
else
{
printf("There is no item with name ""%s""to be edited!\n", editbarang);
}
}
void print()
{
int i = 1;
curr = head;
printf("These are your item list: \n");
while(curr != NULL)
{
printf("%d. %s %d\n",i ,curr->barang, curr->quantity);
curr = curr->next;
i++;
}
printf("\n");
}
void popsemua()
{
while(head != NULL) //looping sampai ketemu tail
{
temp = head;
head = head->next;
free(temp);
}
}
int main()
{
int input = 0;
int qty = 0;
int count = 0;
int total = 0;
char nama[101];
printf("Welcome to the Item Application!\n");
do{
printf("These are the menu lists: \n");
printf("1. Add item\n");
printf("2. Edit your item quantity\n");
printf("3. Remove item\n");
printf("4. Checkout item(s)\n");
printf("5. Exit\n");
printf("Choose menu: ");
scanf("%d", &input); getchar();
if (input==1)
{
do
{
printf("Enter item name [1-100]: ");
scanf("%[^\n]", nama); getchar();
}
while (strlen(nama)<1 || strlen(nama)>100);
do
{
printf("Enter Quantity of your item [1-10]: ");
scanf("%d", &qty); getchar();
} while (qty<1 || qty>10);
push(nama,qty);
printf("\n");
}
else if (input==2)
{
if(head == NULL)
{
printf("What are you going to edit if your list is empty???\n");
}
else
{
printf("Input item name to be edited: ");
scanf("%[^\n]", &nama); getchar();
printf("Input the quantity to be changed: ");
scanf("%d", &qty); getchar();
edit(nama,qty);
printf("Item Successfully edited!\n");
printf("\n");
}
}
else if (input==3)
{
printf("Which item you want to remove?\n");
scanf("%[^\n]", &nama); getchar();
pop(nama);
printf("Item successfully removed!\n");
printf("\n");
}
else if (input==4)
{
total = 0;
count = 1;
print();
printf("\n");
curr = head;
while(curr != NULL) //currnya ada isi
{
printf("| No | Name | Quantity | Price | Total |\n");
printf(" %d. %s %d %d %d\n", count, curr->barang, curr->quantity, curr->harga, curr->quantity * curr->harga);
total = total + (curr->quantity * curr->harga);
curr = curr->next;
count++;
}
printf("\n");
printf("Subtotal: %d\n", total);
printf("Since kindness is free, these are all free!");
printf("\n");
popsemua();
}
else if (input==5)
{
printf("You are exitting this item application!\n");
printf("Goodbye, See you next time!\n");
popsemua();
break;
}
}while(input != 5);
return 0;
}

Nah diatas merupakan koding untuk membuat aplikasi ini. Terima kasih sudah mampir kesini!

AVL Tree

Pengertian AVL Tree

AVL tree adalah sebuah tree yang mirip dengan Binary Search Tree yang mempunyai fungsi yang sama, namun mempunyai aturan sendiri. Di dalam Binary Tree, jika kita menginsert sebuah angka, pasti akan ditampung di kiri atau kanan dari tree tersebut, tergantung dengan nilainya kurang dari atau lebih dari (kalau kurang, di taruh kiri dan kalau lebih, ditaruh di kanan). AVL Tree ini mempunyai aturan bahwa perbedaan subtree kiri dan kanan tidak boleh melebihi 2. Untuk lebih jelasnya, mari kita lihat contoh berikut.

AVL Tree dari geeksforgeeks

Pada contoh di atas, tree tersebut merupakan sebuah AVL tree karena selisih dari subtree kiri dan kanan dari root kurang dari 2 (paling banyak 1). Kita dapat menghitung jumlah subtree kiri dengan melihat paling bawahnya dari kiri. Pada gambar tersebut paling bawahanya adalah 4. Nah, kita menghitung subtreenya dari 12. Di kiri dari 12 ada 8 lalu dikirinya lagi ada 5, lalu terakhir ada 4. Nah jumlah subtree kiri ada 3 sedangkan jumlah subtree kanan ada 2 yaitu 18 dan 17. Selisih dari subtree kiri dan kanan adalah 1, sehingga memenuhi syarat untuk membuat AVL tree. Coba kita lihat contoh yang tidak memenuhi syarat AVL tree.

Tree yang bukan AVL dari geeksforgeeks

Gambar diatas merupakan contoh dari AVL tree yang salah. Mari kita lihat salashnya di mana. Seperti yang saya bilang sebelumnya, sebuah AVL tree harus mempunyai perbedaan subtree kanan dan kiri kurang dari 2. Nah, jika kita hitung subtree kiri, maka kita bisa lihat bahwa ada 4 subtree di kiri. Pada subtree kanan terhadap 2 subtree. Selisih subtree kiri dan kanan adalah 2 sehingga tidak memenuhi syarat dari AVL tree.

Insertion

Sebenarnya untuk melakukan insertion, langkah-langkah yang dilakukan tidak terlalu berbeda dengan insertion pada Binary Search Tree. Yang membedakannya adalah ketika kita sudah selesai menginsert, kita mengecek apakah tree tersebut seimbang (selisih subtree kanan dan kiri paling banyak 1) atau tidak seimbang. Jika seimbang, maka kita akan membiarkannya saja sedangkan jika tree kita tidak seimbang, maka kita harus membuatnya seimbang. Cara untuk membuatnya seimbang adalah dengan single rotation atau double rotation.

Sebuah tree mempunyai 4 kemungkinan atau kasus untuk tidak seimbang yaitu:

Left Left case
Right Right case
Left Right case
Right Left case

Left left dan right right case dapat diselesaikan dengan single rotation, sedangkan left right dan right left case bisa diselesaikan dengan double rotation.

Left Left Case

Left left case adalah kasus dimana treenya tidak seimbang karena lebih berat di kiri.

         6                                      4 
        / \                                   /   \
       4   10      Right Rotate (6)          2      6
      / \          - - - - - - - - ->      /  \    /  \ 
     2   5                                1    3  5   10
    / \
   1   3

Pada kasus di atas, angka 6 menyebabkan ketidakseimbangan dari tree tersebut yang menyebabkan treenya berat ke kiri sehingga harus dilakukan single rotation. Karena treenya berat di kiri, maka ada beberapa bagian yang harus dibuat ke kiri sehingga bisa seimbang. Untuk lebih gampang untuk membayangkannya, anggap saja angka 6 adalah sebuah katrol. Karena titik tumpunya adalah di 6, dan untuk dapat seimbang harus ditarik ke kanan, maka titik tumpu akan menjadi 4 sehingga semua yang ada di kiri bergerak ke kanan.

Right Right Case

  11                              14
 /  \                            /   \ 
2    14     Left Rotate(11)      11    18
    /  \   - - - - - - - ->    / \    / \
   12  18                     2  12  16 20
       / \
      16 20

Kasus di atas sangat mirip dengan kasus left left case, yang membedakannya adalah treenya lebih berat ke kanan sehingga perlu juga dilakukan single rotation agar tree tersebut bisa seimbang.

Left Right Case

    15                              15                           12
    / \                            /   \                        /  \ 
  10   20  Left Rotate (10)       12   20  Right Rotate(15)   10    15
  / \      - - - - - - - - ->    /  \      - - - - - - - ->  / \    / \
5   12                         10   13                      5  11  13 20
    / \                        / \
  11   13                    5   11

Nah kita harus lihat terlebih dahulu kenapa case ini dinamakan left right case. Lihatlah pada subtree kiri dari 15. Kita bisa lihat bahwa subtree terdalamnya ada di 11 dan 13. Karena itulah, treenya berat di 2 tempat di kiri, sehingga kita harus membuat bagian disitu seimbang terlebih dahulu. Nah untuk itu kita harus merotasi 10 dan setelah kita rotasi, ternyata masih belum seimbang. Oleh karena itu, kita harus merotasi 15 sehingga dapat seimbang. Oleh karena itu kasus ini memerlukan dua kali rotasi yang disebut dengan double rotation.

Right Left Case

  15                           15                            17
  / \                          / \                          /  \ 
 1   20   Right Rotate (20)   1  17      Left Rotate(15)   15   20
    / \  - - - - - - - - ->     /  \   - - - - - - - ->  / \    / \
  17  21                      16    20                  1  16  19 21
  / \                              /  \
16  19                            19   21

Kasus ini mirip dengan kasus left right case hanya perbedaannya adalah berat di subtree kanan dari 15 lalu berat di subtree kiri darai 20. Diperlukan metode double rotation sehingga bisa seimbang lagi.

Deletion

Untuk melakukan deletion, cara melakukannya sama dengan ketika kita melakukan deletion pada Binary Search Tree. Yang membedakannya adalah ketika kita melakukan deletion dan membuat tree itu tidak seimbang, maka kita harus melakukan rotaion agar tree tersebut seimbang.

Kita ingin mendelete 55

Karena yang di delete adalah 60, maka tree di kiri menjadi tidak seimbang. Untuk membuatnya seimbang, diperlukan rotation agar treenya menjadi seimbang.

Rotation terhadap 55

Kita melakukan rotasi terhadap 55 sehingga 65 akan menempati 55 dan 55 akan ada di subtree kiri dari 65.

Rotasi terhadap 50

Setelah melakukan rotasi terhadap 55, ternyata tree masih tidak seimbang sehingga 50 harus dirotasikan. Karena 50 dirotasi ke kiri, maka 40 mengambil posisi dari 25. Setelah itu dilakukan lagi rotasi terhadap 50 ke kanan sehingga 40 menempati tempat 50 dan treenya menjadi seimbang.

Hasil AVL Tree yang sudah dilakukan deletion

Bisa disimpulkan bahwa AVL tree merupakan tree yang mirip dengan Binary Search Tree namun mempunyai sedikit perbedaan. AVL tree mempunyai syarat agar subtree kiri dan kanan mempunyai selisih 1 sehingga subtree tersebut bisa seimbang.

Heaps & Tries

Heap

Minggu lalu kita sudah membahas AVL Tree dan sekarang kita akan membahas Heap & Tries. Heap adalah sebuah struktur data dengan konsep binary tree. Heap mempunyai dua jenis yaitu:

Min - heap
Max - heap
Min - Max heap

Heap dapat diimplementasikan dengan linked list, namun akan lebih gampang jika menggunakan array. Agar lebih jelas, lebih baik kita lihat gambar berikut ini.

Heap dari geeksforgeeks

Min - Heap

Pada min - heap terdapat aturan agar heap itu dapat dibuat. Aturan tersebut adalah angka atau huruf yang ada di root harus paling kecil daripada anak - anaknya. Hal ini juga berlaku pada subtree lainnya secara rekursif. Jadi, yang diatas harus lebih kecil daripada bawahnya.

Insertion

Berbeda dengan BST yang mempunyai aturan kiri harus yang kecil dan kanan yang besar, min - heap hanya menghiraukan atasnya. Pada kasus min - heap berarti atasnya harus lebih kecil daripada bawahnya. Agar kita mengerti cara menginsertnya, lihat gambar berikut:

Kita akan menginsert angka 3, 1, 6, 5, 2, 4

Karena angka pertamanya adalah 3, maka kita langsung insert angka tersebut menjadi root.

Insert 1

Nah pada kasus diatas, angka 3 lebih besar daripada 1. Karena aturannya tidak memperbolehkan hal itu untuk terjadi, maka angka 1 dan 3 harus ditukar menjadi seperti berikut:

Selanjutnya, kita akan menginsert angka 6.

Karena angka 1 sudah lebih kecil daripada 6, maka tidak perlu ditukar seperti angka 3. Sehabis itu, kita akan menginsert angka 5 di array selanjutnya.

Karena angka 3 sudah lebih kecil daripada 5, kita tidak perlu menukarnya lagi. Lanjut, kita insert angka 2.

Nah, ini kita harus menukar angka 3 dan 2 sehingga menjadi berikut:

Selanjutnya, kita insert angka terakhir kita yaitu 4.

Angka 6 tidak lebih kecil daripada 4 sehingga harus ditukar.

Setelah ditukar, jadilah sebuah min - heap, horeee hhhhh.

Deletion

Pada min - heap, terdapat aturan agar deletion dapat terjadi dengan benar. Step - stepnya adalah sebagai berikut:

Siapkan heapnya terlebih dahulu (ya iyalah kalo ngga gimana mau di delete bang)
Delete nilai yang ingin kamu delete (kalo mau delete 2, ya hapus 2 jangan 5).
Tempat dari nilai yang kamu delete tadi diganti dengan nilai paling bawah kanan.
Cek nilai yang lainnya. Sehabis kamu ganti apakah ada yang tidak sesuai dengan aturannya? Kalo iya, tukar nilainya terus - terusan sampai heapnya benar.

Mari kita lihat contoh agar lebih mengerti.

Pada heap tree tersebut, kita ingin mendelete angka 2 sehingga menjadi seperti berikut.

Karena 9 merupakan nilai yang ada di paling bawah kanan, maka 9 akan mengambil tempat 2.

Selanjutnya, kita akan mengecek apakah ada node yang tidak memenuhi aturan. Nah karena 9 ternyata lebih besar daripada 5 dan 7, maka kita mengambil 5 untuk menjadi root. Kita tidak mengambil 7 karena 5 adalah nilai yang paling kecil diantara mereka ber 2.

Deletion sukses dilakukan jadi Horeee lagiii HHHHHH.

Max - Heap

Max - heap intinya sama saja dengan min - heap. Hanya, yang membedakan adalah aturannya. Angka atau huruf yang ada di root harus paling besar daripada anak - anaknya. Ini juga berlaku pada subtree lainnya secara rekursif. Jadi, yang diatas harus lebih besar daripada bawahnya.

Insertion

Insertion dari max - heap sangat mirip dengan min - heap. Kita hanya perlu menukar jika ada angka yang lebih besar.

Contoh:

Ceritanya kita akan memasukkan angka 6, 4, 8, 2, 7, 1

Insert 6:
      6

Insert 4:
      6
    /    
   4

Insert 8:
      6             Swap 8 sama 6          8    
    /    \          ------------>        /   \
   4      8                             4     6

Insert 7:

       8                                         8
     /   \          Swap 7 dengan 4            /   \
    4     6         ---------------->         7     6
  /   \                                     /   \
 2     7                                   2     4

Deletion

Insertion dari max - heap mirip dengan min - heap, itu juga berlaku pada deletionnya. Agar lebih jelas, lihatlah contoh berikut:

Misalnya heapnya dengan aturan Max - heap:
      10
    /    \
   5      3
  / \
 2   4

Elemen yang mau dihapusnya yaitu 10

Process:
Elemen paling kanan bawahnya adalah 4

Step 1: Hapus angka 10 yaitu angka yang ada di root
      
    /    \
   5      3
  / \
 2   4
Step 2: Angka 4 itu paling kanan bawah, jadinya gantiin tempat 10
      4
    /    \
   5      3
  / 
 2   
Step 2: Tukar angka yang tidak sesuai dengan aturannya (dalam kasus ini angka 4 dan 5)
Final Heap:
      5
    /    \
   4      3
  / 
 2

Min - Max Heap

Nah ini adalah bentuk terakhir dari heap. Kalo gamer bilang sih Final Boss nya dari heap. Jadi kalo belum bisa ngalahin/ngertiin yang sebelumnya. mending jangan liat ini dulu, oke?

Nah aturan yang ada di heap ini adalah rootnya mempunyai aturan min - heap, lalu dibawahnya menganut aturan max - heap, lalu dibawahnya lagi menganut aturan min - heap. Jadi aturannya selang - seling begitu.

Insertion

Nah setelah kita mengetahui aturannya, mari kita coba menginsert beberapa angka hingga menjadi min - max heap.

Contohnya kita akan menginsert 6, 4, 8, 2, 7, 1

Insert 6:

Min:    6

Insert 4:
Min:      6       6 harus diswap dengan 4            4
        /         ----------------------->         /   
Max:   4                                          6

Insert 8:
Min:      4               
        /    \          
Max:   6      8

Insert 2:
Min:       4
         /   \         
Max:    6     8        
       /
Min:  2

Insert 7:

Min:       4                                            4
         /   \                                        /   \
Max:    6     8            ---------------->         7     8
       / \                                         /   \
Min:  2   7                                       2     6

Insert 1:
Min:       4
         /   \         
Max:    7     8        
       / \   /
Min:  2   6 1

Deletion

Berikut adalah langkah - langkah untuk menghapus sebuah node pada min - max heap:

Sekali lagi untuk yang terakhir kalinya, heapnya harus ada lah
Tentukan mana yang mau dihapus
Setelah tau yang mana mau dihapus, liatin dulu ini heap apa bukan? Kalo bukan ngapain di delete coba?
Nah habis dipastiin, hapusin yang kamu mau
Ganti posisi yang dihapus tersebut dengan node yang paling bawah kanan
a. Downheapmin: Cari angka terkecil dari anak dan cucu dari node yang sudah dihapus. Setelah itu, ganti saja tempatnya
b. Downheapmax: Ini kebalikannya downheapmin

Nah, kalau kurang jelas, mari kita langsung ke contohnya.

Try to understand delete-min of Min-Max Heap - Stack Overflow

Misalnya kita mau delete 9. Hal yang akan terjadi adalah begini

Nah, lalu kita akan mereplacenya dengan kanan paling bawah, yaitu 90.

Kita lalu menerapkan down-heap min. Karena 20 lebih kecil daripada 90, kita harus menukarnya jadi seperti ini:

Tries

Pengertian tries dari Medium.com

Seperti yang telah diberikan diatas, tries itu adalah sebuah kata yang berasal dari kata "retrieve". Jadi trie itu adalah sebuah data structure yang mempunyai sifat tree yang digunakan untuk menyimpan alfabet atau string dari sebuah kata. Menyimpannya adalah dengan membuat cabang terus-terusan ke bawah.

Cara menginsert di dalam sebuah trie

Nah, dalam membuat sebuah trie, kita hanya perlu mengurut alfabetnya sehingga menjadi urut. Dari gambar diatas, pastinya tidak sulit untuk mengerti trie, bukan? (iyain aja sumpah orang gampang kok)

Demikian rangkuman untuk Heaps & Tries. Ingat saja bahwa heap ada min, max, dan min - max heap yang mempunyai aturan yang berbeda - beda. Ada juga tries yaitu salah satu tipe dari tree yang mengatur alfabet.

The Creation Trio