Christophorus Wilson 2301869273
AVL Tree adalah Binary Search Tree yang bentuknya lebih diseimbangkan. Dengan adanya AVL Tree, pencarian suatu data akan membutuhkan waktu yang lebih singkat.
Di dalam AVL Tree, terdapat istilah yang disebut balance factor. Balance factor adalah variabel yang berfungsi untuk mengecek apakah suatu bagian di AVL Tree telah seimbang atau belum. Cara mendapatkan balance factor adalah dengan mencari selisih kedalaman antara subtree kiri dan subtree kanan suatu node. Sebuah node dikatakan seimbang apabila balance factornya tidak lebih dari 1.
Berikut adalah contoh dari balance factor
Insertion
Operasi insertion pada AVL Tree dilakukan seperti pada BST biasa, namun akan ditambahkan function untuk menyeimbangkan AVL Tree nya.
Dalam
menyeimbangkan AVL Tree, terdapat 4 kemungkinan yang dapat terjadi. Misalkan
node yang akan diseimbangkan adalah X
1. Node terdalam berada di subtree kiri dari anak kiri node X.
2. Node terdalam berada di subtree kanan dari anak kanan node X.
3. Node terdalam berada di subtree kanan dari anak kiri node X.
4. Node terdalam berada di subtree kiri dari anak kanan node X.
Pada insertion, node terdalam adalah node yang akan dimasukkan.
Apabila
yang terjadi adalah kemungkinan 1 dan 2, cara menyeimbangkannya adalah dengan
melakukan single rotation.
Sedangkan bila yang terjadi adalah kemungkinan 3 dan 4, cara menyeimbangkannya adalah dengan melakukan double rotation.
Deletion
Operasi deletion pada AVL Tree juga pada dasarnya sama dengan BST, namun juga dibutuhkan function untuk menyeimbangkan AVL Tree tersebut.
AVL Tree adalah Binary Search Tree yang bentuknya lebih diseimbangkan. Dengan adanya AVL Tree, pencarian suatu data akan membutuhkan waktu yang lebih singkat.
Di dalam AVL Tree, terdapat istilah yang disebut balance factor. Balance factor adalah variabel yang berfungsi untuk mengecek apakah suatu bagian di AVL Tree telah seimbang atau belum. Cara mendapatkan balance factor adalah dengan mencari selisih kedalaman antara subtree kiri dan subtree kanan suatu node. Sebuah node dikatakan seimbang apabila balance factornya tidak lebih dari 1.
Berikut adalah contoh dari balance factor
Insertion
Operasi insertion pada AVL Tree dilakukan seperti pada BST biasa, namun akan ditambahkan function untuk menyeimbangkan AVL Tree nya.
1. Node terdalam berada di subtree kiri dari anak kiri node X.
2. Node terdalam berada di subtree kanan dari anak kanan node X.
3. Node terdalam berada di subtree kanan dari anak kiri node X.
4. Node terdalam berada di subtree kiri dari anak kanan node X.
Pada insertion, node terdalam adalah node yang akan dimasukkan.
Apabila
yang terjadi adalah kemungkinan 1 dan 2, cara menyeimbangkannya adalah dengan
melakukan single rotation.
Sedangkan bila yang terjadi adalah kemungkinan 3 dan 4, cara menyeimbangkannya adalah dengan melakukan double rotation.
Deletion
Operasi deletion pada AVL Tree juga pada dasarnya sama dengan BST, namun juga dibutuhkan function untuk menyeimbangkan AVL Tree tersebut.
Comments
Post a Comment