Pada pertemuan kali ini kami membahas Balanced Binary Tree dan kami juga didatangi oleh Dosen Tamu bernama Selvakumar Manickam, Senior Lecture of University Science of Malaysia . Balanced Binari Tree memiliki 2 macam antara lain AVL dan Red-Black Tree, namun pada pertemuan kali ini kami hanya membahas soal AVL.
Height :
– Jika node (root) tidak memiliki subtree heightnya = 0
– Jika node adalah leaf, height = 1
– Jika internal node, maka height = height tertinggi dari anak + 1
Balance Factor :
-selisih height antara anak kiri dan kanan, jika tidak memiliki anak, dianggap 0.
Single Rotation
Single rotasi (rotasi 1x) dilakukan apabila searah, left-left atau right-right
Gambaran Single Rotation :
Double Rotation
Double rotasi (rotasi 2x) dilakukan apabila searah, left-right atau right-left
Gambaran Double Rotation :
Deletion
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 hapus saja. Namun jika node yang dihapus memiliki child maka childnya yang menggantikannya. Namun setelah operasi penghapusan dilakukan, cek kembali apakah tree sudah seimbang atau belum, jika belum maka harus diseimbangkan kembali. Cara menyeimbangkannya pun sama seperti insertion.
Untuk Sesi kedua, Selvakumar Manickam melakukan Review yang dapat dilihat di :