AVL adalah balanced binary search tree dimana ia memiliki perbedaan jumlah node pada subtree kiri dan subtree kanannya maksimal 1 (atau dapat dikatakan antara tingginya sama atau selisih satu).
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.
Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu :
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)
Ke-4 kasus tersebut dapat diselesaikan dengan melakukan rotasi
- Kasus 1 dan 2 dengan single rotation
- Kasus 3 dan 4 dengan double rotation
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)
Ke-4 kasus tersebut dapat diselesaikan dengan melakukan rotasi
- Kasus 1 dan 2 dengan single rotation
- Kasus 3 dan 4 dengan double rotation
Single rotation
single rotation dilakukan bila kondisi AVL tree akan ditambahkan node baru dan posisi node baru seperti pada gambar berikut.t1,t2,t3 adalah subtree yang urutannya height-nya harus sama (>=0)
Double rotation
Double rotation dijalankan bila kondisi AVL tree akan ditambahkan node baru dan posisi node baru.t1,t2,t3,dan t4 adalah subtree yang urutannya harus seperti demikian.tinggi subtree T1 harus sama dengan T4(>=0),tinggi subtree T2 harus sama dengan T3(>=0).Node yang ditambahkan akan menjadi child dari T2 dan T3.
Deletion AVL
operasi penghapusan node sama seperti pada Binary Search Tree yaitu node yang dihapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan.jika yang dihapus adalah leaf,maka langsung dihapus.namun jika node yang dihapus memiliki child maka childnya yang menggantikannya.dan tree dicek sampai keduanya seimbang.
delete node 60
0 komentar:
Posting Komentar