Apa itu AVL Tree? AVL Tree adalah sebuah tree yang sejenis dengan BST. AVL Tree memiliki perbedaan level antara node yang berada di atas ataupun di bawahnya dengan perbedaan minimum -1 dan perbedaan maksimum 1. Perbedaan ini berlaku untuk subtree node yang berada di kanan ataupun di kiri AVL Tree.
Apa sih guna AVL Tree? AVL Tree muncul untuk menyeimbangkan Binary Search Tree (BST), dengan adanya AVL Tree, proses pencarian yang akan kita lakukan (dalam bentuk tree) akan berlangsung/terproses lebih cepat dibandingkan dengan menggunakan BST.
AVL Tree terdiri atas deletion dan insertion.
Insertion
Kasus - kasus dimana harus dilakukan rotation pada saat ingin menambahkan suatu node baru/insert new node, yaitu:
Keterangan:
- Pada kasus 1 dan kasus 2 akan dilakukan single rotation untuk menyeimbangkan node-node yang berada di dalam tree nya.
- Pada kasus 3 dan kasus 4 akan dilakukan double rotation untuk menyeimbangkan node-node yang berada di dalam tree nya.
Single Rotation
Double Rotation
Deletion
Kasus dan cara pada saat ingin melakukan deletion:
- Node yang ingin dihapus berada di leaf/berada di node paling bawah tree. Jika kasus ini terjadi pada saat kita ingin melakukan deletion, berarti kita hanya tinggal langsung menghapus node yang ingin kita hapus/delete tanpa melakukan pengecekan dan pembetulan letak agar node tersebut seimbang.
- Node yang ingin dihapus berada di bagian tengah/bagian awal tree. Jika kasus ini terjadi pada saat kita ingin melakukan deletion, berarti kita harus menghapus node yang telah dipilih (yang ingin dihapus). Lalu apabila dia memiliki anak, kita harus mengganti node yang telah kita hapus dengan node yang berada di bawahnya.
Agar tidak bingung, mari kita lihat contoh deletion yang berada di bagian tengah tree...
Yang diinginkan adalah untuk menghapus node 60
(keadaan tree dimana node 60 sudah dihapus dan tree sudah seimbang)
Tidak ada komentar:
Posting Komentar