AVL Tree

AVL

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. AVL dapat mempercepat proses pencarian.








Pohon AVL pertama kali di temukan oleh Adelson-Velsky dan Landis. AVL adalah Binary Search Trre yang menyeimbangkan diri dan merupakan struktur data pertama yang ditemukan.Dalam pohon AVL, ketinggian dua anak anak dari setiap simpul berbeda paling banyak satu; jika suatu saat mereka berbeda lebih dari satu, penyeimbangan kembali dilakukan untuk memulihkan properti ini.



Untuk menjaga tree tetap seimbang dilakukan pemeriksaan dari node baru . 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 di samping. 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) gambar di samping.












Double Rotation

Double rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar di samping. 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) gambar di samping.











Sekian dari thread ini, Terimah kasih.

Komentar

Posting Komentar

Postingan populer dari blog ini

Gambar
HEAP Apa itu heap? adalah struktur data berbasis pohon khusus di mana pohon tersebut adalah pohon biner lengkap. Secara umum, tumpukan dapat terdiri dari dua jenis: Max-Heap : Di Max-Heap kunci di simpul root harus menjadi yang terbesar dari semua kunci di semua anak. Properti yang sama harus benar secara rekursif untuk semua sub-pohon di Pohon Biner. Min-Heap : Di Min-Heap kunci di simpul root harus minimum kunci di semua anak. Properti yang sama harus benar secara rekursif untuk semua sub-pohon di Pohon Biner. Fungsi Heap adalah  untuk menemukan nilai max untuk max heap, dan min untuk min heap. contoh soal Input:  35 33 42 10 14 19 27 44 26 31 Max - heap Di mana root node lebih besar atau sama dengan salah satu dari anak-anaknya. Min - heap Di mana root node kurang dari atau sama dengan salah satu dari anak-anaknya. Insertion Saat sebuah data dimasukkan kedalam heap, maka data langsung ditempatkan di index terakh...
Baca selengkapnya
Gambar
Struktur Data     Struktur data atau biasa  di sebut Data Structure  adalah cara menyimpan atau merepresentasikan data didalam komputer agar bisa dipakai secara efisien. Sedangkan data adalah representasi dari fakta dunia nyata. Fakta atau keterangan tentang kenyataan yang disimpan, direkam atau direpresentasikan dalam bentuk tulisan, suara, gambar, sinyal atau simbol. Struktur data yang biasanya di pelajari di bagi bagi menjadi beberapa bagian, yaitu: 🔻🔻🔻🔻🔻🔻🔻🔻🔻🔻🔻🔻 Struktur data sederhana    Co ntoh nya : array dan record. Struktur data majemuk Pada Struktur majemuk pun di bagi menjadi 2, yaitu: ➤Linier : Stack, Queue, sertaList dan Multilist ➤Non Linier : Pohon Biner dan Graph Berikut merupakan tipe tipe Struktur data sederhana yang sering di gunakan dalam pemakaian sehari hari : ➤Multilist ➤Stack ➤Queue ➤Tree ➤Graph Penasaran dengan pengertian list yang saya tulis di atas? TENANG  Saya su...
Baca selengkapnya
Gambar
Hashing Table dan Binary Tree H ashing Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel. Contoh perintah pada Hashing Table ➤  insert:             diberikan sebuah key dan nilai, insert nilai dalam tabel ➤  find:                diberikan sebuah key, temukan nilai yang berhubungan dengan key ➤  remove:          diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut ➤  getIterator:     mengambalikan iterator,yang memeriksa nilai satu demi satu Hash table menggunakan struktur data array asosiatif yang mengasosiasikan record dengan sebuah field kunci unik berupa bilangan (hash) yang merupakan representasi dari r...
Baca selengkapnya