AVL वृक्ष: घूर्णन, सम्मिलन, विलोपन C++ उदाहरण
सारा चेन
AVL वृक्ष क्या हैं?
एवीएल वृक्ष बाइनरी सर्च वृक्ष हैं जिनमें बाएं और दाएं उपवृक्ष की ऊंचाई के बीच का अंतर -1, 0, या +1 होता है।
AVL ट्री को सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री भी कहा जाता है। ये ट्री लॉगरिदमिक सर्च टाइम को बनाए रखने में मदद करते हैं। इसका नाम इसके आविष्कारकों (AVL) एडेलसन, वेल्स्की और लैंडिस के नाम पर रखा गया है।
AVL ट्री कैसे काम करता है?
AVL वृक्षों की आवश्यकता को बेहतर ढंग से समझने के लिए, आइए सरल बाइनरी सर्च वृक्षों के कुछ नुकसानों पर नजर डालें।
बाइनरी सर्च ट्री में दिए गए क्रम में डाली गई निम्नलिखित कुंजियों पर विचार करें।
जब हम कुंजियों को उनके मान के बढ़ते क्रम में डालते हैं तो पेड़ की ऊंचाई आकार में रैखिक रूप से बढ़ती है। इस प्रकार, खोज ऑपरेशन, सबसे खराब स्थिति में, O(n) लेता है।
किसी तत्व की खोज में रैखिक समय लगता है; इसलिए इसका उपयोग करने का कोई फायदा नहीं है। बाइनरी सर्च ट्री दूसरी ओर, यदि पेड़ की ऊंचाई संतुलित है, तो हमें बेहतर खोज समय मिलता है।
आइए अब उन्हीं कुंजियों पर नजर डालें, लेकिन उन्हें अलग क्रम में डाला गया है।
यहाँ, कुंजियाँ एक जैसी हैं, लेकिन चूँकि उन्हें अलग-अलग क्रम में डाला जाता है, इसलिए वे अलग-अलग स्थान लेती हैं, और पेड़ की ऊँचाई संतुलित रहती है। इसलिए पेड़ के किसी भी तत्व के लिए खोज O(log n) से अधिक नहीं लेगी। अब यह स्पष्ट है कि यदि प्रविष्टि सही ढंग से की जाती है, तो पेड़ की ऊँचाई को संतुलित रखा जा सकता है।
AVL ट्री में, हम इंसर्शन ऑपरेशन के दौरान पेड़ की ऊंचाई पर नज़र रखते हैं। बाइनरी सर्च ट्री के मूल गुणों का उल्लंघन किए बिना संतुलित ऊंचाई बनाए रखने के लिए संशोधन किए जाते हैं।
AVL वृक्षों में संतुलन कारक
संतुलन कारक (BF) AVL वृक्षों में प्रत्येक नोड का एक मूलभूत गुण है जो वृक्ष की ऊंचाई पर नजर रखने में मदद करता है।
बैलेंस फैक्टर के गुण
- संतुलन कारक को बाएं उपवृक्ष और दाएं उपवृक्ष की ऊंचाई के बीच के अंतर के रूप में जाना जाता है।
- संतुलन कारक (नोड) = ऊंचाई (नोड->बाएं) - ऊंचाई (नोड->दाएं)
- BF के स्वीकृत मान -1, 0, और +1 हैं।
- मान -1 यह दर्शाता है कि दाएँ उप-वृक्ष में एक अतिरिक्त है, अर्थात वृक्ष दाएँ ओर भारी है।
- मान +1 यह दर्शाता है कि बाएं उप-वृक्ष में एक अतिरिक्त है, अर्थात, वृक्ष भारी रह गया है।
- मान 0 यह दर्शाता है कि वृक्ष में प्रत्येक तरफ समान नोड शामिल हैं, अर्थात वृक्ष पूरी तरह से संतुलित है।
एवीएल रोटेशन
AVL वृक्ष को संतुलित रखने के लिए, वृक्ष में नोड डालते या हटाते समय, रोटेशन किया जाता है।
हम निम्नलिखित एलएल रोटेशन, आरआर रोटेशन, एलआर रोटेशन और आरएल रोटेशन करते हैं।
- बायाँ – बायाँ घुमाव
- दायाँ-दायाँ घुमाव
- दायाँ-बायाँ घुमाव
- बाएँ-दाएँ घुमाव
बायाँ – बायाँ घुमाव
यह रोटेशन तब किया जाता है जब बाएं उपवृक्ष के बाएं संतान में एक नया नोड डाला जाता है।
एक एकल दायाँ घुमाव किया जाता है। इस प्रकार के घुमाव की पहचान तब की जाती है जब किसी नोड का संतुलित कारक +2 होता है, और उसके बाएँ-बच्चे का संतुलन कारक +1 होता है।
दायाँ-दायाँ घुमाव
यह रोटेशन तब किया जाता है जब दाएं उपवृक्ष के दाएं संतान में एक नया नोड डाला जाता है।
एक एकल बायाँ घुमाव किया जाता है। इस प्रकार के घुमाव की पहचान तब की जाती है जब किसी नोड का संतुलित कारक -2 होता है, और उसके दाएँ-बच्चे का संतुलन कारक -1 होता है।
दायाँ-बायाँ घुमाव
यह रोटेशन तब किया जाता है जब बाएं उपवृक्ष के दाएं संतान में एक नया नोड डाला जाता है।
यह रोटेशन तब किया जाता है जब किसी नोड का संतुलन कारक -2 होता है, और उसके दाएं बच्चे का संतुलन कारक +1 होता है।
बाएँ-दाएँ घुमाव
यह रोटेशन तब किया जाता है जब दाएं उपवृक्ष के बाएं संतान में एक नया नोड डाला जाता है।
यह रोटेशन तब किया जाता है जब किसी नोड का संतुलन कारक +2 होता है, और उसके बाएं बच्चे का संतुलन कारक -1 होता है।
AVL वृक्षों में सम्मिलन
इन्सर्ट ऑपरेशन लगभग साधारण बाइनरी सर्च ट्री जैसा ही है। हर इन्सर्ट के बाद, हम पेड़ की ऊंचाई को संतुलित करते हैं। इन्सर्ट ऑपरेशन में O(log n) सबसे खराब समय जटिलता लगती है।
चरण 1: BST के समान प्रविष्टि एल्गोरिथ्म का उपयोग करके AVL ट्री में नोड डालें। उपरोक्त उदाहरण में, 160 डालें।
चरण 2: एक बार नोड जोड़ दिए जाने के बाद, प्रत्येक नोड का बैलेंस फैक्टर अपडेट हो जाता है। 160 डालने के बाद, प्रत्येक नोड का बैलेंस फैक्टर अपडेट हो जाता है।
चरण 3: अब जाँच करें कि क्या कोई नोड बैलेंस फैक्टर की सीमा का उल्लंघन करता है यदि बैलेंस फैक्टर का उल्लंघन होता है, तो नीचे दिए गए केस का उपयोग करके रोटेशन करें। उपरोक्त उदाहरण में, 350 के बैलेंस फैक्टर का उल्लंघन होता है और केस 1 वहाँ लागू होता है, हम LL रोटेशन करते हैं और पेड़ फिर से संतुलित हो जाता है।
- यदि BF(नोड) = +2 और BF(नोड -> बायां-चाइल्ड) = +1, तो LL रोटेशन निष्पादित करें।
- यदि BF(नोड) = -2 और BF(नोड -> दायां-चाइल्ड) = 1, तो RR रोटेशन निष्पादित करें।
- यदि BF(नोड) = -2 और BF(नोड -> दायां-चाइल्ड) = +1, तो RL रोटेशन निष्पादित करें।
- यदि BF(नोड) = +2 और BF(नोड -> बायां-चाइल्ड) = -1, तो LR रोटेशन निष्पादित करें।
AVL वृक्षों में विलोपन
हटाना भी बहुत सीधा है। हम सरल बाइनरी सर्च ट्री में इस्तेमाल किए जाने वाले समान तर्क का उपयोग करके हटाते हैं। हटाने के बाद, यदि आवश्यक हो, तो हम पेड़ की संतुलित ऊंचाई बनाए रखने के लिए उसका पुनर्गठन करते हैं।
चरण १: पेड़ में तत्व ढूंढें.
चरण १: बीएसटी विलोपन के अनुसार नोड को हटाएँ।
चरण १: दो स्थितियाँ सम्भव हैं:-
प्रकरण 1: दाएँ उपवृक्ष से हटाया जा रहा है.
- 1A. यदि BF(नोड) = +2 और BF(नोड -> बायाँ-चाइल्ड) = +1, तो LL रोटेशन करें।
- 1बी. यदि बीएफ(नोड) = +2 और बीएफ(नोड -> बायां-चाइल्ड) = -1, तो एलआर रोटेशन करें।
- 1C. यदि BF(नोड) = +2 और BF(नोड -> बायाँ-चाइल्ड) = 0, तो LL रोटेशन करें।
मामला 2: बाएं उपवृक्ष से हटाया जा रहा है.
- 2A. यदि BF(नोड) = -2 और BF(नोड -> दायाँ-चाइल्ड) = -1, तो RR रोटेशन करें।
- 2B. यदि BF(नोड) = -2 और BF(नोड -> दायाँ-चाइल्ड) = +1, तो RL रोटेशन करें।
- 2C. यदि BF(नोड) = -2 और BF(नोड -> दायाँ-चाइल्ड) = 0, तो RR रोटेशन करें।
C++ AVL वृक्षों का उदाहरण
नीचे है C++ जो 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);
}
उपरोक्त कोड का उदाहरण चल रहा है:
- उपरोक्त कोड को कॉपी करें और “avl.cpp” में पेस्ट करें।
- कोड संकलित करें:
g++ avl.cpp -o run
- कोड चलाएँ.
./run
एवीएल वृक्षों के लाभ
- AVL वृक्ष की ऊंचाई हमेशा संतुलित रहती है। ऊंचाई कभी भी लॉग एन से आगे नहीं बढ़ती, जहां एन वृक्ष में नोड्स की कुल संख्या है।
- सरल बाइनरी सर्च वृक्षों की तुलना में यह बेहतर खोज समय जटिलता देता है।
- AVL वृक्षों में आत्म-संतुलन क्षमताएं होती हैं।
सारांश
- AVL वृक्ष स्व-संतुलित बाइनरी खोज वृक्ष हैं।
- संतुलन कारक AVL वृक्षों का मूलभूत गुण है
- किसी नोड के संतुलन कारक को उस नोड के बाएं और दाएं उपवृक्ष की ऊंचाई के बीच के अंतर के रूप में परिभाषित किया जाता है।
- संतुलन कारक के मान्य मान -1, 0, और +1 हैं।
- सम्मिलित करने और हटाने के ऑपरेशन के लिए संतुलन कारक का उल्लंघन करने के बाद रोटेशन की आवश्यकता होती है।
- सम्मिलित करने, हटाने और खोजने के ऑपरेशन की समय जटिलता O(log N) है।
- AVL वृक्ष बाइनरी सर्च वृक्ष के सभी गुणों का पालन करते हैं।
- बाएं उपवृक्ष में ऐसे नोड होते हैं जो मूल नोड से छोटे होते हैं। दाएं उपवृक्ष में ऐसे नोड होते हैं जो हमेशा मूल नोड से बड़े होते हैं।
- AVL वृक्षों का उपयोग वहां किया जाता है जहां खोज ऑपरेशन, सम्मिलित करने और हटाने के ऑपरेशन की तुलना में अधिक बार किया जाता है।
