NIM : 2301908715
Kelas : CD01 / LY01
Rangkuman AVL Tree
Pengertian AVL Tree
Avl Tree adalah binary search tree yang memiliki perbedaan tinggi antara subtree kiri dan subtree kanan maksimal 1. AVL tree ditemukan oleh G.M. Adelson Veleskii dan E.M. Landis . Tujuan AVL Tree adalah untuk menyimbangkan Binary Search Tree, sehingga waktu pencarian menjadi lebih singkat.
ini adalah contoh AVL Tree.
Insertion dalam AVL Tree
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)
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)
contoh 4 kasus yang biasanya terjadi saat operasi insert dilakukan
Dalam AVL Tree terdapat konsep rotation. Rotation adalah konsep memutar node pada tree. Terdapat 2 rotation dalam AVL Tree yaitu left rotation dan right rotation. Left rotation adalah memutar node yang bersangkutan ke kiri, sedangkan Right rotation adalah memutar node yang bersangkutan ke kanan.
– Kasus 1 dan 2 dengan single rotation
– Kasus 3 dan 4 dengan double rotation
Deletion dalam AVL Tree
Dalam AVL Tree, terdapat 2 kasus dimana biasanya deletion dilakukan . yaitu, jika node yang akan dihapus berada pada posisi leaf (tidak punya anak) dan jika node yang akan dihapus memiliki anak. Jika node yang akan dihapus tidak memiliki anak, maka dapat langsung dihapus. Jika node yang akan dihapus memiliki anak, maka kita harus cek kembali agar perbedaan tinggi/level maksimal nya tidak lebih dari 1.
Ada 4 kasus yang biasanya terjadi saat operasi deletion dilakukan yaitu sebagai berikut:
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)
– 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)
Berikut adalah contoh operasi deletion. node yang akan dihapus adalah node 60. node yang akan menggantikan node 60 adalah 55. sehingga, terjadi ketidak seimbangan seperti gambar di bawah.
Karena tree tidak seimbang, maka dilakukan single rotation pada node 55 seperti berikut
Setelah dilakukan single rotation, ternyata masih ada ketidakseimbangan yang terjadi. Oleh karena itu kita harus melakukan double rotation
Hasilnya adalah seperti gambar di bawah
Sumber
http://algostrukturdata.blogspot.com/2014/05/avl.html
