DATA STRUCTURE - AVL TREE

 AVL TREE

AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan.AVL

AVL Tree digunakan untuk   menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.

Untuk menjaga tree tetap imbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru → root. Node pertama yang memiliki |balance factor| > 1 diseimbangkan.


1. OPERASI INSERT : 
Ada 4 kemungkinan kasus yang terjadi saat melakukan operasi Insert yaitu :
*Misalkan T adalah node yang harus diseimbangkan kembali
– Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)
– Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)
– Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)
– Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)

Ke-4 kasus tersebut dapat diselesaikan dengan melakukan rotasi.
Rotasi ada 2 cara yaitu dilakukan dengan: Single rotation dan Double rotation
– Kasus 1 dan 2 dengan single rotation
– Kasus 3 dan 4 dengan double rotation

Contoh penggunaan :
1. SINGLE ROTATION
  Jika suatu Tree diinsert node baru dengan nilai 12, maka akan terjadi ketidak seimbangan dan hal ini terletak pada posisi root.

2. DOUBLE ROTATION
 Jika terdapat sebuah tree yang kemudian dilakukan insert node 26. Maka akan terjadi ketidak seimbangan, sehingga terlihat dari bentuknya dapat diselesaikan dengan kasus 4.

2. OPERASI DELETE :
 Terdapat 2 kasus yang biasanya terjadi saat operasi delete dilakukan, yaitu :
1. Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus.
2. Jika node yang akan dihapus memiliki anak, maka proses penghapusannya harus di cek kembali untuk menyeimbangkan Binary Search Tree dengan perbedaan tinggi / level maksimal 1.

Berikut contoh dalam menghapus node AVL Tree, terdapat AVL Tree yang kemudian di hapus node 60. Dengan gambaran sebagai berikut :

Yang akan menggantikan posisi node 60 adalah node 55. Akan terjadi ketidak seimbangan. Dengan tampilan sebagai berikut :

Maka akan dilakukan single rotation pada node 55 dengan kasus ketidak seimbangan pada kasus no. 2. Dengan tampilan setelah dilakukan single rotation sebagai berikut :

Ketika sudah dilakukan single rotation dan dilakukan kembali perbedaan tinggi / level maksimal 1 ternyata terdapat ketidak seimbangan yang terjadi. Sehingga diperlukan double rotation dengan kasus no. 4. Sehingga hasil dari rotasi yang dilakukan adalah sebagai berikut :




Referensi :
http://dinda-dinho.blogspot.com/2013/06/pengertian-dan-konsep-avl-tree.html
https://www.geeksforgeeks.org/avl-tree-set-1-insertion/
https://socs.binus.ac.id/2017/05/15/deletion-avl-tree/

Hashing dan Hash Tables, Trees dan Binary Tree

HASH TABLE DAN BINARY

HASH TABLE

Sebuah tabel(array) dimana untuk menyimpan dan memetakan nilai kunci yang unik untuk setiap record(baris) menjadi angka(hash) lokasi record tersebut dalam sebuah tabel.

Banyak cara untuk hash sebuah string ke sebuah kunci. Beberapa metode penting untuk membentuk fungsi hash :

1. Mid-square

2. Division (most common)

3. Folding

4. Digit Extraction

5. Rotating Hash

•  Mid Square :

Teknik hashing dimana kunci unik dihasilkan. alam teknik ini, nilai benih diambil dan dikuadratkan. Kemudian, beberapa digit dari tengah diekstraksi. Angka-angka yang diekstrak ini membentuk angka yang diambil sebagai benih baru. 

Rumusnya  : h(k) = s

k = key

s =  hash key yang diperoleh dengan memilih  r bits dari k2

•  Division  :

 Jumlah lokasi memori yang tersedia dihitung, kemudian jumlah tersebut digunakan sebagai pembagi untuk membagi nilai yang asli dan menghasilkan sisa(modulus). Sisa tersebut adalah nilai hashnya.

Rumusnya: h(z) = z mod M

z  = key

M = nilai untuk membagi kunci. biasanya menggunakan bilangan prima, ukuran tabel atau ukuran memori yang digunakan

•  Folding : 

Membagi-bagi string / identifier menjadi beberapa bagian, lalu menambahkan bagian tersebut dan mengambil beberapa angka terakhir sebagai nilai hashnya. 

• Digit Extraction  :

Digit yang ditentukan sebelumnya dari nomor yang diberikan dianggap sebagai alamat hash.
Metode ini mengubah urutan digit dengan pola tertentu. Contohnya mengambil digit ke tiga sampai ke enam dari nilai aslinya, kemudian membalikan urutannya dan menggunakan digit yang terurut terbalik itu sebagai nilai hash. 

•   Rotating Hash : 

 metode ini menggunakan berbagai macam metode seperti metode division atau mid-square. lalu terjadi rotasi setelah mendapatkan kode atau alamat hash melalui metode hash.

Rotasi dilakukan dengan menggeser digit untuk mendapatkan alamat hash baru.contoh :

diberikan alamat hash 20021 maka hasil rotasi adalah 12002.

TREE & Binary Tree

Tree 

Struktur data non-linear yang mewakili hubungan hierarkis di antara objek data.

Tree adalah kumpulan dari satu atau lebih node.

Simpul yang berisi informasi yang nilainya lebih besar dari simpul atas atau yang disebut root akan ditempatkan sebagai cabang kanan, jika lebih kecil dari simpul atas akan ditempatkan seagai cabang kiri.

Tree terdiri dari akar atau root atau induk, yang berisi himpunan node dan garis berarah yang disebut branch yang menghubungkan dua node.

• Root

Jika suatu tree tidak kosong maka node yang pertama dan merupakan sebuah node unik disebut root.

• Leave atau daun

Merupakan node yang nilai outdegreenya 0, yaitu node yang tidak memiliki successor (sebuah node yang terjadi pada beberapa node).

Node terdiri dari dua yaitu:

-Node internal merupakan node yang bukan root atau leave

-Node eksternal.

• Parent / induk

Tree  disebut parent jika outdegreenya lebih dari 0.

• Child / anak 

Child merupakan bagian akhir dari tree.

• Ada 3 urutan dasar yang dapat digunakan untuk mengunjungi tiap tree(pohon), yaitu :

1. Pre-order : cetak isi node yang dikunjungi, kunjungi LEFT Child, kunjungi RIGHT Child.

2. In-order : kunjungi LEFT Child, cetak isi node yang dikunjungi, kunjungi RIGHT Child.

3. Post-order : kunjungi LEFT child, kunjungi RIGHT child, cetak isi node yang dikunjungi

Binary Tree

Pohon yang setiap simpul/nodenya paling banyak mempunyai dua buah sub-pohon. Binary tree dapat diimplementasikan dalam c/c++ dengan menggunakan double linkedlist.

Jenis- jenis Binary tree :

1. Perfect Binary Tree

Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.

 2.Complete Binary Tree

Jenis ini mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda dan setiap node kecuali leaf hanya boleh memiliki 2 child.

 

3. Skewed Binary Tree

Skewed Binary Tree adalah Binary Tree yang semua nodenya (kecuali leaf) hanya

memiliki satu child.

4. Balance Binary Tree

dimana memiliki perbedaan jumlah node pada subtree kiri dan subtree kanannya maksimal 1 (atau dapat dikatakan antara tingginya sama atau selisih satu).

 Expression Tree Concept

• Prefix 

Metode penulisan dengan meletakkan operator di depan operand dan tanpa menuliskan tanda kurung. Contoh pemakaian prefix adalah  +AB, – +ABC, * + AB – CD.

• Infix 

Cara penulisan ungkapan dengan meletakkan operator di antara dua operand dalam hal ini pemakaian tanda kurung sangat menentukan hasil operasi. Contoh pemakaian infix adalah A+B, A+B-C, (A+B)*(C-D).

• Postfix 

Metode penulisan dengan menuliskan operator setelah operand dan tanpa menuliskan tanda kurung. Salah satu contoh proses pengubahan infix menjadi postfix dari karakter:

( A + B ) / (( C – D ) * E ^ F).

 

Referensi : 
https://www.academia.edu/25537608/TABEL_HASH_HASH_TABLE
http://chandra-mahardika.blogspot.com/2015/10/materi-prefix-infix-dan-postfix.html
http://t-edukasi.blogspot.com/2018/01/materi-dan-pengertian-jenis-jenis.html
https://herlinnairine.wordpress.com/2015/05/05/tree-dalam-pengantar-struktur-data/
http://syazdiayhodian.blogspot.com/2011/06/hashing.html