АВЛ дрвеће: ротације, уметање, брисање са примером Ц ++

Шта су АВЛ дрвеће?

АВЛ дрвеће су бинарна стабла претраживања у којима је разлика између висине левог и десног подстабла или -1, 0 или +1.

АВЛ стабла се називају и самобалансирајуће бинарно стабло претраживања. Ова стабла помажу у одржавању логаритамског времена претраживања. Име је добио по својим проналазачима (АВЛ) Аделсон, Велски и Ландис.

У овом упутству о алгоритму ћете научити:

Како ради АВЛ дрво?

Да бисмо боље разумели потребу за АВЛ стаблима, погледајмо неке недостатке једноставних бинарних стабала претраживања.

Размотрите следеће кључеве уметнуте одређеним редоследом у бинарно стабло претраживања.

Визуелизација АВЛ стабла



где пронаћи избрисане фотографије на андроиду

Висина стабла линеарно расте по величини када убацујемо кључеве по растућем редоследу њихове вредности. Дакле, операција претраживања, у најгорем случају, узима О (н).

За тражење елемента потребно је линеарно време; стога нема сврхе користити структуру бинарног стабла претраживања. С друге стране, ако је висина дрвета уравнотежена, добијамо боље време за претраживање.

Погледајмо сада исте кључеве, али уметнуте различитим редоследом.

Овде су кључеви исти, али пошто су уметнути различитим редоследом, заузимају различите положаје, а висина стабла остаје уравнотежена. Стога претрага неће узети више од О (лог н) за било који елемент стабла. Сада је евидентно да ако се уметање изврши исправно, висина стабла може бити уравнотежена.

У АВЛ дрвећу проверавамо висину стабла током операције уметања. Измене су направљене да би се одржала уравнотежена висина без кршења основних својстава бинарног стабла претраживања.

Фактор равнотеже у АВЛ дрвећу

Фактор равнотеже (БФ) је основни атрибут сваког чвора у АВЛ стаблима који помаже у надгледању висине стабла.

Особине фактора биланса

АВЛ стабло фактора равнотеже

  • Фактор равнотеже познат је као разлика између висине левог подстабла и десног подстабла.
  • Фактор равнотеже (чвор) = висина (чвор-> лево)-висина (чвор-> десно)
  • Дозвољене вредности БФ су –1, 0 и +1.
  • Вредност –1 означава да лево подстабло садржи једно додатно, односно да је дрво остало тешко.
  • Вредност +1 означава да лево подстабло садржи једно додатно, односно да је дрво остало тешко.
  • Вредност 0 показује да стабло укључује једнаке чворове са сваке стране, односно да је дрво савршено уравнотежено.

АВЛ Ротације

Да би сам балансирао АВЛ Трее, приликом уметања или брисања чвора са стабла врше се ротације.

Изводимо следећу ротацију ЛЛ, ротацију РР, ротацију ЛР и ротацију РЛ.

  • Лефт - Лефт Ротатион
  • Десно - десно окретање
  • Ротација десно - лево
  • Лево - Десно Ротирање

Лефт - Лефт Ротатион

Ова ротација се изводи када се нови чвор уметне у лево подређено место левог подстабла.

АВЛ Трее Лефт - Лефт Ротатион



бесплатни програми за уређивање фотографија за рачунар

Изводи се једна десна ротација. Ова врста ротације се идентификује када чвор има уравнотежен фактор као +2, а његово лево дете има фактор равнотеже као +1.

Десно - десно окретање

Ова ротација се врши када се нови чвор уметне у десно дете десног подстабла.

Изводи се једно окретање улево. Ова врста ротације се идентификује када чвор има уравнотежен фактор као -2, а његово десно дете има фактор равнотеже као -1.

Ротација десно - лево

Ова ротација се изводи када се нови чвор уметне у десно дете левог подстабла.

Ова ротација се изводи када чвор има фактор равнотеже као –2, а његово десно дете има фактор равнотеже као +1.

Лево - Десно Ротирање

Ова ротација се изводи када се нови чвор уметне у десно дете левог подстабла.

Ова ротација се изводи када чвор има фактор равнотеже као +2, а његово десно дете има фактор равнотеже као -1.

Уметање у АВЛ дрвеће

Операција уметања је скоро иста као у једноставним бинарним стаблима претраживања. Након сваког уметања, балансирамо висину стабла. Операција уметања узима О (лог н) најгору сложеност времена.

Имплементација уметања АВЛ стабла

Корак 1 : Уметните чвор у АВЛ стабло користећи исти алгоритам за уметање као и БСТ. У горњем примеру уметните 160.

Корак 2 : Када се чвор дода, фактор равнотеже сваког чвора се ажурира. Након уметања 160, фактор равнотеже сваког чвора се ажурира.

Корак 3 : Сада проверите да ли неки чвор крши опсег фактора равнотеже ако је фактор равнотеже прекршен, а затим извршите ротације користећи доњи случај. У горњем примеру, фактор равнотеже од 350 је прекршен и случај 1 тамо постаје применљив, извршавамо ротацију ЛЛ и дрво се поново уравнотежује.

  1. Ако је БФ (чвор) = +2 и БФ (чвор -> лево -дете) = +1, изведите ЛЛ ротацију.
  2. Ако је БФ (чвор) = -2 и БФ (чвор -> десно дете) = 1, изведите РР ротацију.
  3. Ако је БФ (чвор) = -2 и БФ (чвор -> десно дете) = +1, изведите ротацију РЛ.
  4. Ако је БФ (чвор) = +2 и БФ (чвор -> леви подређени) = -1, изведите ЛР ротацију.

Брисање у АВЛ дрвећу

Брисање је такође врло једноставно. Бришемо користећи исту логику као у једноставним бинарним стаблима претраживања. Након брисања, дрво реструктурирамо, ако је потребно, како бисмо одржали уравнотежену висину.

Корак 1: Пронађите елемент у дрвету.

Корак 2: Избришите чвор, према БСТ брисању.

3. корак: Могућа су два случаја:-

Случај 1: Брисање са десног подстабла.

  • 1А. Ако је БФ (чвор) = +2 и БФ (чвор -> лево дете) = +1, изведите ротацију ЛЛ.
  • 1Б. Ако је БФ (чвор) = +2 и БФ (чвор -> леви подређени) = -1, изведите ЛР ротацију.
  • 1Ц. Ако је БФ (чвор) = +2 и БФ (чвор -> лево -дете) = 0, изведите ЛЛ ротацију.

Случај 2 : Брисање са левог подстабла.

  • 2А. Ако је БФ (чвор) = -2 и БФ (чвор -> десно дете) = -1, изведите РР ротацију.
  • 2Б. Ако је БФ (чвор) = -2 и БФ (чвор -> десно дете) = +1, изведите ротацију РЛ.
  • 2Ц. Ако је БФ (чвор) = -2 и БФ (чвор -> десно дете) = 0, изведите РР ротацију.

Ц ++ Пример АВЛ дрвећа

Испод је Ц ++ код који имплементира АВЛ стабла: | _+_ |

Покренути пример горњег кода:

  1. Копирајте горњи код и залепите у 'авл.цпп'.
  2. Саставите код:
 #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); } 
  1. Покрените код.
g++ avl.cpp -o run

Предности АВЛ дрвећа

  • Висина АВЛ стабла је увек уравнотежена. Висина никада не прелази лог Н, где је Н укупан број чворова у стаблу.
  • Омогућава бољу сложеност времена претраживања у поређењу са једноставним стаблима бинарне претраге.
  • АВЛ стабла имају способности самобалансирања.

Резиме:

  • АВЛ стабла су самобалансирајућа бинарна стабла претраживања.
  • Фактор равнотеже је основни атрибут АВЛ стабала
  • Фактор равнотеже чвора је дефинисан као разлика између висине левог и десног подстабла тог чвора.
  • Важеће вредности билансног фактора су -1, 0 и +1.
  • Операција уметања и брисања захтева ротацију након кршења фактора равнотеже.
  • Временска сложеност операције уметања, брисања и претраживања је О (дневник Н).
  • АВЛ стабла прате сва својства Бинари Сеарцх Треес.
  • Лево подстабло има чворове који су мањи од корена. Десно подстабло има чворове који су увек већи од корена.
  • АВЛ стабла се користе тамо где су операције претраживања чешће у поређењу са операцијама уметања и брисања.