People Innovation Excellence

Deletion – AVL Tree

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.

Ada 2 kasus yang biasanya terjadi saat operasi delete dilakukan, yaitu :
– Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus.

  • Jika node yang akan dihapus memiliki anak, maka proses penghapusannya harus di cek kembali untuk menyeimbangkan Binary Search Tree dengan perbedaan tinggi / level maksimal 1.
  • anggap T adalah node yang harus diseimbangkan kembali
    – Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)
    – Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)
    – Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)
    – Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)

Berikut contoh dalam menghapus node AVL Tree, terdapat AVL Tree yang kemudian di hapus node 60. Dengan gambaran sebagai berikut :

Yang akan menggantikan posisi node 60 adalah node 55. Akan terjadi ketidak seimbangan. Dengan tampilan sebagai berikut :

Maka akan dilakukan single rotation pada node 55 dengan kasus ketidak seimbangan pada kasus no. 2. Dengan tampilan setelah dilakukan single rotation sebagai berikut :

Ketika sudah dilakukan single rotation dan dilakukan kembali perbedaan tinggi / level maksimal 1 ternyata terdapat ketidak seimbangan yang terjadi. Sehingga diperlukan double rotation dengan kasus no. 4. Sehingga hasil dari rotasi yang dilakukan adalah sebagai berikut :

Rerefence :

Reema Thareja,. 2011. Data structures using C. OXFORD. New Delhi


Published at :
Written By
Violitta Yesmaya, S.Kom., M.T.I
Deputy Head of Computer Science Program | School of Computer Science
Leave Your Footprint

    Periksa Browser Anda

    Check Your Browser

    Situs ini tidak lagi mendukung penggunaan browser dengan teknologi tertinggal.

    Apabila Anda melihat pesan ini, berarti Anda masih menggunakan browser Internet Explorer seri 8 / 7 / 6 / ...

    Sebagai informasi, browser yang anda gunakan ini tidaklah aman dan tidak dapat menampilkan teknologi CSS terakhir yang dapat membuat sebuah situs tampil lebih baik. Bahkan Microsoft sebagai pembuatnya, telah merekomendasikan agar menggunakan browser yang lebih modern.

    Untuk tampilan yang lebih baik, gunakan salah satu browser berikut. Download dan Install, seluruhnya gratis untuk digunakan.

    We're Moving Forward.

    This Site Is No Longer Supporting Out-of Date Browser.

    If you are viewing this message, it means that you are currently using Internet Explorer 8 / 7 / 6 / below to access this site. FYI, it is unsafe and unable to render the latest CSS improvements. Even Microsoft, its creator, wants you to install more modern browser.

    Best viewed with one of these browser instead. It is totally free.

    1. Google Chrome
    2. Mozilla Firefox
    3. Opera
    4. Internet Explorer 9
    Close