fbpx

Struktur Data : Operasi AVL Tree

Operasi Insert

Ada 4 kasus yang biasanya terjadi setelah operasi insert dilakukan: (T adalah node yang harus diseimbangkan)

  • Kasus 1 : node terbawah terletak pada subtree kiri dari anak kiri T (left-left)
  • Kasus 2 : node terbawah terletak pada subtree kanan dari anak kanan T (right-right)
  • Kasus 3 : node terbawah terletak pada subtree kanan dari anak kiri T (right-left)
  • Kasus 4 : node terbawah terletak pada subtree kiri dari anak kanan T (left-right)

Ke-4 kasus tersebut dapat diselesaikan dengan melakukan rotasi:

  • Kasus 1 dan 2 dengan single rotation
  • Kasus 3 dan 4 dengan double rotation

Single Rotation

Kasus 1

Kasus 2

Contoh

  • Node T adalah 30, lakukan rotasi kanan dengannode anak (kiri/kanan) menggantikan node T
  • Jadikan subtree B sebagai anak kiri node T
  • Node T adalah 10, lakukan rotasi kanan dengan node 5 menggantikan node 10
  • Node 8 menjadi anak kiri node T (10)
  • Node T adalah 30, laukan rotasi kiri dengan node 35 menggantikan node 30
  • Node 32 menjadi anak kanan node T (30)

Double Rotation

Contoh

  • Lakukan rotasi kiri pada node T-1 (node 22). Node 27 menggantikan node 22 dan subtree (24,26) menjadi anak kanan node 22
  • Lakukan rotasi kanan pada node T (node 30). Node 27 mengantikan node 30 dan node 29 menjadi anak kiri node 30.
  • Lakukan rotasi kiri pada node T-1 (Node 5)
  • Lakukan rotasi kanan dengan node 6 mengantikan node 10

Operasi Delete

Jika node yang akan dihapus berada pada posisi leaf atau node terbawah, 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

  • Diseimbangkan dengan melakukan rotasi, sama seperti waktu insert
  • Kasus 1 dan 2 dengan single rotation
  • Kasus 3 dan 4 dengan double rotation

Contoh

  • Jika kita menghapus node 60 di AVL tree sebelah kiri, maka node 55 akan menggantikan node 60 (Ingat: carimaksimum di subtree kiri atau minimum di subtree kanan untuk menggantikan node yang dihapus)
  • Tree menjadi tidak balanced (kasus 2) setelah proses penghapusan dan harus diseimbangkan
  • Lakukan single rotation (rotasi kiri) pada node T = 55 ๐Ÿกช ternyata masih tidak seimbang (kasus 4)
  • Diperlukan double rotation untuk kasus 4 (rotasi kiri pada node 25 dan rotasi kanan pada node 50) untuk menyeimbangkan AVL tree

Materi Lengkap

Silakan baca juga beberapa artikel menarik kami tentang Tree (Bagian 2), daftar lengkapnya adalah sebagai berikut.


Tonton juga video pilihan dari kami berikut ini

Bagikan ke teman-teman Anda

Contact Us

How to whitelist website on AdBlocker?

How to whitelist website on AdBlocker?

  1. 1 Click on the AdBlock Plus icon on the top right corner of your browser
  2. 2 Click on "Enabled on this site" from the AdBlock Plus option
  3. 3 Refresh the page and start browsing the site
error: Content is protected !!
Up