AVL tree and B tree

AVL tree

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.

   agar  tree tetap seimbang, setelah meletakkan sebuah node,kita harus  melakukan pemeriksaan dari node baru → root. Node pertama yang memiliki |balance factor| > 1 diseimbangkan. Proses penyeimbangan dilakukan dengan 2 cara yaitu Single rotation dan Double rotation

Single rotation

Single rotation dilakukan apabila searah, left-left atau right-right

               contoh:

           Double rotation

          Double rotation  dilakukan apabila searah, left-right atau right-left.

           AVL Tree Deletion

        Operasi penghapusan node sama seperti pada Binary Search Tree, yaitu node yang dihapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan. Jika yang dihapus adalah leaf, maka langsung hapus saja. Namun jika node yang dihapus memiliki child maka childnya yang menggantikannya. Namun setelah operasi penghapusan dilakukan, cek kembali apakah tree sudah seimbang atau belum, jika belum maka harus diseimbangkan kembali. Cara menyeimbangkannya pun sama seperti insertion.

        B Tree

            Pada B-Tree dikenal istilah order. Order menentukan jumlah maksimum/minimum anak yang dimiliki oleh setiap node, sehingga order merupakan hal yang cukup penting dalam B-Tree. 2-3 Tree pada postingan sebelumnya yaitu Balanced Binary Search Tree (AVL and RBT) and 2-3 Tree merupakan salah satu B-Tree berorder 3. Itu sebabnya setiap nodenya memiliki batasan anak, dengan minimal 2 anak dan maksimal 3 anak.

Aturan pada B-Tree : m = order

• Setiap node (kecuali leaf) memiliki anak paling banyak sejumlah m anak
• Setiap node (kecuali root) memiliki anak paling sedikit m/2 anak
• Root memiliki anak minimal 2, selama root bukan leaf
• Jika node non leaf memiliki k anak, maka jumlah data yang tersimpan dalam node k-1
• Data yang tersimpan pada node harus terurut secara inorder
• Semua leaf berada pada level yang sama, level terbawah

        Insertion

Aturan Insertion :

• Anggap data yang mau di insert adalah key
• Posisikan key pada node yang sesuai, seperti pada BST dan 2-3 Tree, anggap node tersebut A
• Jika A adalah node dengan jumlah data kurang dari m-1, maka langsung masukan saja
• Jika A adalah node dengan jumlah data m-1, maka masukan nilai tengah kemudian masukan ke parentnya. Kemudian anggaplah parent tersebut A. Kemudian periksa kembali sesuai aturan point ke 3 dan 4.

       Deletion
Aturan Deletion :

• Anggap node yang mau di delete adalah key

• Delete dilakukan pada leaf. Meskipun pada saat menghapus node parent, kita tetap menganggapnya menghapus leaf, karena ketika parent dihapus lalu digantikan oleh anak terbesar subtree kiri atau anak terkecil subtree kanan sama saja kita seolah-olah menghapus anak yang menggantikannya. dimana anak tersebut selalu berada pada posisi leaf. maka leaf tersebut dianggap P.

• Jika ukuran P > m/2 maka langsung delete saja data yang ingin dihapus

• Jika ukuran P = m/2 maka : perhatikan siblingnya (anggap sibling adalah Q)

• Q > m/2, maka rotasi pada P

• Q = m/2, satukan P dan Q

Review Data Struct

Struktur data adalah cara penyimpanan, penyusunan dan pengaturan data di dalam media penyimpanan komputer sehingga data tersebut dapat digunakan secara efisien.


Dalam teknik pemrograman, struktur data berarti tata letak data yang berisi kolom-kolom data, baik itu kolom yang tampak oleh pengguna (user) ataupun kolom yang hanya digunakan untuk keperluan pemrograman yang tidak tampak oleh pengguna. Setiap baris dari kumpulan kolom-kolom tersebut dinamakan catatan (record). Lebar kolom untuk data dapat berubah dan bervariasi. Ada kolom yang lebarnya berubah secara dinamis sesuai masukan dari pengguna, dan juga ada kolom yang lebarnya tetap. Dengan sifatnya ini, sebuah struktur data dapat diterapkan untuk pengolahan database (misalnya untuk keperluan data keuangan) atau untuk pengolah kata (word processor) yang kolomnya berubah secara dinamis. Contoh struktur data dapat dilihat pada berkas-berkas lembar-sebar (spreadsheet), pangkal-data (database), pengolahan kata, citra yang dipampat (dikompres), juga pemampatan berkas dengan teknik tertentu yang memanfaatkan struktur data.


Array


Array dalam bahasa C selalu dimulai dari indeks 0. Larik dapat didefinisikan secara statik atau dinamik. Jika didefinisikan statik, ukuran larik akan tetap dari awal program hingga akhir program. Jika didefinisikan dinamik, ukuran larik dapat berubah selama program berjalan karena memesan tempat pada memori heap. Proses pemesanan tempat pada memori disebut dengan alokasi. Sedangkan proses pembebasan memori yang sudah dipesan disebut dengan dealokasi.


Contoh array statik:


#include <stdio.h>
int main(){
int arr[10] // indeks awal 0 dan indeks akhir 9
arr [0] = 5;
printf("%d",arr[0]);
}


Contoh array dinamik:

#include <malloc.h>
int main(){
int * arr;
arr = (int *) malloc(10 * sizeof(int)); //memesan 10 tempat pada memori
arr[0] = 5;
free(arr); //menghapus array.
Memori pada heap dibebaskan arr = (int *) malloc(5 * sizeof(int)); //memesan 5 tempat baru pada memori free(arr); //di akhir program jangan lupa untuk menghapus array dinamik
}

Linked list


sebuah struktur data yang digunakan untuk menyimpan sejumlah objek data biasanya secara terurut sehingga memungkinkan penambahan, pengurangan, dan pencarian atas elemen data yang tersimpan dalam senarai dilakukan secara lebih efektif. Pada praktiknya sebuah struktur data memiliki elemen yang digunakan untuk saling menyimpan rujukan antara satu dengan lainnya sehingga membentuk sebuah senarai abstrak, tiap-tiap elemen yang terdapat pada senarai abstrak ini sering kali disebut sebagai node. karena mekanisme rujukan yang saling terkait inilah disebut sebagai senarai berantai.


jenis- jenis linked list:


1. single linked list


Terjadi bila struktur data sebuah node hanya memiliki satu tautan atas node berikutnya dalam sebuah link, maka senarai tersebut dinamakan sebagaisingle linked list.


2.double linked list


Terjadi bila struktur data atas tiap-tiap node memiliki rujukan pada node sebelum dan berikutnya. Sebagian algoritme membutuhkan taut ganda, contohnya sorting dan reverse traversing.


3. circular linked list


terjadi bila nformasi rujukan pada node terakhir akan merujuk pada node pertama, dan rujukan pada node pertama akan merujuk pada node terakhir bila yang digunakan sebagai dasar implementasi adalah double linked list.


Hash Table


Hash Table adalah 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.


Keunggulan dari struktur hash table ini adalah waktu aksesnya yang cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya. Akan tetapi pada kenyataannya sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (bertabrakan).


Pemetaan hash function yang digunakan bukanlah pemetaan satusatu, (antara dua record yang tidak sama dapat dibangkitkan angka hash yang sama) maka dapat terjadi bentrokan (collision) dalam penempatan suatu data record. Untuk mengatasi hal ini, maka perlu diterapkan kebijakan resolusi bentrokan (collision resolution policy) untuk menentukan lokasi record dalam tabel. Umumnya kebijakan resolusi bentrokan adalah dengan mencari lokasi tabel yang masih kosong pada lokasi setelah lokasi yang berbentrokan.


Operasi Pada Hash Tabel
Ø insert: diberikan sebuah key dan nilai, insert nilai dalam tabel
Ø find: diberikan sebuah key, temukan nilai yang berhubungan dengan key
Ø remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut
Ø getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu


Binary Search Tree (BST)

Binary Search Tree (BST) merupakan tree yang terurut (ordered Binary Tree) yang memiliki kelebihan bila dibanding dengan struktur data lain. Diantaranya adalah proses pengurutan (sorting) dan pencarian (searching) dapat dilakukan bila data sudah tersusun dalam struktur data BST. Pengurutan dapat dilakukan bila BST ditelusuri (traversed) menggunakan metode in-order.


contoh:

struct node* search(struct node* root, intkey)
{
// Base Cases: root is null or key is present at root
if (root == NULL || root->key == key) 

return root;
// Key is greater than root's key 

if (root->key < key) 

return search(root->right, key);
// Key is smaller than root's key
return search(root->left, key);
};

Hash Table

Hashing table Hash Table is a data structure which stores data in an associative manner. In a hash table, data is stored in an array format, where each data value has its own unique index value. Access of data becomes very fast if we know the index of the desired data.

Hashing table in research of blockchain In the bitcoin protocol, hash functions are part of the block hashing algorithm which is used to write new transactions into the blockchain through the mining process. In bitcoin mining, the inputs for the function are all of the most recent, not-yet-confirmed transactions (along with some additional inputs relating to the timestamp and a reference to the previous block).

Hashing table example:
#include<stdio.h>
#include <string.h>
#include <stdlib.h>
#define CAPACITY 50000
unsigned long hash_function(char* str) { unsigned long i = 0; for (int j=0; str[j]; j++) i += str[j]; return i % CAPACITY; }
typedef struct Ht_item Ht_item;
struct Ht_item { char* key; char* value; }; typedef struct HashTable HashTable; struct HashTable {Ht_item** items; int size; int count; };
Ht_item* create_item(char* key, char* value) { Ht_item* item = (Ht_item*) malloc (sizeof(Ht_item)); item->key = (char*) malloc (strlen(key) + 1); item->value = (char*) malloc (strlen(value) + 1);

strcpy(item->key, key);
strcpy(item->value, value);
return item; }
HashTable* create_table(int size) { HashTable* table = (HashTable*) malloc (sizeof(HashTable));
table->size = size;
table->count = 0;
table->items = (Ht_item**) calloc (table->size, sizeof(Ht_item*));
for (int i=0; isize; i++) table->items[i] = NULL; return table; }
void free_item(Ht_item* item) { free(item->key); free(item->value); free(item); }
void free_table(HashTable* table) { for (int i=0; isize; i++) { Ht_item* item = table->items[i]; if (item != NULL) free_item(item); }
free(table->items);
free(table); } void handle_collision(HashTable* table, unsigned long index, Ht_item* item) { } void ht_insert(HashTable* table, char* key, char* value) { Ht_item* item = create_item(key, value); unsigned long index = hash_function(key); Ht_item* current_item = table->items[index]; if (current_item == NULL) {
if (table->count == table->size) { printf("Insert Error: Hash Table is full\n"); free_item(item);
return; }
table->items[index] = item;
table->count++; }
else { if (strcmp(current_item->key, key) == 0) { strcpy(table->items[index]->value, value); return; }
else { handle_collision(table, index, item); return; } } }
char* ht_search(HashTable* table, char* key) { int index = hash_function(key); Ht_item* item = table->items[index];
if (item != NULL) { if (strcmp(item->key, key) == 0) return item->value; } return NULL; }
void print_search(HashTable* table, char* key) { char* val; if ((val = ht_search(table, key)) == NULL) { printf("Key:%s does not exist\n", key); return; }
else { printf("Key:%s, Value:%s\n", key, val); } }
void print_table(HashTable* table) { printf("\nHash Table\n-------------------\n"); for (int i=0; isize; i++) { if (table->items[i]) { printf("Index:%d, Key:%s, Value:%s\n", i, table->items[i]->key, table->items[i]->value); } } printf("-------------------\n\n"); }
int main() {
HashTable* ht = create_table(CAPACITY); ht_insert(ht, "1", "First address");
ht_insert(ht, "2", "Second address");
print_search(ht, "1"); print_search(ht, "2");
print_search(ht, "3");
print_table(ht);
free_table(ht);
return 0; }

Data structures Struktur data adalah organisasi data, manajemen, dan format penyimpanan yang memungkinkan akses dan modifikasi yang efisien. Linked list Link list dapat dibagi menjadi 4 yaitu: -Single Linked List -Double Linked List -Circular Linked List -Multiple Linked List Single linked list: Single Linked List merupakan suatu linked list yang hanya memiliki satu variabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya. Biasanya field pada tail menunjuk ke NULL.