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 dua cara untuk balancing AVL Tree yaitu :

- Insertion
- Deletion

Proses insertion pada AVL Tree sama halnya dengan insertion pada Binary Search Tree. Dimana Node baru diposisikan sebagai leaf. Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu :
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)
vio - 1
Ke-4 kasus tersebut dapat diselesaikan dengan melakukan rotasi
– Kasus 1 dan 2 dengan single rotation
– Kasus 3 dan 4 dengan double rotation
Contoh – Single Rotation: Jika suatu Tree diinsert node baru dengan nilai 12, maka akan terjadi ketidak seimbangan dan hal ini terletak pada posisi root
vio - 2
Contoh – Double Rotation : Jika terdapat sebuah tree yang kemudian dilakukan insert node 26. Maka akan terjadi ketidak seimbangan, sehingga terlihat dari bentuknya dapat diselesaikan dengan kasus 4.
vio - 3
Deletion :
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 :


Comments

Post a Comment

Popular posts from this blog

Heaps

Image
Heaps adalah salah satu bentuk tree yang memenuhi syarat heap. jika anak node lebih besar atau sama dengan node tersebut maka disebut min-heap. lalu jika  sebuah node nilainya lebih besar atau sama dengan anak node tersebut disebut max-heap, adapun gabungan dari kedua heap disebut  min-max heap dimana dalam baris node atas lebih kecil dari node bawahnya lalu node bawahnya lagi lebih besar dan seterusnya. Min Heap & Max Heap Min Max Heap
Read more

HASHING TABLE & BINARY TREE

Image
HASHING TABLE & BINARY TREE Hashing adalah salah satu topik yang akan ditanyakan pewawancara kepada Anda dalam setiap wawancara karena dengan bantuan hashing, Anda dapat melakukan operasi penyisipan, penghapusan, dan pencarian dalam waktu O (1). Dasar-dasar Hashing Hashing adalah cara untuk menyimpan data ke dalam beberapa struktur data (umumnya Tabel Hash digunakan) sedemikian rupa sehingga operasi dasar pada data tersebut yaitu penyisipan, penghapusan, dan pencarian dapat dilakukan dalam waktu O (1). Di sini, data disimpan dalam bentuk pasangan nilai kunci, yaitu untuk setiap data, Anda akan penghapusan, dan pencarian data Anda akan dilakukan. menetapkan beberapa kunci dan berdasarkan pada kunci itu penyisipan, HASHING TABLE Dalam Tabel Hash, untuk menyimpan data kami menggunakan fungsi Hash yang mengambil data sebagai input dan berdasarkan data itu menghasilkan beberapa kunci dan kami menyimpan data berdasarkan kunci itu. Data kami dap...
Read more

LINKED LIST

Image
   Linked list adalah  Koleksi linear dari data, yang disebut sebagai  nodes ,  dimana setiap   node akan menunjuk pada  node  lain melalui sebuah  pointer, linked list juga merupakan k umpulan   nodes  yang merepresentasikan sebuah  sequence.   Dalam linked list terbagi menjadi 2 yaitu single linked list dan doubly linked list. Single linked list adalah sebuah linked list yang menggunakan sebuah variabel pointer saja untuk menyimpan banyak data dengan suatu daftar isi yang saling berhubungan, sedangkan, double linked list adalah mengatasi kelemahan-kelemahan dalam single linked list contohnya dengan dua buah pointer yaitu prev dan next. 1. Single Linked List     Single Linked List merupakan suatu linked list yang hanya memiliki satu varuabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya.Biasanya field pada tail menunjuk ke NULL Single Linked List merupakan suatu linked lis...
Read more