Skip to main content

AVL Tree (Insertion and Deletion)

AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree digunakan untuk melakukan searching yang lebih singkat dan sederhana.

Ada 4 case dalam melakukan operasi insert :

  • Single Rotation
    Ada 2 case yang dapat diselesaikan dengan single rotation, yaitu ketika node terdalam terletak pada subtree kiri dan anak kiri T, (left rotation) dan ketika node terdalam terletak pada subtree kanan dan anak kanan T (right rotation).




  • Double RotationDi double rotation juga terdapat 2 case yang dapat terselesaikan dengan double rotation, yaitu jika node terdalam terletak pada subtree kanan dan anak kiri T (right-left), dan node terdalam terletak pada subtree kiri dan anak kanan T (left-right).


Ada 2 case yang terjadi saat operasi delete :

  1. Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus.
  2. 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)

              Jika kita ingin menghapus node 60

    Terdapat node yang tidak seimbang yaitu node 55, maka kita dapat seimbangkan dengan single rotation (left rotation), tetapi node 50 menjadi tidak seimbang.

    Lalu diseimbangkan dengan double rotation (left-right) karena dari 50 ke 25 kiri dan 25 ke 40 kanan.

     















Comments

Post a Comment

Popular posts from this blog

Binary Search Tree

Binary Search Tree        -         Pengertian       Binary search tree (BST) adalah sebuah data struktur yang digunakan untuk mempercepat        searching, sorting, insertion dan deletion.       BST juga dikenal sebagai binary tree yang sudah disortir       Untuk sebuah node x dari BST : è Value di subtree kiri lebih kecil dari value dalam x è Value di subtree kanan lebih besar dari value dalam x       -         Binary search tree operations       BST mempunyai beberapa operasi : è Search(x) : untuk mencari key x di dalam BST Misalnya kita ingin mencari key x : o    Pertama kita mulai dari root o    Jika root adalah x maka proses selesai o    Jika x lebih kecil dari key root maka dilakukan searching secara rekursif di subtree sebelah kiri, be...
Post a Comment
Read more

Heap & Tries

Heap  Heap adalah suatu tree yang terdiri dari 3, yaitu Min Heap, Max Heap, dan Min-Max Heap. Heap juga berguna untuk membuat Priority Queue. Ciri - ciri dari heap adalah : - Setiap parent mempunyai maksimal 2 child - Root dari heap berupa angka maksimal / minimal dari tree tersebut - Berbeda dengan tree lain, heap menyimpan data-datanya di dalam array - Index array di heap dimulai dari 1 untuk memudahkan ketika mencari parent dari child - Setiap angka baru yang dimasukkan akan berada pada index terakhir yang akan dibandingkan dengan parentnya Rumus untuk mencari parent di heap adalah : Parent_index = index/2 Leftchild_index = index * 2 Rightchild_index = index*2+1 1. Min Heap Min Heap adalah heap yang dimana rootnya adalah angka minimum dari heap itu sendiri. Contoh Insertion : Contoh Deletion : 2. Max Heap Max Heap adalah kebalikan dari min heap. Max heap adalah sebuah heap yang dimana rootnya adalah angka maksimum dari heap itu sendiri. Contoh Insert...
Post a Comment
Read more