AVL Tree
AVL Tree
merupakan salah satu bentuk dari BST. Perbedaan AVL tree dari BST biasa
merupakan keseimbangan antara kiri dan kanan. Jika di BST hal tersebut tidak
diperhatikan dalam AVL tree bagian kiri dan kanan tree kita perlu seimbang
sehingga tidak boleh ada bagian yang jauh lebih dalam.Untuk membuat AVL tree
kita seperti membuat BST dengan syarat tambahan yaitu keseimbangan tree kita.
Rotation.
Rotation merupakan
cara kita menyeimbangkan tree kita. syarat-syarat untuk melakukan rotasi adalah
:
-jika ada
yang tidak seimbang di anak subtree kanan bagian kiri, maka kita akan melakukan
rotasi LRR dimana kita akan LR kemudian RR yaitu mengubah posisi masing-masing
ke kiri satu dari posisi awal kemudain mengubah posisi masing-masing ke kanan satu
dari posisi sekarang untuk bagian subtree yang tidak seimbang.
-jika ada
yang tidak seimbang di anak subtree kiri bagian kiri, maka kita lakukan RR
dimana kita mengubah posisi masing-masing node ke kanan satu dari posisi saat
ini di bagian subtree yang tidak seimbang.
-jika ada
yang tidak seimbang di anak subtree kanan bagian kanan, maka kita lakukan LR
dimana kita mengubah posisi masing-masing node ke kiri satu dari posisi saat
ini di bagian subtree yang tidak seimbang.
-jika ada
yang tidak seimbang di anak subtree kanan bagian kiri, maka kita lakukan RLR
dimana kita lakukan RR kemudian kita lakukan LR yaitu menggubah posisi masing-masing
node ke kanan satu kemudian mengubah posisinya lagi kekiri satu.
B-Tree
B-tree
merupakan tree yang dapan memiliki banya anak di kedua bagian. Akan tetapi
dalam b tree kita memiliki batas minimal dan maksimal untuk setiap anak.
Aturan dalam
membuat B-tree adalah:
-
Setiap
Node memiliki paling banyaka m anak.
-
Setiap
Node memiliki paling sedikit m/2 anak.
-
Jika
root bukan merupakan leaf root harus memiliki minimal 2 anak.
-
Jika
Node memiliki n anak maka data maksimal yang dapat disimpan dalam Node tersebut
adalah n-1.
-
Semua
leaf harus berada pada level yang sama.
