AVLdanBtree

AVL dan Btree

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.

Ketinggian subtree kosong adalah 0. Tinggi daun adalah 1. Ketinggian simpul internal adalah ketinggian maksimum anak-anaknya ditambah 1. Faktor keseimbangan semua node di pohon AVL harus paling banyak 1. 

Operasi pada AVL :
- insertion 

insert node baru pada bst, dimana node baru diposisikan sebagai leaf. Setelah itu, dilakukan penyeimbangan pada path dari node yang baru diinsert.

- deletion

node yang dihapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan.

Selain itu, terdapat single rotation dan double rotation. Single rotation merupakan rotasi sekali left ke left atau right ke right. Sedangkan double rotation merupakan dua kali rotasi dengan left-right ataupun sebaliknya.

Btree

Akar Btree paling sedikit memiliki 2 simpul anak. Btree adalah tree yang dimana tidak memiliki simpul daun yang lebih panjang terhadap daun yang lain. 

Pada Btree terdapat search, insert, delete, dan create.

Untuk search digunakan ketika kita ingin mencari suatu data dengan indeks yang diinginkan. Untuk insert digunakan ketika memasukkan data. Delete untuk menghaapus data, dan create untuk membuat data baru.