AVL Tree
AVL tree adalah binary search tree yang selisih Heightnya diantara -1,0,1.
AVL tree digunakan dalam binary search tree untuk menyeimbangkan dan menyederhanakan BST agar mudah untuk dicari, BST yang selisih Heightnya kurang dari -1 dan lebih dari 1 akan memerlukan Balancing.
 |
| https://miro.medium.com/max/1024/0*Vi3aQ9sY9Yu4VNpa.png |
Balancing memiliki beberapa kondisi, yaitu:
- Jika ada Unbalance pada anak kiri subtree kanan, maka dapat dilakukan rotasi kiri-kanan.
- Jika ada Unbalance pada anak kiri subtree kiri, maka dapat dilakukan rotasi kanan.
- Jika ada Unbalance pada anak kanan subtree kanan, maka dapat dilakukan rotasi kiri.
- Jika ada Unbalance pada anak kanan subtree kiri, maka dapat dilakukan rotasi kanan-kiri.
Algoritma Insert pada AVL Tree:
- Masukkan Node baru menggunakan rekursif sehingga saat melacak kembali Anda akan semua node orang tua untuk memeriksa apakah mereka masih seimbang atau tidak.
- Setiap node memiliki bidang yang disebut tinggi dengan nilai default sebagai 1.
- Ketika simpul baru ditambahkan, ketinggian simpul orang tuanya bertambah 1.
- Jadi seperti yang disebutkan pada langkah 1, setiap tinggi leluhur akan diperbarui saat kembali melacak ke root.
- Di setiap node, faktor keseimbangan juga akan diperiksa. faktor keseimbangan = (tinggi Subtree kiri - tinggi Subtree kanan).
- Jika Balance Factor = 1 berarti pohon seimbang pada simpul itu.
- Jika Balance Factor > 1 berarti pohon tidak seimbang pada simpul itu, tinggi kiri lebih tinggi daripada kanan sehingga itu berarti kita perlu rotasi. (Baik Kiri-Kiri atau Kiri-Kanan).
- Katakanlah simpul saat ini yang kita periksa adalah X dan Jika simpul baru kurang dari X.left maka itu akan menjadi kasus Kiri-Kiri, dan jika simpul baru lebih besar dari X.left maka itu akan menjadi kasus Kiri-Kanan. lihat gambar di atas.
- Jika Balance Factor < -1 berarti pohon tidak seimbang pada simpul itu, tinggi kanan lebih tinggi dari kiri sehingga itu berarti kita perlu rotasi. (Baik Kasus Kanan-Kanan atau Kanan-Kiri)
- Katakanlah node saat ini yang kita periksa adalah X dan Jika node baru kurang dari X.right maka itu akan menjadi kasus Kanan-Kanan, dan jika node baru lebih besar dari X.right maka itu akan menjadi kasus Kanan-Kiri.
Contoh Insert dan Delete pada AVL Tree:
 |
| Source: https://drive.google.com/file/d/18ffgLVaiJL8Ebhyx06oAywXt4M2Z4FAd/view?usp=sharing |
B-Tree
B-Tree adalah pohon seimbang yang dioptimalkan untuk situasi saat sebagian atau seluruh pohon harus dipertahankan dalam penyimpanan sekunder seperti disk magnetik . Karena akses disk yang mahal ( memakan waktu ) operasi , b-tree mencoba untuk meminimalkan jumlah akses disk . Sebagai contoh, b - tree dengan ketinggian 2 dan faktor percabangan 1001 dapat menyimpan lebih dari satu miliar kunci tetapi membutuhkan paling banyak dua akses disk untuk mencari setiap node.
Karakteristik B-Tree:
- Semua daun akan dibuat pada level yang sama.
- B-Tree ditentukan oleh sejumlah derajat, yang juga disebut "urutan" (ditentukan oleh aktor eksternal, seperti programmer), disebut sebagai m
- Subtree kiri dari node akan memiliki nilai lebih rendah dari sisi kanan subtree. Ini berarti bahwa node juga diurutkan dalam urutan menaik dari kiri ke kanan.
- Jumlah maksimum node anak, sebuah simpul root serta simpul turunannya dapat dihitung dengan rumus ini: m-1
Keuntungan menggunakan B-Tree:
- Mengurangi jumlah pembacaan yang dilakukan pada disk
- Pilihan yang baik untuk memilih ketika proses reading dan writing pada blok data yang besar
- B Tree dapat dengan mudah dioptimalkan untuk menyesuaikan ukurannya (yaitu jumlah node anak) sesuai dengan ukuran disk
- Ini adalah teknik yang dirancang khusus untuk menangani sejumlah besar data.
- Algoritma yang paling tepat untuk database dan sistem file.
Algoritma Insert pada B-Tree:
- Alokasikan Leaf yang baru dan pindahkan setengahnya ke kumpulan elemen yang baru.
- Masukkan kunci dan alamat terkecil daun baru ke induk.
- Jika induk sudah penuh, pisahkan.
- Tambahkan kunci tengah ke simpul induk.
- Ulangi sampai ditemukan orangtua yang tidak perlu dibagi.
- Jika root terpecah, buat root baru yang memiliki satu kunci dan dua pointer. (Yaitu, nilai yang didorong ke root baru akan dihapus dari node asli)
Contoh Insert dan Delete pada B-Tree :  |
| Source : https://drive.google.com/file/d/18ffgLVaiJL8Ebhyx06oAywXt4M2Z4FAd/view?usp=sharing |
