HELLO

• Binary search tree adalah Tree yang akan lebih memduahkan dalam mencari sebuah data yang diinginkan, karena BST memiliki child kiri yang lebih kecil daripada parentnya sedangkan child kanan lebih besar daripada parentnya.

• Sedangkan AVL tree adalah tree yang merupakan Binary Search Tree yang di buat balanced.

Di dalam AVL tree akan terdapat:

• Height node yang dimulai dari 1
• Balanced factor yang merupakan angka yang didapat dari hasil pengurangan child kiri dikurang dengan child kanan
• Dimana balanced factor dari setiap node haruslah “0” atau “1”, bila melebihi angka “1” berarti terjadi violation dan tree harus dibuat balance agar menjadi AVL tree yang baik dan benar

Dimana angka yang berwarna hitam ialah height sedangkan angka yang berwarna merah adalah balanced factornya.

INSERTION

Aturan insert di dalam AVL tree sama saja dengan BST namun yang membedakan ialah, setiap kali kita selesai memasukkan angka, yang harus dilakukan adalah menghitung balanced factornya untuk menentukan apakah tree sudah balance atau tidak.

• Apabila terjadi violation berarti tree tersebut belumlah balance.

Untuk menyeimbangkan tree:

• Setelah mendapatkan data mana yang terjadi violation, ambil lah 2 jalur pertama menuju nide yang paling terakhir di insert
• Kemudian akan terjadi 2 kemungkinan yaitu: Apakah itu single rotation atau double rotation
• Bila single rotation, cara menyelesaikannya ialah
• 
• Bila double rotation, cara menyelesaikannya ialah
• 
• Contoh insetion dalam AVL tree

DELETION

Begitu juga dengan delete, caranya masi sama dengan BST hanya saja setiap kita menghapus nodenya, kita harus memeriksa ulang apakah terjadi violation

Contoh delete 50

disini terdeteksi bahwa di angka 55 terjadi violation, dan itu adalah single rotation maka:

kemudian, tidak selesai begitu saja, kita harus memeriksa ulang semua balannced factornya lagi

karena di node angka 50 terjadi violation, langkah yang harus dilakukan ialah mencari 2 buah child yang memiliki height yang paling besar.

Dapat dilihat pada gambar, child tersebut adalah 25 dan 40.

Dengan begitu harus diseimbangkan dengan double rotaion agar treenya balance menjadi