AVL Tree merupakan salah satu jenis BST (binary Search Tree). BST digunakan dengan tujuan untuk mempercepat pencarian data. Apabila BST yg terbentuk cukup seimbang (mendekati complete binary tree) maka waktu pencarian data tidak lebih dari log2n langkah.
AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.
AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.
Cara menentukan Height dan Balance Factor:
Height:
- Jika node(root) tidak memilik 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
AVL Tree Operation
A.Insertion
Insert suatu node pada AVL sama halnya pada insert node pada binary search tree, dimana node baru diposisikan sebagai leaf. Setelah memasukan node baru, maka harus dilakukan penyeimbangan kembali pada path dari node yang baru di insert atau path terdalam.
Ada 4 Kasus yang biasanya terjadi saat operasi insert:
1. Node terdalam terletak pada subtree kiri dari naak kiri T (left-left)
2. Node terdalam terletak pada subtree kanan dari anak kanan T (right - right)
3. Node terdalam terletak pada subtree kanan dari anak kiri T (right - left)
4. Node terdalam terletak pada subtree kiri dari anak kanan T(left- right)
Cara menangani keempat kasus tersebut ada 2 cara:
1. Single rotation
Single rotation(rotasi 1x) dilakukan apabila searah, left - left atau right- right.
Berikut gambar dari operasi single rotation
2.Double rotation
Double rotation(rotasi 2x) apabila searah, left- right atau right -left
berikut gambar dari operasi double rotation,
B. Deletion
Operasi deletion node sama seperti pada Binary Search Tree, yaitu node yang dihapus digantukan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan. Jika yang dihapus adlaah 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 sama seperti operasi insertion.
Berikut conoth dari operasi Deletion
*Kita ingin menghapus node (60)
Refference:
Komentar
Posting Komentar