I. PENGERTIAN
AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi atau level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree dibuat untuk menyeimbangkan Binary Search Tree. AVL Tree dapat membuat bentuk tree lebih simple atau sederhana dan juga waktu pencarian lebih efektif.
II. OPERASI INSERT
Insertion adalah operasi menambahkan node pada tree.
Ada 4 kasus yang dapat terjadi saat operasi insert dilakukan, yaitu:
misalkan : T adalah node yang harus diseimbangkan
1. Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T
2. Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T
3. Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T
4. Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T
Kasus-kasus di atas dapat diselesaikan dengan cara rotasi. Rotasi ada 2 yaitu: single rotation dan double rotation. Single rotation untuk menyelesaikan kasus 1 dan 2. Double rotation untuk menyelesaikan kasus 3 dan 4.
- Single rotation
- Double rotation
II. OPERASI DELETE
Operasi delete adalah menghapus atau menghilangkan node dari tree. Ada 2 tipe delete yaitu :
1. Jika node yang ingin dihapus merupakan leaf atau node yang tidak mempunyai anak, maka node tersebut dapat langsung di delete.
2. Jika node yang ingin dihapus memiliki anak seperti terletak pada 4 kasus dibawah berikut, maka penghapusannya harus di cek kembali agar tree dapat seimbang dan perbedaan tinggi atau levelnya maksimal 1.
4 Kasus yang dapat terjadi pada operasi delete, jika node yang ingin didelete memiliki anak:
1. Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri
2. Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan
3. Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri
4. Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan
Referensi :
https://socs.binus.ac.id/2017/05/15/deletion-avl-tree/
Dibuat oleh :
Livia Leonita - 2301905726
CB01
No comments:
Post a Comment