Balanced Binary Search Tree (AVL)

AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi (height) / 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 dari BST dapat dipersingkat dan disederhanakan. 

Sama Seperti BST , AVL Mempunyai 2 Operasi yaitu : Insertion , dan Deletion
Namun Perbedaan nya Saat selesai Menginsert maupun mendelete seperti biasa , harus di Rotate untuk menyeimbangkan Tree nya.
dalam AVL terdapat 2 jenis Rotation yaitu,
Single Rotation -> Rotation Left,dan  Rotation Right.

Double Rotation -> Rotation Left Right , dan Rotation Right Left.



Cara Menentukan Height dan Balance Factor :
Height :
- Jika node/root tidak memiliki subtree heightnya =0
- Jika node adalah leaf , height =1
- Jika internal node,maka height = height tertinggi dari anaknya dan +1

Balance factor :
-> Selisih Height Anak Kiri - Selisih Height Anak Kanan
-> Jika tidak punya anak , maka dianggap 0
Contoh  Lainnya Sebagai Refrensi Tambahan:

B-Tree

Pada B-Tree dikenal istilah Order. Order menentukan Julah maksimum / minimum anak yang dimiliki oleh setiap node. AVL (Balanced Binary Search Tree ) , RBT (Red Black Tree ) dan 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.

B-Tree adalah pohon seimbang yang dioptimalkan untuk situasi saat sebagian atau seluruh pohon harus dipertahankan dalam penyimpanan sekunder seperti disk magnetik.


Aturan :
1. Setiap Node (Kecuali Leaf) memiliki anak paling banyak x anak
2. Setiap Node (kecuali root) memiliki anak paling sedikit x/2 anak
3. Root memiliki anak minimal 2  (Selama root bukan leaf).
4. Jika Node non-leaf memiliki y anak , maka jumlah data yang tersimpan dalan Node y-1.
5. Data yang tersimpan pada Node harus terurut secara inorder.
6. Semua leaf berada pada level(height) yang sama , level(height) terbawah.

Operasi Pada B-Tree Terdapat : Searching , Insertion , dan Deletion

Kegunaan B-Tree :
1. Menjaga data tetap terurut untuk akses sekuensial.
2. Menggunakan indeks hierarki untuk menimalisir akses ke media penyimpanan.
3. Menggunakan blok penuh-parsial untuk mempercepat penambahan dan penghapusan data.
4. Indeks disesuaikan secara elegan menggunakan algoritma rekursif,
5. Meminimalisir proses yang terbuang dengan memastikan semua simpul setidaknya setengah Penuh.


Daftar Pustaka :
http://suciantinovi.blogspot.com/2014/05/balanced-binary-tree-and-2-3-tree.html
https://en.wikipedia.org/wiki/AVL_tree
http://dinda-dinho.blogspot.com/2013/06/pengertian-dan-konsep-avl-tree.html
http://knowing012.blogspot.com/2014/03/implementasi-b-tree.html
http://suciantinovi.blogspot.com/2014/05/b-tree-and-heap-deap.html