Skip to main content

AVL Tree

AVL Tree

AVL Tree ditemukan oleh Adelson-Velskii dan Landis. AVL Tree merupakan salah satu jenis BST (binary Search Tree). BST digunakan dengan tujuan untuk mempercepat pencarian data. Apabila BST yg terbentuk cukup seimbang (mendekati complete binary tree) maka waktu pencarian data tidak lebih dari log2n langkah. 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.

Insertion

Untuk menjaga tree tetap imbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru → root. Node pertama yang memiliki |balance factor| > 1 diseimbangkan. Proses penyeimbangan dilakukan dengan: Single Rotation dan Double Rotation.

Single Rotation

Single rotation dilakukan bila kondisi AVL Tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar 2. T1, T2, dan T3 adalah subtree yang urutannya harus seperti demikian serta height- nya harus sama (≥ 0). Hal ini juga berlaku untuk AVL tree yang merupakan citra cermin (mirror image).

Double Rotation

Double Rotation dilakukan bila kondisi AVL Tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar 3. T1, T2, T3, dan T4 adalah subtree yang urutannya harus seperti demikian. Tinggi subtree T1 harus sama dengan T4 (≥ 0), tinggi subtree T2 harus sama dengan T3 (≥ 0). Node yang ditambahkan akan menjadi child dari subtree T2 atau T3. Hal ini juga berlaku untuk AVL Tree yang merupakan citra cermin (mirror image).


Deletion

Proses menghapus sebuah node di AVL Tree hampir sama dengan BST. Penghapusan sebuah node dapat menyebabkan tree tidak imbang Setelah menghapus sebuah node, lakukan pengecekan dari node yang dihapus → root. Gunakan single atau double rotation untuk menyeimbangkan node yang tidak imbang. Pencarian node yang imbalance diteruskan sampai root. 

Sumber:
- socs.binus.ac.id
- dinda-dinho.blogspot.com
Labels:

Comments

Post a Comment

Popular posts from this blog

Hashing Table and Binary Tree

Hashing Hashing adalah teknik pada Data Strucuture yang digunakan untuk memetakan nilai yang diberikan dengan kunci tertentu untuk akses elemen yang lebih cepat. Misalkan fungsi hash H(x) memetakan nilai x pada indeks x% 10 dalam sebuah array. Sebagai contoh jika daftar nilai adalah [11,12,13,14,15] itu akan disimpan di posisi {1,2,3,4,5} masing-masing dalam array atau tabel hash.  Hash Function pada Data Structure: 1. Division Method Dalam hal ini fungsi hash tergantung pada sisa pembagian. Sebagai contoh, 52,68,99,84 harus ditempatkan di tabel hash dan mari kita ambil ukuran tabel adalah 10. Lalu, (key)=record% table size.  2=52%10  8=68%10 9=99%10 4=84%10 2. Mid Square Method Dalam metode ini pertama kunci kuadrat dan kemudian bagian tengah hasilnya diambil sebagai indeks. Sebagai contoh, pertimbangkan bahwa jika kita ingin menempatkan catatan 3101 dan ukuran tabel adalah 1000. Jadi 3101 * 3101 = 9616201 yaitu h (3101) = 162 (tengah 3...
Post a Comment
Read more

Heap dan Tries

Heap Heap  adalah struktur data berbasis pohon khusus di mana pohon itu adalah pohon biner lengkap. Secara umum, Heap  terdiri dari dua jenis, yaitu: Max-Heap : Dalam Max-Heap node root harus paling besar di antara node yang ada di semua children-nya. Properti yang sama harus benar secara rekursif untuk semua subtree di Tree tersebut. Min-Heap : Dalam Min-Heap node root harus paling kecil di antara node yang ada di semua children-nya. Properti yang sama harus benar secara rekursif untuk semua subtree di Tree tersebut. Insert Untuk melakukan I nsert , kita harus melakukan operasi up-heap. Tambahkan elemen pada level bawah Heap , Bandingkan elemen yang baru dengan parentnya. Jika berada di urutan yang benar, pembandingan berhenti. Jika tidak, swap elemen dengan parent dan kembalikan ke langkah sebelumnya. Delete Untuk melalkukan delete, kita harus melakukan operai down-heap. Ganti root Heap dengan elemen terakhir pada level terakhir. Bandingkan root baru dengan children-nya. J...
Post a Comment
Read more