Balanced Binary Search Tree
Pada rangkuman sebelumnya, kita telah membahas mengenai Binary Search Tree atau BST. Sebelumnya, juga sudah saya bahas bahwa BST memiliki kelemahan, yaitu suatu kondisi dimana ternyata Tree tersebut tidak benar-benar memiliki Time Complexity O(log n). Kondisi ini disebabkan oleh bentuk Skewed Tree atau tree hanya memanjang ke salah satu sisi saja, sehingga bentuknya mirip linear dan memiliki Time Complexity O(n). Solusi untuk masalah ini adalah Balanced Binary Search Tree yang dapat diimplementasikan melalui beberapa cara, salah satunya AVL yang akan kita bahas pada pertemuan kali ini.
AVL Tree
AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi / height maksimal 1 antara subtree kiri dan subtree kanan.
Berikut gambarannya :
Menentukan Height
Cara menentukan Height dan Balance Factor :
Height :
- Jika node (root) tidak memiliki subtree maka heightnya = 0
- Leaf node heightnya = 1
- Height internal node (node yang bukan root / leaf) = successor maximum height + 1
Balance Factor :
Selisih height antara anak kiri dan kanan. Apabila tidak memiliki anak, Balance Factor = 0.
AVL Tree : Insertion
Insertion pada AVL pada dasarnya sama dengan Binary Search Tree, dimana node baru akan mengisi leaf. Perbedaannya adalah pada AVL, setiap dilakukan insertion, dilakukan juga pengecekkan. Apabila terjadi AVL violation, dimana sebuah node memiliki balance factor > 1, maka dilakukan rebalancing. Pengecekkan umumnya dimulai dari node terdalam, sampai terakhirnya root.
Umumnya pada proses balancing, terdapat 4 kasus.
Node yang menjadi poros balancing biasanya dikenal juga dengan node T.
- 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 kiri dari anak kanan (left - right)
- Kasus 4 : node terdalam terletak pada subtree kanan dari anak kiri (right - left)
Keempat kasus tersebut dapat diselesaikan melalui proses rotasi
- Kasus 1 dan 2 dengan single rotation.
- Kasus 3 dan 4 dengan double rotation.
Note :
- Node terdalam dikenal juga dengan node yang baru di insert.
- Left dan Right adalah proses rotasinya.
Single Rotation
Single Rotation dilakukan apabila node terdalam masih satu path yang lurus dengan node yang melakukan AVL violation, sehingga bila ditarik garis, pathnya terlihat lurus.
 |
| Contoh Single Rotation |
Pada contoh di atas, T melakukan AVL violation, sehingga T menjadi poros untuk proses rebalancing. Node A adalah node terdalamnya. Proses rotasi yang terjadi adalah left - left, dimana T bertukar posisi dengan S, kemudian subtree kanan dari S, menjadi subtree kiri T.
Double Rotation
Double Rotation dilakukan apabila node terdalam memiliki path yang tidak lurus dengan node yang melakukan violation, sehingga apabila ditarik garis, pathnya akan terlihat bengkok.
Contoh Kasus :
 |
| Step 1 : right - right rotation |
 |
| Step 2 : left - left rotation |
Pada kasus di atas, R adalah node terdalam dan T adalah node yang melakukan violation. Proses rotation yang diperlukan untuk rebalancing kasus di atas adalah right-left rotation yang dibagi menjadi 2 step.
AVL Tree : Deletion
Proses Deletion pada AVL juga sama dengan Binary Search Tree, yaitu apabila node yang dihapus adalah leaf, maka langsung dihapus saja. Apabila node yang dihapus memiliki satu child, maka childnya yang akan menggantikan. Apabila node yang dihapus memiliki dua child, maka node yang dihapus akan digantikan dengan node terbesar pada subtree kiri atau node terkecil pada subtree kanan. Namun pada AVL, dilakukan pengecekkan setiap kali proses deletion dilakukan. Apabila tree menjadi tidak seimbang akibat proses deletion, maka rebalancing akan dilakukan (seperti pada insertion).
Contoh Kasus :
 |
| Step 1 : Node yang akan dihapus adalah node 60. Sehingga dicarikan penggantinya yaitu node terbesar dari subtree kiri, node 55. |
 |
| Step 2 : Terjadi violation pada node 55, sehingga diperlukan rotation. Maka, dilakukan lah right-right rotation dengan node 55 sebagai porosnya. |
 |
| Step 3 : Terjadi violation lagi di node 50. Kali ini dibutuhkan double rotation karrena pathnya bengkok. Dilakukanlah right-left Rotation dengan node 50 sebagai poros utama dan 25 sebagai poros right - right rotation. |
 |
| Step 4 : Balanced AVL Tree |
Sekian rangkuman pertemuan kali ini, saya harap rangkuman saya dapat membantu teman-teman dalam memahami konsep AVL Tree.
Referensi :
- http://suciantinovi.blogspot.com/2014/05/balanced-binary-tree-and-2-3-tree.html (Saya mengakui rangkuman saya sangat mirip dengan blogspot tersebut, karena memang saya mengutip blogspot tersebut. Alasannya karena saya sangat setuju dengan isi dari blogspot tersebut, penjelasannya baik. Tapi tentu saya melakukan beberapa perubahan sesuai dengan pemahaman dan preference saya)
- Slide Binusmaya : AVL Tree (hanya mengutip kasus, karena kebanyakan di internet kasusnya kurang relevan dengan apa yang saya ingin sampaikan)
Tidak ada komentar:
Posting Komentar