Pokok AVL: Putaran, Penyisipan, Penghapusan dengan Contoh C ++

Apa itu Pokok AVL?

Pokok AVL adalah pokok carian binari di mana perbezaan antara ketinggian subtree kiri dan kanan sama ada -1, 0, atau +1.

Pokok AVL juga dipanggil pokok carian binari yang mengimbangkan diri. Pokok-pokok ini membantu mengekalkan masa pencarian logaritma. Ia dinamakan sempena penciptanya (AVL) Adelson, Velsky, dan Landis.

Dalam tutorial Algoritma ini, anda akan belajar:

Bagaimana AVL Tree berfungsi?

Untuk lebih memahami keperluan pokok AVL, marilah kita melihat beberapa kelemahan pokok carian binari sederhana.

Pertimbangkan kunci berikut yang disisipkan dalam urutan tertentu di pohon carian binari.

Visualisasi pokok AVL



periksa sama ada nombor adalah java perdana

Ketinggian pokok tumbuh dengan ukuran linier apabila kita memasukkan kunci mengikut urutan nilainya. Oleh itu, operasi carian, paling teruk, memerlukan O (n).

Ia memerlukan masa linear untuk mencari elemen; oleh itu tidak ada gunanya menggunakan struktur Binary Search Tree. Sebaliknya, jika ketinggian pokok seimbang, kita akan mendapat masa pencarian yang lebih baik.

Mari kita lihat kunci yang sama tetapi dimasukkan dalam urutan yang berbeza.

Di sini, kuncinya sama, tetapi kerana dimasukkan dalam urutan yang berbeza, mereka mengambil kedudukan yang berbeza, dan ketinggian pokok tetap seimbang. Oleh itu carian tidak akan memerlukan lebih daripada O (log n) untuk unsur pokok. Sekarang terbukti bahawa jika penyisipan dilakukan dengan betul, ketinggian pokok dapat dijaga seimbang.

Di pokok AVL, kami memerhatikan ketinggian pokok semasa operasi penyisipan. Pengubahsuaian dilakukan untuk mengekalkan ketinggian yang seimbang tanpa melanggar sifat asas Binary Search Tree.

Faktor Imbangan dalam Pokok AVL

Faktor keseimbangan (BF) adalah atribut asas setiap nod di pokok AVL yang membantu memantau ketinggian pokok.

Sifat Faktor Imbangan

Pokok AVL faktor keseimbangan

  • Faktor keseimbangan dikenali sebagai perbezaan antara ketinggian subtree kiri dan subtree kanan.
  • Faktor keseimbangan (node) = tinggi (simpul-> kiri) - tinggi (simpul-> kanan)
  • Nilai BF yang dibenarkan ialah –1, 0, dan +1.
  • Nilai –1 menunjukkan bahawa sub-pokok kiri mengandungi satu tambahan, iaitu, pokok dibiarkan berat.
  • Nilai +1 menunjukkan bahawa sub-pokok kiri mengandungi satu tambahan, iaitu, pokok dibiarkan berat.
  • Nilai 0 menunjukkan bahawa pokok merangkumi nod yang sama di setiap sisi, iaitu, pokok itu seimbang dengan sempurna.

Putaran AVL

Untuk membuat keseimbangan Pokok AVL itu sendiri, semasa memasukkan atau menghapus nod dari pokok, putaran dilakukan.

Kami melakukan putaran LL, putaran RR, putaran LR, dan putaran RL berikut.

  • Putaran Kiri - Kiri
  • Putaran Kanan - Kanan
  • Putaran Kanan - Kiri
  • Putaran Kiri - Kanan

Putaran Kiri - Kiri

Putaran ini dilakukan apabila simpul baru dimasukkan ke anak kiri subtree kiri.

Pokok AVL Kiri - Putaran Kiri



cari indeks nilai dalam senarai python

Putaran kanan tunggal dilakukan. Jenis putaran ini dikenal pasti apabila simpul mempunyai faktor seimbang sebagai +2, dan anak kirinya mempunyai faktor keseimbangan sebagai +1.

Putaran Kanan - Kanan

Putaran ini dilakukan apabila simpul baru dimasukkan ke anak kanan subtree kanan.

Putaran kiri tunggal dilakukan. Jenis putaran ini dikenal pasti apabila simpul mempunyai faktor seimbang sebagai -2, dan anak kanannya mempunyai faktor keseimbangan sebagai -1.

Putaran Kanan - Kiri

Putaran ini dilakukan apabila simpul baru dimasukkan ke anak kanan subtree kiri.

Putaran ini dilakukan apabila simpul mempunyai faktor keseimbangan sebagai –2, dan anak kanannya mempunyai faktor keseimbangan sebagai +1.

Putaran Kiri - Kanan

Putaran ini dilakukan apabila simpul baru dimasukkan ke anak kanan subtree kiri.

Putaran ini dilakukan apabila nod mempunyai faktor keseimbangan sebagai +2, dan anak kanannya mempunyai faktor keseimbangan sebagai -1.

Penyisipan di Pokok AVL

Operasi sisipan hampir sama seperti pada pokok carian binari sederhana. Selepas setiap penyisipan, kami mengimbangkan ketinggian pokok. Operasi sisipan memerlukan kerumitan masa terburuk O (log n).

Pelaksanaan penyisipan pokok AVL

Langkah 1 : Masukkan node di pohon AVL menggunakan algoritma penyisipan BST yang sama. Dalam contoh di atas, masukkan 160.

Langkah 2 : Setelah node ditambahkan, faktor keseimbangan setiap nod dikemas kini. Setelah 160 dimasukkan, faktor keseimbangan setiap nod dikemas kini.

Langkah 3 : Sekarang periksa apakah ada simpul yang melanggar julat faktor keseimbangan jika faktor keseimbangan dilanggar, kemudian lakukan putaran menggunakan casing di bawah. Dalam contoh di atas, faktor keseimbangan 350 dilanggar dan kes 1 berlaku di sana, kami melakukan putaran LL dan pokoknya kembali seimbang.

  1. Sekiranya BF (node) = +2 dan BF (simpul -> kiri-anak) = +1, lakukan putaran LL.
  2. Sekiranya BF (node) = -2 dan BF (node ​​-> kanan-anak) = 1, lakukan putaran RR.
  3. Sekiranya BF (node) = -2 dan BF (simpul -> kanan-anak) = +1, lakukan putaran RL.
  4. Sekiranya BF (node) = +2 dan BF (simpul -> kiri-anak) = -1, lakukan putaran LR.

Penghapusan di Pokok AVL

Penghapusan juga sangat lurus ke hadapan. Kami memadam menggunakan logik yang sama seperti pada pokok carian binari sederhana. Selepas penghapusan, kami menyusun semula pokok, jika diperlukan, untuk mengekalkan ketinggiannya yang seimbang.

Langkah 1: Cari unsur di pokok.

Langkah 2: Padamkan simpul, seperti dalam Penghapusan BST.

Langkah 3: Dua kes mungkin: -

Kes 1: Memadam dari subtree yang betul.

  • 1A. Sekiranya BF (node) = +2 dan BF (simpul -> kiri-anak) = +1, lakukan putaran LL.
  • 1B. Sekiranya BF (node) = +2 dan BF (simpul -> kiri-anak) = -1, lakukan putaran LR.
  • 1C. Sekiranya BF (node) = +2 dan BF (simpul -> kiri-anak) = 0, lakukan putaran LL.

Kes 2 : Memadam dari subtree kiri.

  • 2A. Sekiranya BF (node) = -2 dan BF (node ​​-> kanan-anak) = -1, lakukan putaran RR.
  • 2B. Sekiranya BF (node) = -2 dan BF (simpul -> kanan-anak) = +1, lakukan putaran RL.
  • 2C. Sekiranya BF (node) = -2 dan BF (node ​​-> kanan-anak) = 0, lakukan putaran RR.

C ++ Contoh Pokok AVL

Berikut adalah kod C ++ yang menerapkan pokok AVL:

 #include #include #include 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 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 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<<'
'<<'Empty tree'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 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<<'
1.Display levelorder on newline'; cout<<'
2.Insert'; cout<<'
3.Delete
'; cout<<'
0.Exit
'; cout<>c; switch (c) { case 1: b.levelorder_newline(); // to print the tree in level order break; case 2: cout<>x; b.root = b.insert(b.root,x); break; case 3: cout<>x; b.root = b.deleteNode(b.root,x); break; case 0: break; } } while(c!=0); } 

Contoh menjalankan kod di atas:

  1. Salin kod di atas dan tampal di 'avl.cpp'.
  2. Kumpulkan kod:
g++ avl.cpp -o run
  1. Jalankan kod.
./run 

Kelebihan Pokok AVL

  • Ketinggian pokok AVL sentiasa seimbang. Ketinggian tidak pernah tumbuh melebihi log N, di mana N adalah jumlah nod di pokok.
  • Ini memberikan kerumitan masa carian yang lebih baik jika dibandingkan dengan pokok Carian Binari sederhana.
  • Pokok AVL mempunyai kemampuan mengimbangkan diri.

Ringkasan:

  • Pokok AVL adalah pokok carian binari yang mengimbangkan diri.
  • Faktor keseimbangan adalah sifat asas pokok AVL
  • Faktor keseimbangan nod ditakrifkan sebagai perbezaan antara ketinggian subtree kiri dan kanan nod tersebut.
  • Nilai sah faktor keseimbangan adalah -1, 0, dan +1.
  • Operasi memasukkan dan menghapus memerlukan putaran dilakukan setelah melanggar faktor keseimbangan.
  • Kerumitan masa operasi memasukkan, hapus, dan carian adalah O (log N).
  • Pokok AVL mengikuti semua sifat Binary Search Pohon.
  • Subtree kiri mempunyai nod yang lebih rendah daripada nod akar. Subtree kanan mempunyai node yang selalu lebih besar daripada simpul root.
  • Pokok AVL digunakan di mana operasi carian lebih kerap dibandingkan dengan operasi memasukkan dan memadam.