AVL Tree

AVL Tree adalah salah satu jenis Binary Search Tree seimbang yang paling dasar. Dalam bentuk AVL, akan dilakukan konsep menyeimbangkan bentuk BST agar di kedua sisi memiliki kedalaman yang sama dan maksimum selisih kedalaman child tiap nodenya 1. Hal ini dilakukan untuk mempercepat dalam proses pencarian dan menghindari kemungkinan worst case scenario pada BST biasa (worst case = n kali pencarian) karena AVL Tree memiliki worst case yang mendekati log n.

Seperti yang diketahui, AVL Tree merupakan BST yang dimodifikasi dengan cara menyeimbangkan sisi kiri dan kanan tree agar proses pencarian dapat berjalan lebih cepat. Oleh sebab itu, metode dasar AVL menyerupai BST biasa yaitu dengan memiliki aturan insert, delete, dan searching yang sama. Hal yang membedakan hanyalah dilakukannya proses penyeimbangan setiap kali metode insert dilakukan. Contohnya pada kasus berikut ini :

Contoh Tree yang tidak balance menjadi balance

Angka-angka yang terletak diatas tiap node adalah selisih kedalaman node untuk sisi kiri dan kanan.
Dapat dilihat pada node A di tree paling kiri tertulis angka 2, hal ini karena kedalaman node A (bukan jumlah node dibawah A) di sisi kanan adalah 2 sedangkan sisi kirinya tidak memiliki child alias 0, sehingga jika dihitung selisihnya adalah 2. Begitu pula di node B memiliki selisih 1 karena sisi kanan kedalamannya 1 dan sisi kirinya 0, sedangkan node C selisihnya 0 karena sisi kiri dan kanannya tidak ada node.

Berdasarkan aturan AVL, jika ada node yang memiliki selisih kedalaman lebih dari 1, maka akan melanggar aturan AVL. Untuk mengatasi masalah tersebut maka akan dilakukan proses penyeimbangan pohon dengan 2 metode, yaitu yang disebut Single Rotation dan Double Rotation.

Sebelum mengetahui kedua metode tersebut, kita harus tahu kondisi kondisi apa saja yang perlu diperhatikan saat akan melakukan rotasi :

• Hal pertama yang harus diingat adalah proses penyeimbangan tree akan dilakukan dari bagian terdalam dahulu, jadi apabila ada 2 node atau lebih yang melanggar aturan AVL, node paling dalam akan diselesaikan terlebih dahulu, kemudian jika node atasnya masih mengalami masalah baru akan diselesaikan kemudian (Tetapi pada umumnya jika node terdalam sudah diperbaiki, node node diatasnya yang bermasalah akan terbaiki juga).
• Apabila tree berat sisi di sebelah kanan, proses rotasi yang akan dilakukan adalah menarik tree ke sisi kiri dan begitu juga sebaliknya.
• Jika ada node yang bermasalah, ada 2 jenis kasus yang perlu diperhatikan, kasus pertama adalah jika 2 link pertama dari node yang terlanggar ke node pelanggarnya lurus (kiri dan kiri atau kanan dan kanan) yang dimana proses rotasi akan dilakukan dengan cara Single Rotation. Kasus kedua adalah jika 2 link pertama dari node yang terlanggar ke node pelanggarnya bengkok (kiri dan kanan atau kanan dan kiri) yang dimana perlu menggunakan metode Double Rotation untuk menyeimbangkan tree.
• Jika ada 2 node yang menjadi penyebab masalah ketidakseimbangan tree dan kedua metode dapat digunakan (Single dan Double Rotation) maka umumnya dipilih Single Rotation.

Single Rotation :

Sesuai namanya, metode ini akan menyeimbangkan tree dengan seolah-olah melakukan rotasi (perpindahan posisi node) sebanyak satu kali. Berikut adalah contohnya :

Kasus Single Rotation pada saat Deletion

Pada ilustrasi tersebut dapat dilihat bahwa setelah dilakukan deletion pada node 56 maka tree menjadi tidak seimbang (Berat di kiri karena kedalaman kiri node 50 adalah 3 sedangkan sisi kanannya kedalaman 1 sehingga selisihnya 2).

Hal yang menjadi penyebab Tree tidak seimbang adalah node 10, jika kita lihat traversal 2 garis pertama dari node 50 ke node 10 adalah lurus (kiri terus kiri) sehingga dapat dilakukan single rotation untuk menyeimbangkan tree.

Hal yang terjadi adalah kita anggap 50 (atau node yang melanggar) sebagai pivot yang akan menarik node dibawahnya ke atas, dalam hal ini akan dilakukan tarikan ke arah kanan. Seolah-olah node 50 menarik node 40 ke posisi node 50 dan kemudian node 50 akan turun ke kanan sehingga terlihat node 50 menjadi child sebelah kanannya node 40. Semua node bagian kiri dari node 40 juga akan ikut terangkat keatas, kemudian jika awalnya node 40 memiliki child dibagian kanan akan secara otomatis child tersebut akan menjadi bagian kiri dari node 50 (hanya node teratas saja, jika ada child lagi dibawahnya maka akan tetap normal).

Setelah dilakukan metode penyeimbang tersebut maka Tree akan kembali menjadi AVL Tree.

Double Rotation :

Metode ini sama seperti Single Rotation, bedanya adalah rotasi dilakukan 2 kali. Jika 2 garis utamanya kiri kemudian ke kanan maka akan dilakukan rotasi ke kiri dengan node pertama dibawahnya node yang melanggar sebagai pivot kemudian rotasi ke kanan dengan node yang bermasalah sebagai pivotnya. Untuk 2 garis pertama kanan kemudian kiri dilakukan sebaliknya (rotasi kanan kemudian rotasi ke kiri). Ilustrasinya sebagai berikut :

Double Rotation Kanan Kiri

Ilustrasi diatas menggambarkan Double Rotation Kanan-Kiri, hal tersebut ditandai karena pada node E terjadi pelanggaran karena sisi kiri kedalamannya 1 (sampai W) dan sisi kanannya kedalaman 3 (sampai node X dan Y) sehingga berat sebelah di kanan. Kemudian jika dilihat traversal 2 node pertama dari node E ke node X atau Y adalah kanan kemudian kiri (bengkok) sehingga diperlukan metode Double Rotation.

Karena node E yang bermasalah, akan dilakukan rotasi ke kanan dari node pertama dibawahnya, yaitu node G. Node G menarik node F ke posisi node G dan G mejadi child kanan F, sedangkan child kanan F sebelumnya (node Y) menjadi child kiri node G. Rotasi pertama selesai.

Rotasi kedua dilakukan di node yang bermasalah (node E), karena berat ke kanan maka dilakukan rotasi ke kiri. Node  E sebagai pivot menarik node F ke atas dan node E sekarang menjadi child kiri node F. Karena dilakukan rotasi kiri, maka child kiri F sebelumnya (node X) menjadi child kanan node E. Semua child kanan F pun seolah-olah ikut naik keatas sehingga pada akhirnya membentuk BST yang seimbang (dalam kasus ini perfect binary tree) dan fungsional seperti BST pada biasanya.

Sekian penjelasan mengenai konsep dasar dari AVL Tree. Semoga membantu :)

Rangkuman Linked List dan BST

Review Materi Linked List dan BST

Linked list adalah sebuah struktur data yang terdiri atas urutan data-data yang di tiap datanya memiliki referensi untuk data berikutnya atau sebelumnya dalam suatu urutan data.

Ilustrasi Linked List

Linked list pada umumnya digunakan untuk menampung data-data, sehingga memiliki fungsi yang mirip dengan Array. Namun, antara kedua hal tersebut terdapat hal-hal yang menjadi pembeda, yaitu :

• Pada array, ukuran array sudah ditentukan saat dideklarasikan sehingga menggunakan memori yang tetap dan tidak bisa berubah ukurannya. Sedangkan pada linked list, memori yang digunakan tergantung jumlah data yang dimasukkan. Memori akan terpakai atau tersedia hanya saat penambahan atau pengurangan data. Sehingga linked list lebih dinamis.
• Pada array, data disimpan di lokasi memori yang berurutan satu dengan yang lain. Sedangkan pada linked list lokasi penyimpanan data tidak secara berurutan.
• Pada array, bisa dilakukan pengaksesan data secara acak karena kita dapat mengakses secara langsung dengan memasukkan index yang diinginkan. Sedangkan pada linked list tidak dapat dilakukan pengaksesan data secara acak karena mengikuti urutan sequence (looping).

Linked list biasanya digunakan untuk memecahkan masalah secara real-time karena cirinya yang mengalokasikan memori seiring program berjalan, hal ini penting agar program yang dijalankan tidak mengalami kendala performa akibat memori penuh yang disebabkan data tidak terpakai. Linked list menggunakan tipe data pointer untuk referensi antar datanya. Posisi dalam suatu linked list ditandai dengan adanya posisi head yang merujuk pada posisi data paling awal dan tail yang merujuk pada posisi data paling akhir.

Linked list terdiri atas 2 metode, yaitu Insert/Push yang merupakan penambahan rekor data/node dan Delete/Pop yang merupakan penghapusan rekor data/node dalam suatu linked list.

Ada 2 jenis linked list yaitu :

Single Linked List

Single Linked List adalah jenis linked list yang memiliki hubungan satu arah sebagai referensi antar datanya. Hubungan antar data direpresentasikan dengan adanya pointer next yang menunjuk data di posisi berikutnya.

Diagram Single Linked List

Circular Single Linked List adalah single linked list yang dimana node terakhirnya menunjuk ke node paling awal (head) sehingga tidak ada node yang merujuk ke NULL, seolah-olah looping.

Circular Single Linked List

Double Linked List

Double Linked List pada dasarnya sama dengan single linked list, hal yang membedakannya adalah adanya hubungan dua arah antar datanya yaitu next dan prev. Next merujuk pada data sesudah dan prev merujuk pada data sebelumnya.

Double Linked List

Circular Double Linked List adalah double linked list yang membentuk suatu sirkuit (tertutup) sehingga tidak ada data yang menuju NULL baik untuk prev maupun nextnya. Karena ada dua arah hubungan, maka ada dua sirkuit yang terbentuk. Pertama adalah next dari data terakhir yang menuju ke data pertama (head) dan yang kedua adalah prev dari data pertama yang menuju ke data terakhir (tail).

Circular Double Linked List

Stack

Stack adalah jenis struktur data yang menyimpan elemennya dalam urutan tertentu.
Stack menggunakan analogi tumpukan, yang berarti data yang terakhir kali masuk diakses terlebih dahulu dibanding data yang pertama kali masuk. Data tersimpan dalam metode Last In First Out (LIFO).
Stack sendiri dapat direpresentasikan dalam array atau suatu linked list.

Dalam bentuk array, hanya diperlukan dua variabel sebagai penanda yaitu, Top yang berfungsi menyimpan alamat data teratas dan Max yang berfungsi sebagai ukuran array. Jika Top NULL maka stack kosong, sedangkan jika Top adalah Max-1 maka stack penuh.

Dalam bentuk linked list, hampir sama konsepnya seperti linked list biasa, yaitu tiap node memiliki data dan alamat node berikutnya. Pointer awal dari linked list dijadikan Top. Semua proses insertion dan deletion dilakukan di node Top ini. Jika Top NULL artinya stacknya kosong.

Queue

Jenis struktur data yang bergantung dari urutan input data. Queue sendiri menggunakan analogi antrian, yaitu istilah First In First Out (FIFO). Sehingga pada queue data yang dimasukkan pertama kali akan dikeluarkan atau diakses terlebih dahulu.

Seperti Stack, Queue dapat direpresentasikan dalam bentuk array maupun Linked list. Secara konsep queue memiliki dasar yang sama dengan stack, hanya saja menggunakan konsep FIFO.

Prefix, Infix, Postfix

Prefix adalah notasi matematika dimana operator ditulis terlebih dahulu sebelum operand.
Contoh : * 5 7 (memiliki arti yang sama dengan (5*7))

Infix adalah notasi matematika dimana operator ditulis diantara operand.
Contoh : 5 * 7 (penulisan pada umumnya)

Postfix adalah notasi matematika dimana operator ditulis setelah operand ditulis.
Contoh : 5 7 * (memiliki arti yang sama dengan (5*7))

Alasan adanya prefix dan postfix adalah karena keduanya tidak memerlukan () sehingga lebih mudah untuk diproses komputer.
:
Proses penghitungan dengan notasi Prefix dan Postfix dapat dilakukan dengan menggunakan metode Stack.
Secara dasar metode yang digunakan ada 2 yaitu :

• Jika yang diterima adalah operand, maka akan dilakukan metode push().
• Jika yang diterima adalah operator, maka akan dilakukan pop sebanyak 2 kali yang dimana tiap elemennya disimpan ke sebuah variabel A dan B, kemudian dilakukan push(B operator A).

Dengan kedua metode diatas proses perhitungan akan lebih cepat diproses karena iterasinya lebih sedikit.

Hashing

Hashing adalah teknik yang digunakan untuk menyimpan dan mengambil keys dengan cepat.
Dalam hashing, sebuah string dirubah menjadi value yang lebih kecil atau key yang merepresentasikan string awalnya.
Metode Hashing digunakan untuk mengambil data dalam sebuah database karena lebih cepat untuk mengakses data menggunakan key daripada string originalnya.
Hashing sendiri dapat didefinisikan sebagai konsep mendistribusi key dalam sebuah array yang diberi nama Hash Table menggunakan fungsi yang disebut Hash Function.


Hash Table

Merupakan array untuk menyimpan string original. Index tabel merupakan hashed key, sedangkan isi index adalah string originalnya.
Ukuran hash table biasanya beberapa urutan lebih sedikit dibandingkan dari jumlah total string yang memungkinkan, jadi beberapa string bisa memiliki key yang sama.

Hash Function

Ada beberapa cara untuk meng-hash string menjadi key. Berikut adalah beberapa metode penting untuk membuat hash functions.

• Mid-Square

Metode ini dilakukan dengan cara mengkuadratkan string (dirubah menjadi integer terlebih dahulu) kemudian menggunakan beberapa bit dari tengah hasil kuadrat untuk mendapatkan hash keynya.

Contoh :

• Division / Pembagian

Penentuan hash key dilakukan dengan membagi string menggunakan operator modulus (biasanya dibagi dengan size tablenya)

Contoh : Misalkan Modulus = 12

hash key dari angka 30 adalah 6 (30 % 12 = 6)

hash key dari angka 40 adalah 4 (40 % 12 = 4)

• Folding / Lipatan

Metode yang memecah-mecah string menjadi beberapa bagian, kemudian menjumlahkan bagian-bagiannya untuk mendapatkan hash key

Contoh :

Jika suatu hash table hanya memiliki 100 lokasi penyimpanan, maka data hanya bisa disimpan pada lokasi yang memiliki 2 digit saja, oleh sebab itu string/data dipecah menjadi 2 digit

untuk key 5786 akan dipecah menjadi 57 + 86 yang menghasilkan 143, karena hanya dipakai 2 digit maka yang terpakai adalah 43.

untuk ke 12345 akan dipecah menjadi 12 + 34 + 5 yang menghasilkan 51, maka lokasinya menjadi 51,

• Digit Extraction

Penentuan lokasi hash dilakukan dengan cara menentukan digit-digit yang akan dijadikan sebagai alamat hash

Contoh :

Jika key = 235146

Digit yang akan diekstrak adalah digit ke 1, 4, 5, dan 6. Maka alamat hash key diatas adalah 2146.

• Rotating Hash

Gunakan metode fungsi hash manapun yang sudah diterangkan diatas, kemudian hasil hash address tersebut akan dilakukan rotasi.

Rotasi dilakukan dengan menggeser digit-digit untuk mendapatkan alamat hash baru

Contoh :

Hasil hash address = 20021

Hasil rotasi = 12002

Collision

Collision adalah hal yang terjadi ketika ada beberapa data yang memiliki hash key yang sama.

Untuk menyelesaikan masalah tersebut, ada 2 metode yang dapat dilakukan :

1. Linear Probing

Mencari slot array yang kosong untuk menempatkan string (Metode ini tidak disarankan untuk digunakan, lebih baik menggunakan metode chaining)

Contoh :

2. Chaining

Meletakkan string didalam slot yang sama menggunakan linked list. Dengan melakukan cara ini maka tidak perlu takut tidak memiliki array yang cukup untuk menyimpan data karena penyimpanan data secara dinamis (linked list).

Contoh :

Binary Tree

Binary Tree adalah struktur data yang menyerupai tree dimana tiap nodenya memiliki paling banyak dua children, yaitu left dan right. Node yang tidak memiliki children disebut leaf.

Jenis-jenis binary tree :

- Perfect Binary Tree : binary tree yang setiap tingkatnya memiliki kedalaman yang sama.

- Complete Binary Tree : binary tree yang pada tiap tingkatnya, kecuali yang paling terakhir terisi semua, semua nodenya terposisi paling kiri  sebisanya. Perfect Binary Tree termasuk Complete Binary Tree.

- Skewed Binary Tree : binary tree yang tiap nodenya memiliki paling banyak 1 child. Secara tidak langsung, skewed tree akan membentuk relasi linked list biasa.

Penggunaan Binary Tree :

- Melakukan penghitungan operasi prefix dan postfix

- Melakukan searching dengan menggunakan BST (Binary Search Tree)


Binary Search Tree

Binary Search Tree

Binary Search Tree adalah salah satu jenis struktur data yang memungkinkan pencarian secara cepat, melakukan sorting, serta kemudahan untuk memasukkan dan menghapus data.

Pada dasarnya Binary Search Tree adalah Binary Tree yang sudah disorting demi memudahkan pencarian data.

Konsep pada Binary Search Tree memiliki kemiripan dengan konsep Linked List, yaitu menggunakan pointer untuk menunjuk data tertentu. Jika pada Linked List terdapat head dan tail, pada BST menggunakan istilah root yang menunjuk kepada node yang paling awal dimasukkan/sebagai penentu awal. Untuk melakukan pencarian jika pada Linked List menggunakan next dan prev, namun pada BST menggunakan istilah left dan right. Left merujuk pada lokasi node yang nilainya lebih kecil dari posisi node yang dicek saat itu, sedangkan right merujuk ke lokasi node yang nilainya lebih besar. Hal yang perlu diperhatikan adalah tiap nilai dari node dalam BST tidak sama.

Operasi Pada Binary Search Tree

Pada dasarnya BST memiliki 3 metode dasar yaitu :

• Search

Metode search merupakan salah satu alasan mengapa pada BST dilakukan secara berurutan(sorting). Dengan dilakukan secara sorting besar dan kecil maka proses pencarian dapat dilakukan secara efisien dibandingkan melakukan iterasi satu per satu untuk mencari sebuah data.

Cara kerja metode search ;

1. Masukkan data yang ingin kita cari
2. Pencarian akan dilakukan dari data teratas yang akan kita jadikan sebagai root
3. Jika nilai data lebih kecil dari root maka root akan menjadi root->left dan jika lebih besar maka root akan menjadi root-> right
4. Proses pencarian dilakukan sampai data ditemukan dan akan return root agar didapatkan datanya, jika tidak ditemukan bisa di return NULL.

Code :

Contoh searching nama

• Insert

Insert adalah metode untuk memasukkan data ke dalam BST. Proses insertion di BST memperhatikan nilai dari data karena akan dipertimbangkan agar data tersorting dengan benar.

Cara kerja metode insert :

1. Akan dilakukan pengecekan terlebih dahulu apakah di posisi root NULL atau tidak
2. Jika iya maka dilakukan metode Insert
3. Jika tidak akan dicek apakah nilainya lebih besar atau kecil dari root
4. Hal tersebut dilakukan sampai ditemukan posisi root yang kosong
5. Jika ketemu posisi kosong akan dilakukan langkah ke 2

Code :

Contoh insert untuk nama

• Delete

Metode delete digunakan untuk menghapus node dalam BST.

Dalam metode delete harus dipertimbangkan node mana yang akan dihapus.

Ada 3 skenario yang perlu diperhatikan :

1. Jika node yang akan dihapus tidak memiliki child maka hapus node tersebut.
2. Jika node memiliki 1 child maka hapus node tersebut kemudian sambungkan child tersebut dengan parent dari node yang dihapus.
3. Jika node memiliki 2 child maka carilah child terkanan dari subtree kiri node, kemudian rubahlah isi dari node dengan node child terkanan tersebut kemudian hapus node child terkanan tersebut (jika ada childnya maka sambungkan dengan skenario ke 2 secara rekursif).

Code :

Contoh Delete Nama

Selain 3 metode utama diatas, ada 1 lagi metode yang bisa digunakan pada BST yaitu metode Display untuk melihat isi dari BST tersebut.

Ada 3 cara yang biasa dipakai untuk display yaitu :

• In Order : Cara display seperti ini digunakan  untuk menampilkan data secara urut (sorting)

Code :

void inOrder(Data *root){

if(root != NULL){

inOrder(root->left);

printf("%d\n",root->num);

inOrder(root->right);

}

}

• Pre Order : Cara display dengan menampilkan urutan data dari paling atas (tetap dari kiri ke kanan)

Code :

void preOrder(Data *root){

if(root != NULL){

                printf("%d\n",root->num);

preOrder(root->left);

preOrder(root->right);

}

}

• Post Order : Cara display mirip dengan in order namun yang di display bagian kanan dari subtree kiri terlebih dahulu (jika kiri sudah mentok, bergerak ke kanan sampai mentok baru diprint hasilnya)

Code :

void postOrder(Data *root){

if(root != NULL){

postOrder(root->left);

postOrder(root->right); 

                printf("%d\n",root->num);

}

}


Sekian untuk materi review mengenai Linked List sampai BST ini. Semoga membantu :)