AVL tree adalah pohon pencarian biner di mana perbedaan ketinggian sub pohon kiri dan kanan dari setiap node kurang dari atau sama dengan satu. Teknik menyeimbangkan ketinggian pohon biner dikembangkan oleh Adelson, Velskii, dan Landi dan karenanya diberi bentuk singkat sebagai pohon AVL atau Pohon Biner Seimbang.
Pohon AVL dapat didefinisikan sebagai berikut:
Biarkan T menjadi pohon biner non-kosong dengan TL dan TR sebagai subtrees kiri dan kanannya. Pohon itu seimbang tinggi jika:
TL dan TR seimbang tinggi
hL - hR <= 1, di mana hL - hR adalah ketinggian TL dan TR
Faktor Keseimbangan dari sebuah simpul dalam pohon biner dapat memiliki nilai 1, -1, 0, tergantung pada apakah ketinggian subtree kirinya lebih besar, kurang dari atau sama dengan ketinggian subtree kanan.
Didefinisikan secara lebih implisit:
• Balance, yaitu –1, 0, atau +1, sama dengan ketinggian subtree kanan dikurangi ketinggian subtree kiri; jika keseimbangan –1, kita katakan pohon root pada anggota ini "berat kiri"; jika keseimbangan +1, pohonnya “berat kanan”;
• kiri, yang menunjuk ke anak kiri (atau nol jika tidak ada anak kiri);
• kanan , yang menunjuk ke anak yang kanan (atau nol jika tidak ada anak dikanan);
• induk, yang menunjuk ke induk (atau itu null kalau tidak ada induk, berarti node tersebut adadlah root untuk pohon tersebut).
Representasi AVL Tree dalam code :
Struct AVLNode
{
int data;
struct AVLNode *left, *right;
int balfactor;;
Operesai Dalam AVL Tree
Insertion
Langkah 1: Pertama, masukkan value baru ke pohon menggunakan logika penyisipan BST (Binary Search Tree).
Langkah 2: Setelah memasukkan value harus memeriksa Faktor Saldo dari setiap node.
Langkah 3: Ketika Balance Factor dari setiap node akan ditemukan seperti 0 atau 1 atau -1 maka algoritma akan melanjutkan untuk operasi selanjutnya.
Langkah 4: Ketika faktor keseimbangan dari node apapun datang selain dari ketiga value di atas maka pohon tersebut dikatakan tidak seimbang. Kemudian lakukan Rotasi yang sesuai untuk membuatnya seimbang dan kemudian algoritma akan melanjutkan untuk operasi selanjutnya.
Deletion
Langkah 1: Pertama, cari node value yang ada.
Langkah 2: hapus node tersebut (Misalkan nonde-nya adalah x)
Langkah 3: Menghapus node di pohon AVL dapat dihapus leaves-nya . Ada tiga kemungkinan kasus:
- Ketika x tidak memiliki anak, hapus x
- Ketika x memiliki satu anak, biarkan x 'menjadi anak dari x.
- Perhatikan: x 'tidak dapat memiliki anak, karena subtree T dapat dibedeakan dengan salah satu yang paling tinggi :
- lalu replace value x dengan isi x '
- lalu hapus x '(leeaves)
Langkah 4: Ketika x memiliki dua anak,
- kemudian temukan penggantti x (yang tidak memiliki anak kiri)
- lalu ganti value x-nya dengan value z-nya, dan hapus z
Dalam ketiga kasus tersebut, dapat menghapus (delete ) 1 node (leaf).
