Pohon AVL: Rotasi, Penyisipan, Penghapusan dengan C++ Example
Sarah Chen
Apa itu Pohon AVL?
pohon AVL adalah pohon pencarian biner yang selisih tinggi subpohon kiri dan kanannya adalah -1, 0, atau +1.
Pohon AVL juga disebut pohon pencarian biner yang menyeimbangkan diri. Pohon-pohon ini membantu mempertahankan waktu pencarian logaritmik. Namanya diambil dari nama penemunya (AVL) Adelson, Velsky, dan Landis.
Bagaimana cara kerja Pohon AVL?
Untuk lebih memahami kebutuhan pohon AVL, mari kita lihat beberapa kelemahan pohon pencarian biner sederhana.
Pertimbangkan kunci berikut yang dimasukkan dalam urutan yang diberikan di pohon pencarian biner.
Tinggi pohon bertambah secara linear saat kita memasukkan kunci dalam urutan peningkatan nilai. Jadi, operasi pencarian, paling buruk, membutuhkan O(n).
Dibutuhkan waktu linier untuk mencari suatu elemen; maka tidak ada gunanya menggunakan Pohon Pencarian Biner struktur. Di sisi lain, jika tinggi pohon seimbang, kita mendapatkan waktu pencarian yang lebih baik.
Sekarang mari kita lihat kunci yang sama tetapi disisipkan dalam urutan yang berbeda.
Di sini, kuncinya sama, tetapi karena dimasukkan dalam urutan yang berbeda, posisi kuncinya berbeda, dan ketinggian pohon tetap seimbang. Oleh karena itu pencarian tidak akan memakan waktu lebih dari O(log n) untuk setiap elemen pohon. Kini terbukti bahwa jika penyisipan dilakukan dengan benar, tinggi pohon dapat tetap seimbang.
Pada pohon AVL, kami terus memeriksa tinggi pohon selama operasi penyisipan. Modifikasi dilakukan untuk mempertahankan tinggi yang seimbang tanpa melanggar sifat dasar Pohon Pencarian Biner.
Faktor Keseimbangan di Pohon AVL
Faktor keseimbangan (BF) adalah atribut fundamental dari setiap node di pohon AVL yang membantu memantau ketinggian pohon.
Sifat Faktor Keseimbangan
- Faktor keseimbangan disebut selisih tinggi subpohon kiri dan subpohon kanan.
- Faktor keseimbangan(simpul) = tinggi(simpul->kiri) – tinggi(simpul->kanan)
- Nilai BF yang diperbolehkan adalah –1, 0, dan +1.
- Nilai –1 menunjukkan bahwa subpohon sebelah kanan mengandung satu tambahan, yaitu pohon tersebut mempunyai berat yang tepat.
- Nilai +1 menunjukkan bahwa sub-pohon kiri mengandung satu tambahan, yaitu pohon dibiarkan berat.
- Nilai 0 menunjukkan bahwa pohon tersebut memiliki simpul-simpul yang sama pada setiap sisinya, yaitu pohon tersebut seimbang sempurna.
Rotasi AVL
Untuk membuat Pohon AVL menyeimbangkan dirinya sendiri, saat menyisipkan atau menghapus node dari pohon, dilakukan rotasi.
Kami melakukan rotasi LL, rotasi RR, rotasi LR, dan rotasi RL berikut.
- Kiri – Rotasi Kiri
- Kanan – Rotasi Kanan
- Rotasi Kanan – Kiri
- Rotasi Kiri – Kanan
Kiri – Rotasi Kiri
Rotasi ini dilakukan ketika node baru disisipkan pada anak kiri dari subpohon kiri.
Rotasi kanan tunggal dilakukan. Jenis rotasi ini diidentifikasi ketika sebuah node mempunyai faktor keseimbangan +2, dan anak kirinya mempunyai faktor keseimbangan +1.
Kanan – Rotasi Kanan
Rotasi ini dilakukan ketika node baru disisipkan pada anak kanan dari subpohon kanan.
Satu putaran ke kiri dilakukan. Jenis rotasi ini diidentifikasi ketika sebuah node mempunyai faktor seimbang sebesar -2, dan anak kanannya memiliki faktor keseimbangan sebesar -1.
Rotasi Kanan – Kiri
Rotasi ini dilakukan ketika node baru disisipkan pada anak kanan dari subpohon kiri.
Rotasi ini dilakukan ketika sebuah node memiliki faktor keseimbangan –2, dan anak kanannya memiliki faktor keseimbangan +1.
Rotasi Kiri – Kanan
Rotasi ini dilakukan ketika node baru disisipkan pada anak kiri dari subpohon kanan.
Rotasi ini dilakukan ketika sebuah node memiliki faktor keseimbangan +2, dan anak kirinya memiliki faktor keseimbangan -1.
Penyisipan di Pohon AVL
Operasi penyisipan hampir sama seperti pada pohon pencarian biner sederhana. Setelah setiap penyisipan, kami menyeimbangkan tinggi pohon. Operasi penyisipan membutuhkan kompleksitas waktu terburuk O(log n).
Langkah 1: Masukkan node ke dalam pohon AVL menggunakan algoritma penyisipan yang sama dengan BST. Dalam contoh di atas, masukkan 160.
Langkah 2: Setelah node ditambahkan, faktor keseimbangan setiap node diperbarui. Setelah 160 dimasukkan, faktor keseimbangan setiap node diperbarui.
Langkah 3: Sekarang periksa apakah ada node yang melanggar kisaran faktor keseimbangan jika faktor keseimbangan dilanggar, kemudian lakukan rotasi menggunakan kasus di bawah ini. Dalam contoh di atas, faktor keseimbangan 350 dilanggar dan kasus 1 berlaku di sana, kita melakukan rotasi LL dan pohon diseimbangkan kembali.
- Jika BF(node) = +2 dan BF(node -> left-child) = +1, lakukan rotasi LL.
- Jika BF(node) = -2 dan BF(node -> right-child) = 1, lakukan rotasi RR.
- Jika BF(node) = -2 dan BF(node -> right-child) = +1, lakukan rotasi RL.
- Jika BF(node) = +2 dan BF(node -> left-child) = -1, lakukan rotasi LR.
Penghapusan di Pohon AVL
Penghapusan juga sangat mudah. Kami menghapus menggunakan logika yang sama seperti pada pohon pencarian biner sederhana. Setelah penghapusan, kami merestrukturisasi pohon, jika diperlukan, untuk menjaga keseimbangan ketinggiannya.
Langkah 1: Temukan elemen di pohon.
Langkah 2: Hapus node, sesuai Penghapusan BST.
Langkah 3: Dua kasus mungkin terjadi: -
Kasus 1: Menghapus dari subpohon kanan.
- 1A. Jika BF(node) = +2 dan BF(node -> left-child) = +1, lakukan rotasi LL.
- 1B. Jika BF(node) = +2 dan BF(node -> left-child) = -1, lakukan rotasi LR.
- 1C. Jika BF(node) = +2 dan BF(node -> left-child) = 0, lakukan rotasi LL.
Kasus 2: Menghapus dari subpohon kiri.
- 2A. Jika BF(node) = -2 dan BF(node -> right-child) = -1, lakukan rotasi RR.
- 2B. Jika BF(node) = -2 dan BF(node -> right-child) = +1, lakukan rotasi RL.
- 2C. Jika BF(node) = -2 dan BF(node -> right-child) = 0, lakukan rotasi RR.
C++ Contoh Pohon AVL
Di bawah ini adalah C++ yang mengimplementasikan pohon AVL:
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
struct node {
struct node *left;
int data;
int height;
struct node *right;
};
class AVL
{
private:
public:
struct node * root;
AVL(){
this->root = NULL;
}
int calheight(struct node *p){
if(p->left && p->right){
if (p->left->height < p->right->height)
return p->right->height + 1;
else return p->left->height + 1;
}
else if(p->left && p->right == NULL){
return p->left->height + 1;
}
else if(p->left ==NULL && p->right){
return p->right->height + 1;
}
return 0;
}
int bf(struct node *n){
if(n->left && n->right){
return n->left->height - n->right->height;
}
else if(n->left && n->right == NULL){
return n->left->height;
}
else if(n->left== NULL && n->right ){
return -n->right->height;
}
}
struct node * llrotation(struct node *n){
struct node *p;
struct node *tp;
p = n;
tp = p->left;
p->left = tp->right;
tp->right = p;
return tp;
}
struct node * rrrotation(struct node *n){
struct node *p;
struct node *tp;
p = n;
tp = p->right;
p->right = tp->left;
tp->left = p;
return tp;
}
struct node * rlrotation(struct node *n){
struct node *p;
struct node *tp;
struct node *tp2;
p = n;
tp = p->right;
tp2 =p->right->left;
p -> right = tp2->left;
tp ->left = tp2->right;
tp2 ->left = p;
tp2->right = tp;
return tp2;
}
struct node * lrrotation(struct node *n){
struct node *p;
struct node *tp;
struct node *tp2;
p = n;
tp = p->left;
tp2 =p->left->right;
p -> left = tp2->right;
tp ->right = tp2->left;
tp2 ->right = p;
tp2->left = tp;
return tp2;
}
struct node* insert(struct node *r,int data){
if(r==NULL){
struct node *n;
n = new struct node;
n->data = data;
r = n;
r->left = r->right = NULL;
r->height = 1;
return r;
}
else{
if(data < r->data)
r->left = insert(r->left,data);
else
r->right = insert(r->right,data);
}
r->height = calheight(r);
if(bf(r)==2 && bf(r->left)==1){
r = llrotation(r);
}
else if(bf(r)==-2 && bf(r->right)==-1){
r = rrrotation(r);
}
else if(bf(r)==-2 && bf(r->right)==1){
r = rlrotation(r);
}
else if(bf(r)==2 && bf(r->left)==-1){
r = lrrotation(r);
}
return r;
}
void levelorder_newline(){
if (this->root == NULL){
cout<<"\n"<<"Empty tree"<<"\n";
return;
}
levelorder_newline(this->root);
}
void levelorder_newline(struct node *v){
queue <struct node *> q;
struct node *cur;
q.push(v);
q.push(NULL);
while(!q.empty()){
cur = q.front();
q.pop();
if(cur == NULL && q.size()!=0){
cout<<"\n";
q.push(NULL);
continue;
}
if(cur!=NULL){
cout<<" "<<cur->data;
if (cur->left!=NULL){
q.push(cur->left);
}
if (cur->right!=NULL){
q.push(cur->right);
}
}
}
}
struct node * deleteNode(struct node *p,int data){
if(p->left == NULL && p->right == NULL){
if(p==this->root)
this->root = NULL;
delete p;
return NULL;
}
struct node *t;
struct node *q;
if(p->data < data){
p->right = deleteNode(p->right,data);
}
else if(p->data > data){
p->left = deleteNode(p->left,data);
}
else{
if(p->left != NULL){
q = inpre(p->left);
p->data = q->data;
p->left=deleteNode(p->left,q->data);
}
else{
q = insuc(p->right);
p->data = q->data;
p->right = deleteNode(p->right,q->data);
}
}
if(bf(p)==2 && bf(p->left)==1){ p = llrotation(p); }
else if(bf(p)==2 && bf(p->left)==-1){ p = lrrotation(p); }
else if(bf(p)==2 && bf(p->left)==0){ p = llrotation(p); }
else if(bf(p)==-2 && bf(p->right)==-1){ p = rrrotation(p); }
else if(bf(p)==-2 && bf(p->right)==1){ p = rlrotation(p); }
else if(bf(p)==-2 && bf(p->right)==0){ p = llrotation(p); }
return p;
}
struct node* inpre(struct node* p){
while(p->right!=NULL)
p = p->right;
return p;
}
struct node* insuc(struct node* p){
while(p->left!=NULL)
p = p->left;
return p;
}
~AVL(){
}
};
int main(){
AVL b;
int c,x;
do{
cout<<"\n1.Display levelorder on newline";
cout<<"\n2.Insert";
cout<<"\n3.Delete\n";
cout<<"\n0.Exit\n";
cout<<"\nChoice: ";
cin>>c;
switch (c)
{
case 1:
b.levelorder_newline();
// to print the tree in level order
break;
case 2:
cout<<"\nEnter no. ";
cin>>x;
b.root = b.insert(b.root,x);
break;
case 3:
cout<<"\nWhat to delete? ";
cin>>x;
b.root = b.deleteNode(b.root,x);
break;
case 0:
break;
}
} while(c!=0);
}
Contoh menjalankan kode di atas:
- Salin kode di atas dan tempel di “avl.cpp”.
- Kompilasi kode:
g++ avl.cpp -o run
- Jalankan kodenya.
./run
Keuntungan Pohon AVL
- Ketinggian pohon AVL selalu seimbang. Tingginya tidak pernah melebihi log N, di mana N adalah jumlah total node di pohon.
- Memberikan kompleksitas waktu pencarian yang lebih baik jika dibandingkan dengan pohon Pencarian Biner sederhana.
- Pohon AVL memiliki kemampuan menyeimbangkan diri.
Ringkasan
- Pohon AVL adalah pohon pencarian biner yang menyeimbangkan dirinya sendiri.
- Faktor keseimbangan adalah atribut fundamental dari pohon AVL
- Faktor keseimbangan suatu simpul didefinisikan sebagai selisih antara tinggi subpohon kiri dan kanan simpul tersebut.
- Nilai faktor keseimbangan yang valid adalah -1, 0, dan +1.
- Operasi penyisipan dan penghapusan memerlukan rotasi yang dilakukan setelah melanggar faktor keseimbangan.
- Kompleksitas waktu dari operasi penyisipan, penghapusan, dan pencarian adalah O(log N).
- Pohon AVL mengikuti semua properti Pohon Pencarian Biner.
- Subpohon kiri mempunyai simpul yang lebih kecil dari simpul akar. Subpohon sebelah kanan mempunyai simpul yang selalu lebih besar dari simpul akar.
- Pohon AVL digunakan di mana operasi pencarian lebih sering terjadi dibandingkan dengan operasi penyisipan dan penghapusan.
