AVL Tree And B-Tree

• AVL Tree

Dalam pohon yang benar-benar seimbang, upa pohon kiri dan kanan dari setiap simpul mempunyai tinggi yang sama. Walaupun kita tdak dapat mencapai tujuan ini secara sempurna, setidaknya dengan membangun Binary Search Tree dengan metode penambahan elemen yang nantinya akan meyakinkan setiap upa pohon kiri dan kanan tidak akan berselisih lebih dari 1. Jadi, sebuah AVL-Tree merupakan Binary Search Tree yang upa pohon kiri dan kanan dari akarnya tidak akan berseisih lebih dari 1 dan setiap upa pohon dari AVL-Tree juga merupakan AVL Tree. Dan setiap simpul di AVL-Tree mempunyai faktor penyeimbang yang bernilai left-gigher, equal-height, righthigher.

• Gambar AVL Tree

• Operasi Penambahan Elemen

Karena AVL-Tree ini juga merupakan Binary Search Tree maka penambahan elemen pada AVL-Tree ini juga dapat kita lakukan dengan metode yang sama dengan Binary Search Tree. penambahan elemen itu sering sekali tidak membuat tinggi dari upa pohonnya meningkat sedemikian sehingga dapat membuat selisih tinggi dari upa pohon kiri dan kanan lebih dari 1. Namun, bukan tidak mungkin hal ini bisa terjadi. Satu-satunya kasus dimana masalah ini muncul adalah ketika simpul baru itu ditambahkan ke upa pohon yang lebih tinggi dari upa pohon lainnya sehingga tingginya akan bertambah dan membuat selisih tingginya menjadi lebih dari 1.

• Single Rotation

Single rotation dilakukan bila kondisi AVL Tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar berikut ini

• Double Rotation

Double rotation dilakukan bila kondisi AVL Tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar berikut ini

• Menghapus Node di AVL Tree

Proses menghapus sebuah node di AVL Tree hampir sama dengan BST. Penghapusan sebuah node dapat menyebabkan tree tidak imbang setelah menghapus sebuah node, lakukan pengecekan dari node yang dihapus menjadi root. Gunakan Single Rotation atau Double Rotation untuk menyeimbangkan node yang tidak imbang.

• Balance Tree

dalam Binary Tree Search, tinggi maksimal suatu tree adalah N-1, dimana N adalah jumlah node. Dalam melakukan suatu operasi, misalnya insertion, deletion, dan searching. Kecepata  waktu merupakan hal yang cukup penitng untuk diperhatikan. Setiap operasi pasti di harapkan dapat berjalan dengan cepat, sehingga semakin cepat suatu operasi maka semakin baik. Cepat atau tidaknya suatu operasi, bergantung pada ketinggian tree tersebut, semakin rendah tingginya, maka semakin cepat.