AVL Tree
AVL(Adelson-Velskii and Landis) tree adalah sebuah binary search tree yang di balancing(diseimbangkan), sebuah AVL tree dikatakan balance jika perbedaan node pada subtree kiri dan subtree kanan maksimal 1. Suatu AVL tree dikatakan seimbang jika mempunyai balance factor antara -1 sampai 1. Balance factor di dapatkan dari tinggi subtree sebelah kiri dikurang dengan subtree kanan. Jika hasilnya tidak sesuai dengan range di balance factor, tree tersebut harus dirotate agar kembali seimbang.
Operasi dalam AVL Tree : Insertion
Insert suatu node pada AVL sama halnya pada insert node pada binary search tree, dimana node baru diposisikan sebagai leaf. Setelah memasukkan node baru, maka harus dilakukan penyeimbangan kembali pada path dari node yang baru di insert atau path terdalam. Namun biasanya, path terdalam adalah path dari node yang baru saja di insert.
Terdapat 4 kasus insertion yang sering kita temui :
– Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)
– Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)
– Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)
– Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)
keempat kasus tersebut bisa diselesaikan dengan rotasi
-kasus 1 & 2 cukup single rotation
-kasus 3 &4 harus double rotation
a. Single Rotation
b. Double Rotation
Operasi dalam AVL Tree : Deletion
Ada 2 kasus yang biasanya terjadi saat operasi delete dilakukan, yaitu :
– Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus.
Jika node yang akan dihapus memiliki anak, maka proses penghapusannya harus di cek kembali untuk menyeimbangkan Binary Search Tree dengan perbedaan tinggi / level maksimal 1.
anggap T adalah node yang harus diseimbangkan kembali
– Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)
– Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)
– Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)
– Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)
source :
Tidak ada komentar:
Posting Komentar