AVL & B - Tree

AVL Tree

AVL Tree dinamai setelah penemunya Adelson, Velski & Landis. AVL Tree adalah Binary Search Tree yang balance. Pohon AVL memeriksa ketinggian sub-pohon kiri dan kanan dan memastikan bahwa perbedaannya tidak lebih dari 1. Perbedaan ini disebut balance factor.
BalanceFactor = height(left-sutree) − height(right-sutree).
Jika balance factor bernilai kurang dari -1 atau lebih dari 1, maka pohon tidak balance dan diperlukan rotasi.

4 Macam Rotasi:
1. Left Rotation
Jika sebuah node menjadi tidak seimbang  karena node dimasukkan di subtree kanan, maka dilakukan rotasi kiri.
2. Right Rotation
Jika sebuah node menjadi tidak seimbang  karena node dimasukkan di subtree kiri, maka dilakukan rotasi kanan.
3. Left-Right Rotation
Rotasi kiri-kanan adalah kombinasi dari rotasi kiri diikuti oleh rotasi kanan.
4. Right-Left Rotation
Rotasi kanan-kiri adalah kombinasi dari rotasi kanan diikuti oleh rotasi kiri.

Operasi dalam AVL Tree:
1.Search
In an AVL tree, the search operation is performed with O(log n) time complexity. The search operation in the AVL tree is similar to the search operation in a Binary search tree. 

2.Insertion
In an AVL tree, the insertion operation is performed with O(log n) time complexity. In AVL Tree, a new node is always inserted as a leaf node.


3.Deletion
The deletion operation in AVL Tree is similar to deletion operation in BST. But after every deletion operation, we need to check with the Balance Factor condition. If the tree is balanced after deletion go for next operation otherwise perform suitable rotation to make the tree Balanced.

B-Tree

B-Tree adalah self-balancing search tree. Gagasan utama menggunakan B-Tree adalah untuk mengurangi jumlah akses disk. Sebagian besar operasi pohon (pencarian, masukkan, hapus, maks, min, ..etc) memerlukan O (h) akses disk di mana h adalah ketinggian pohon. B-tree adalah pohon yang gemuk. Ketinggian B-Trees dijaga tetap rendah dengan meletakkan kunci maksimum yang mungkin dalam simpul B-Tree. Karena h rendah untuk B-Tree, akses disk total untuk sebagian besar operasi berkurang secara signifikan dibandingkan dengan Binary Search Tree yang lain seperti AVL,  Tree, Red-Black Tree.

Ciri-ciri B-Tree
1) Semua leaf berada pada level yang sama.
2) B-Tree didefinisikan dengan istilah tingkat minimum ‘t ’. Nilai t tergantung pada ukuran blok disk.
3) Setiap node kecuali root harus mengandung setidaknya kunci t-1. Root mungkin berisi kunci minimal 1.
4) Semua node (termasuk root) dapat berisi maksimal 2t - 1 kunci.
5) Jumlah anak-anak dari sebuah simpul sama dengan jumlah kunci di dalamnya ditambah 1.
6) Semua kunci simpul diurutkan dalam urutan yang meningkat. Anak antara dua tombol k1 dan k2 berisi semua kunci dalam kisaran dari k1 dan k2.
7) B-Tree tumbuh dan menyusut dari akar yang tidak seperti Binary Search Tree. Binary Search Trees tumbuh ke bawah dan juga menyusut dari bawah.

8) Seperti Pohon Penelusuran Biner seimbang lainnya, kompleksitas waktu untuk mencari, menyisipkan, dan menghapus adalah O (Logn).

Operasi dalam B-Tree
1. Search
Mulai dari root dan secara rekursif melakukan traverse. Untuk setiap node non-leaf yang dikunjungi, jika simpul tersebut memiliki kunci, maka akan mereturn node tersebut. Jika tidak, kembali ke anak yang sesuai (Anak yang tepat sebelum kunci pertama yang lebih besar) dari node. Jika kami mencapai simpul daun dan tidak menemukan k di simpul daun,  maka akan mengembalikan NULL.

2. Insert 
Key yang diinsert akan selalu masuk ke node leaf. Namun, sebelum menginsert harus dipastikan bahwa ada tempat kosong di node leaf tersebut.

3. Delete
Untuk mendelete sebuah node pada B-Tree harus memperhatikan properties B-Tree.