AVL Tree
Nama : Raymon Elnardi
Nim : 2301908620
AVL Tree (Georgy Adelson-Velsky and Landis' tree) adalah BST yang diseimbangkan (Balanced).
Tujuannya di terapkan AVL Tree kedalam BST adalah untuk mecegah worst case dari BST (Skewed BST) dan memastikan height dari BST menjadi O Log N.
Adapula hal hal yang harus diketahui terlebih dahulu sebelum melanjutkan AVL Tree,
1. height dari sebuah subtree yang kosong bernilai 0
2. height dari sebuah leaf bernilai 1
3. height dari sebuah internal node sama dengan maksimum height dari childern ditambah 1
Balance Factor, selisih dari subtree kanan dan subtree kiri
syarat untuk membuat AVL Tree adalah, setiap node pada Tree harus memiliki Balance Factor berkisar -1 sampai 1.
gambar diatas adalah contoh dari AVL Tree.
Gambar diatas menjelaskan bagaimana proses berubahnya BST non-AVL menjadi AVL Tree.
Dari gambar diatas dapat dilihat bahwa terdapat pelanggaran pada node 2 karena Balance Factornya bernilai 2, maka dari kita perlu mengubah posisi node 2.
ada 2 jenis pelanggaran AVL Tree,
1. Ketika 2 buah garis yang ditarik dari node yang dilanggar ke node subtreenya lurus (Left-Left atau Right-Right), maka kita gunakan Single Rotation.
2. Ketika 2 buah garis yang ditarik dari node yang dilanngar ke node subtreenya berkelok-kelok (Left -Right atau Right-Left) kita gunakan Double Rotation.
Saya akan mejelaskan bagaimana cara kerja Single Rotation menggunakan contoh diatas.
Pertama- tama kita perlu mengidentifikasi node mana yang melanggar aturan AVL Tree, yang mana memiliki Balance Factor kurang dari -1 atau lebih dari 1, dapat kita lihat bahwa node 2 memiliki subtree kiri yang height-nya 1 dan subtree kanan yang height-nya 3, 1 - 3 = -2, berarti node 2 melanggar aturan tersebut.
Kedua, kita perlu memindahkan node 2 kearah subtree yang lebih kecil, yaitu subtree kiri, yang kemudian posisi node 2 akan digantikan oleh child-nya yang berada di subtree kanan, yaitu node 4.
Terakhir, jika dipikirkan kembali, sekarang node 4 memiliki 3 buah Child, yaitu 2,3, dan 5 sehingga kita perlu memindahkan node 3 ke subtree kanan milik node 2.
Dengan begitulah sekarang BST tersebut menjadi AVL Tree.
*Untuk Double Rotation hanya melakukan Single Rotation Sebanyak 2x.
Terima Kasih
Nim : 2301908620
AVL Tree (Georgy Adelson-Velsky and Landis' tree) adalah BST yang diseimbangkan (Balanced).
Tujuannya di terapkan AVL Tree kedalam BST adalah untuk mecegah worst case dari BST (Skewed BST) dan memastikan height dari BST menjadi O Log N.
Adapula hal hal yang harus diketahui terlebih dahulu sebelum melanjutkan AVL Tree,
1. height dari sebuah subtree yang kosong bernilai 0
2. height dari sebuah leaf bernilai 1
3. height dari sebuah internal node sama dengan maksimum height dari childern ditambah 1
Balance Factor, selisih dari subtree kanan dan subtree kiri
syarat untuk membuat AVL Tree adalah, setiap node pada Tree harus memiliki Balance Factor berkisar -1 sampai 1.
gambar diatas adalah contoh dari AVL Tree.
Gambar diatas menjelaskan bagaimana proses berubahnya BST non-AVL menjadi AVL Tree.
Dari gambar diatas dapat dilihat bahwa terdapat pelanggaran pada node 2 karena Balance Factornya bernilai 2, maka dari kita perlu mengubah posisi node 2.
ada 2 jenis pelanggaran AVL Tree,
1. Ketika 2 buah garis yang ditarik dari node yang dilanggar ke node subtreenya lurus (Left-Left atau Right-Right), maka kita gunakan Single Rotation.
2. Ketika 2 buah garis yang ditarik dari node yang dilanngar ke node subtreenya berkelok-kelok (Left -Right atau Right-Left) kita gunakan Double Rotation.
Saya akan mejelaskan bagaimana cara kerja Single Rotation menggunakan contoh diatas.
Pertama- tama kita perlu mengidentifikasi node mana yang melanggar aturan AVL Tree, yang mana memiliki Balance Factor kurang dari -1 atau lebih dari 1, dapat kita lihat bahwa node 2 memiliki subtree kiri yang height-nya 1 dan subtree kanan yang height-nya 3, 1 - 3 = -2, berarti node 2 melanggar aturan tersebut.
Kedua, kita perlu memindahkan node 2 kearah subtree yang lebih kecil, yaitu subtree kiri, yang kemudian posisi node 2 akan digantikan oleh child-nya yang berada di subtree kanan, yaitu node 4.
Terakhir, jika dipikirkan kembali, sekarang node 4 memiliki 3 buah Child, yaitu 2,3, dan 5 sehingga kita perlu memindahkan node 3 ke subtree kanan milik node 2.
Dengan begitulah sekarang BST tersebut menjadi AVL Tree.
*Untuk Double Rotation hanya melakukan Single Rotation Sebanyak 2x.
Terima Kasih
Komentar
Posting Komentar