Skip to main content

AVL Tree


AVL Tree diciptakan oleh Adelson-Velskii dan Landis. AVL Tree merupakan Binary Search Tree yang memiliki selisih tinggi / level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree mempersingkat waktu pencarian dan menyederhanakan bentuk tree. 

Tree diatas merupakan AVL karena selisih subtree kiri dan subtree kanan memenuhi salah satu syaratnya yaitu sama dengan 1. 
Di bawah ini adalah tree yang bukan AVL karena selisih subtree kiri dan subtree kanan sama dengan 2, yang berarti tidak memenuhi syarat.


INSERTION
Untuk insertion AVL Tree terdapat 4 case:

1. Single Rotation

Kasus 1 Left-Left Case akan diselesaikan dengan Right Rotate dan menjadi:

       18
     /     \
    5      27

Kasus 2 Right-Right Case akan diselesaikan dengan Left Rotate dan menjadi:

       45
     /     \
    30   75

2. Double Rotation

Kasus 3 Right-Left Case akan diselesaikan dengan Right Rotate lalu Left Rotate menjadi:

(1) Right Rotate
       
       50
           \
           63
              \
              72

(2) Left Rotate

          63
        /      \
      50     72

Kasus 4 Left-Right Case akan diselesaikan dengan Left Rotate lalu Right Rotate menjadi:

(1) Left Rotate

              37
            /
         22
         /
     16

(2) Right Rotate

          22
        /      \
      16     37


DELETION
Operasi penghapusan node pada AVL Tree sama seperti pada Binary Search Tree, yaitu node yang dihapus digantikan oleh node yang memiliki nilai terbesar pada subtree kiri atau node yang memiliki nilai terkecil pada subtree kanan. 

(1) Jika node yang dihapus adalah leaf, maka node tersebut langsung dihapus. 

(2) Jika node yang dihapus memiliki child, maka childnya yang akan menggantikannya. Setelah itu, akan dilakukan pengecekan apakah tree sudah memenuhi syarat AVL, jika belum makan akan diseimbangkan yaitu dengan cara yang sama dengan insertion. 

Sumber:

Comments

Post a Comment

Popular posts from this blog

HASHING, HASH TABLE, BINARY TREE

Hashing merupakan teknik untuk menyimpan data-data dan secara unik mengidentifikasi data tertentu dari sekelompok data serupa. Teknik hashing memudahkan saat ingin melakukan pencarian data karena teknik ini memetakan Hash Key dalam tabel Hash Table menggunakan fungsi yang sudah ditentukan yaitu Hash Function . Konsep hashing digunakan dalam database untuk menyimpan banyak data dan setiap data dimasukkan ke setiap index dalam  Hash Table .  Hash Function (Teknik Hashing)  1. Mid - Square : Teknik ini menguadratkan key yang akan dimasukkan ke hash table, lalu mengambil angka tengah dari hasil yang sudah dikuadratkan sebagai hash key. Contoh:  Key = 3123 Hasil Kuadrat Key = 9753129 Key baru = 531 Jadi hash key yang disimpan adalah 531. 2. Division : Teknik ini mencari sisa bagi dari jumlah karakter yang ingin disimpan (ASCII). Contoh: "PIPE" akan memiliki hash key (64+16 + 64+9 + 64+16 + 64+5) % 97 = 11. 3. Folding :  Teknik ini membagi key menjadi beberapa
Post a Comment
Read more

BINARY SEARCH TREE

Binary Search Tree (BST) merupakaan salah satu struktur data yang digunakan untuk menyimpan data yang mempermudah proses pencarian data (searching), memasukkan data berurut (insertion) dan menghapus data (deletion). Binary Search Tree memiliki bentuk seperti Tree dan setiap data harus memiliki nilai yang berbeda dimana data disebut dengan Node. Node yang berada diposisi paling atas disebut dengan Root. Dalam BST, node akan terhubung dengan node lainnya sebanyak maksimalnya 2. Kedua node memiliki nama left subtree dan right subtree. Left subtree harus memiliki nilai lebih kecil dari nilai di node dan right subtree harus memiliki nilai lebih besar dari node. Node yang tidak memiliki left maupun right subtree disebut leaf. Searching Misalkan ingin mencari integer dengan value n. Searching dimulai dari Root. Apabila n bernilai sama dengan Root, pencarian data akan berhenti karena data sudah ditemukan. Namun, apabila n bernilai lebih kecil dari Root, maka pencarian b
Post a Comment
Read more