Pada modul sebelumnya dibahas bagaimana mendeteksi imbalance tree, pada modul ini akan dibahas bagaimana rebalancing tree tersebut.
Ada 4 macam imbalance tree, yaitu left-left, right-right, left-right dan right-left imbalance. Untuk jelasnya lihat gambar berikut.
Untuk melakukan balancing padan tree, digunakan rotasi. Berdasarkan tipe imbalance tree, terdapat 4 cara rotasi:
- left-left, lakukan right rotation.
- right-right, lakukan left rotation.
- left-right, lakukan left rotation untuk mengubah tree menjadi left-left, kemudian lakukan right rotation.
- right-left, lakukan right rotation untuk mengubah tree menjadi right-right, kemudian lakukan left rotation.
Right rotation pada left-left imbalance
Berikut tahap-tahap right rotation dengan contoh kasus tree pada gambar-1.
- Pertama tentukan pivot point, pada gambar dibawah adalah node 20.
- Kemudian lakukan rotasi ke kanan, dimana node 20 akan menjadi root.
- Node 10 dan children akan langsung dipasangkan dibawah node 20, sebagai kaki kiri.
- Node 20 dan children akan langsung dipasangkan dibawah node 20, sebagai kaki kanan.
- Node 25 akan dipasangkan dikaki kiri node 30.
Left rotation pada right-right imbalance
Berikut tahap-tahap leftrotation dengan contoh kasus tree pada gambar-2.
- Pertama tentukan pivot point, pada gambar dibawah adalah node 40.
- Kemudian lakukan rotasi ke kiri, dimana node 40 akan menjadi root.
- Node 60 dan children akan langsung dipasangkan dibawah node 40, sebagai kaki kanan.
- Node 30 dan children akan langsung dipasangkan dibawah node 40, sebagai kaki kiri.
- Node 35 akan dipasangkan dikaki kanan node 30.
Left rotation – Right Rotation pada left-right imbalance
Untuk balancing left-right imbalance tree, digunakan 2 rotasi diatas, yaitu left rotation hanya pada pivot point. Tree akan menjadi left-left imbalance, baru balancing dengan right rotation.
- Pertama tentukan pivot point untuk left rotation, pada gambar dibawah adalah node 20.
- Kemudian lakukan rotasi ke kiri, dimana node 20 akan menggantikan posisi node 10.
- Node 10 dan children akan langsung dipasangkan dibawah node 20, sebagai kaki kiri.
- Node 25 akan langsung dipasangkan dibawah node 20, sebagai kaki kanan.
- Node 15 akan dipasangkan dikaki kanan node 10.
- Sekarang kita memiliki left-left unbalanced (sama seperti gambar-1), langkah selanjutnya adalah melakukan right rotation.
Righ rotation – Left rotation pada right-left imbalance
Untuk balancing right-right imbalance tree, digunakan 2 rotasi diatas, yaitu right rotation hanya pada pivot point. Tree akan menjadi right-right imbalance, baru balancing dengan left rotation.
- Pertama tentukan pivot point untuk right rotation, pada gambar dibawah adalah node 40.
- Kemudian lakukan rotasi ke kanan, dimana node 40 akan menggantikan posisi node 60.
- Node 60 dan children akan langsung dipasangkan dibawah node 40, sebagai kaki kanan.
- Node 35 akan langsung dipasangkan dibawah node 40, sebagai kaki kiri.
- Node 35 akan dipasangkan dikaki kiri node 60.
- Sekarang kita memiliki right-right unbalanced (sama seperti gambar-2), langkah selanjutnya adalah melakukan left rotation.
