أشجار AVL: التدوير والإدراج والحذف باستخدام مثال C++

ما هي أشجار AVL؟

أشجار AVL هي أشجار بحث ثنائية يكون فيها الفرق بين ارتفاع الشجرة الفرعية اليمنى واليسرى إما -1 أو 0 أو +1.

تُسمى أشجار AVL أيضًا بشجرة بحث ثنائية ذاتية التوازن. تساعد هذه الأشجار في الحفاظ على وقت البحث اللوغاريتمي. تم تسميته على اسم مخترعيه (AVL) أديلسون، فيلسكي، ولانديس.

كيف تعمل شجرة AVL؟

لفهم الحاجة إلى أشجار AVL بشكل أفضل، دعونا نلقي نظرة على بعض عيوب أشجار البحث الثنائية البسيطة.

خذ بعين الاعتبار ما يليwing تم إدراج المفاتيح بالترتيب المحدد في شجرة البحث الثنائية.


عمل شجرة AVL
تصور شجرة AVL

يزداد حجم الشجرة ارتفاعًا خطيًا عندما نقوم بإدخال المفاتيح بترتيب متزايد لقيمتها. وهكذا يكون البحث operaفي أسوأ الأحوال، يأخذ O(n).

يستغرق البحث عن عنصر وقتًا خطيًا؛ وبالتالي ليس هناك فائدة من استخدام شجرة البحث الثنائية بناء. ومن ناحية أخرى، إذا كان ارتفاع الشجرة متوازنا، فإننا نحصل على وضع أفضلarchiنانوغرام الوقت.

دعونا الآن نلقي نظرة على نفس المفاتيح ولكن تم إدخالها بترتيب مختلف.

عمل شجرة AVL

المفاتيح هنا هي نفسها، ولكن نظرًا لأنه تم إدخالها بترتيب مختلف، فإنها تتخذ مواضع مختلفة، ويظل ارتفاع الشجرة متوازنًا. ومن ثم فإن البحث لن يستغرق أكثر من O(log n) لأي عنصر من عناصر الشجرة. أصبح من الواضح الآن أنه إذا تم الإدراج بشكل صحيح، فيمكن الحفاظ على توازن ارتفاع الشجرة.

في أشجار AVL، نتحقق من ارتفاع الشجرة أثناء الإدراج operaنشوئها. تم إجراء التعديلات للحفاظ على الارتفاع المتوازن دون انتهاك الخصائص الأساسية لشجرة البحث الثنائية.

عامل التوازن في أشجار AVL

يعد عامل التوازن (BF) سمة أساسية لكل عقدة في أشجار AVL والتي تساعد في مراقبة ارتفاع الشجرة.

خصائص عامل التوازن


عامل التوازن في أشجار AVL

شجرة عامل التوازن AVL
  • يُعرف عامل التوازن بالفرق بين ارتفاع الشجرة الفرعية اليسرى والشجرة الفرعية اليمنى.
  • عامل التوازن (العقدة) = الارتفاع (العقدة->اليسار) - الارتفاع (العقدة->اليمين)
  • القيم المسموح بها لـ BF هي –1، 0، و+1.
  • تشير القيمة -1 إلى أن الشجرة الفرعية اليمنى تحتوي على شجرة إضافية واحدة، أي أن الشجرة ثقيلة جدًا.
  • تشير القيمة +1 إلى أن الشجرة الفرعية اليسرى تحتوي على شجرة إضافية واحدة، أي أن الشجرة تركت ثقيلة.
  • تشير القيمة 0 إلى أن الشجرة تتضمن عقدًا متساوية من كل جانب، أي أن الشجرة متوازنة تمامًا.

دورات AVL

لتحقيق التوازن في شجرة AVL نفسها، عند إدراج أو حذف عقدة من الشجرة، يتم إجراء عمليات التدوير.

نحن ننفذ ما يليwing دوران LL، دوران RR، دوران LR، ودوران RL.

  • اليسار - دوران اليسار
  • يمين - دوران يمين
  • اليمين - دوران اليسار
  • اليسار - دوران اليمين

اليسار - دوران اليسار

يتم إجراء هذا التدوير عند إدراج عقدة جديدة عند الفرع الفرعي الأيسر للشجرة الفرعية اليسرى.


شجرة AVL لليسار – الدوران لليسار

شجرة AVL لليسار – الدوران لليسار

يتم إجراء دوران يمين واحد. يتم تحديد هذا النوع من التدوير عندما يكون للعقدة عامل متوازن مثل +2، ويكون لدى فرعها الأيسر عامل توازن مثل +1.

يمين - دوران يمين

يتم تنفيذ هذا التدوير عند إدراج عقدة جديدة في الفرع الأيمن للشجرة الفرعية اليمنى.

شجرة AVL لليمين - التدوير لليمين

يتم تنفيذ دوران واحد لليسار. يتم تحديد هذا النوع من التدوير عندما يكون للعقدة عامل توازن هو -2، ويكون لفرعها الأيمن عامل توازن هو -1.

اليمين - دوران اليسار

يتم تنفيذ هذا التدوير عند إدراج عقدة جديدة عند الفرع الأيمن للشجرة الفرعية اليسرى.

شجرة AVL لليمين - الدوران لليسار

يتم تنفيذ هذا التدوير عندما يكون للعقدة عامل توازن يساوي -2، ويكون لفرعها الأيمن عامل توازن يساوي +1.

اليسار - دوران اليمين

يتم تنفيذ هذا التدوير عند إدراج عقدة جديدة عند الفرع الأيسر للشجرة الفرعية اليمنى.

شجرة AVL لليسار – الدوران لليمين

يتم تنفيذ هذا التدوير عندما يكون للعقدة عامل توازن يساوي +2، ويكون لدى فرعها الأيسر عامل توازن يساوي -1.

الإدراج في أشجار AVL

إدراج operaيكون الأمر مشابهًا تقريبًا كما هو الحال في أشجار البحث الثنائية البسيطة. بعد كل إدراج، نقوم بموازنة ارتفاع الشجرة. إدراج operaيستغرق tion O(log n) أسوأ وقت complexإيتي.


الإدراج في أشجار AVL

تنفيذ إدراج شجرة AVL

الخطوة الثانية: أدخل العقدة في شجرة AVL باستخدام نفس خوارزمية الإدراج الخاصة بـ BST. في المثال أعلاه، أدخل 160.

الخطوة الثانية: بمجرد إضافة العقدة، يتم تحديث عامل التوازن لكل عقدة. بعد إدراج 160، يتم تحديث عامل التوازن لكل عقدة.

الخطوة الثانية: تحقق الآن مما إذا كانت أي عقدة تنتهك نطاق عامل التوازن إذا تم انتهاك عامل التوازن، ثم قم بإجراء التدوير باستخدام الحالة أدناه. في المثال أعلاه، تم انتهاك عامل التوازن البالغ 350 وأصبحت الحالة 1 قابلة للتطبيق هناك، ونجري دوران LL وتتم موازنة الشجرة مرة أخرى.

  1. إذا كان BF(node) = +2 وBF(node ​​-> left-child) = +1، فقم بإجراء تدوير LL.
  2. إذا كانت BF(node) = -2 وBF(node ​​-> right-child) = 1، فقم بإجراء تدوير RR.
  3. إذا كان BF(node) = -2 وBF(node ​​-> right-child) = +1، فقم بإجراء تدوير RL.
  4. إذا كان BF(node) = +2 وBF(node ​​-> left-child) = -1، فقم بإجراء التدوير LR.

الحذف في أشجار AVL

الحذف هو أيضًا أمر مباشر جدًا. نقوم بالحذف باستخدام نفس المنطق كما هو الحال في أشجار البحث الثنائية البسيطة. بعد الحذف، نقوم بإعادة هيكلة الشجرة، إذا لزم الأمر، للحفاظ على ارتفاعها المتوازن.

خطوة 1 ابحث عن العنصر الموجود في الشجرة

خطوة 2 احذف العقدة، وفقًا لحذف BST.

خطوة 3 هناك حالتان محتملتان:-

حالة 1: الحذف من الشجرة الفرعية الصحيحة.

  • 1 أ. إذا كان BF(node) = +2 وBF(node ​​-> left-child) = +1، فقم بإجراء تدوير LL.
  • 1 ب. إذا كان BF(node) = +2 وBF(node ​​-> left-child) = -1، فقم بإجراء التدوير LR.
  • 1C. إذا كانت BF(node) = +2 وBF(node ​​-> left-child) = 0، فقم بإجراء التدوير LL.

الحذف في أشجار AVL

حالة 2: الحذف من الشجرة الفرعية اليسرى.

  • 2 أ. إذا كان BF(node) = -2 وBF(node ​​-> right-child) = -1، فقم بإجراء تدوير RR.
  • 2 ب. إذا كان BF(node) = -2 وBF(node ​​-> right-child) = +1، فقم بإجراء تدوير RL.
  • 2ج. إذا كانت BF(node) = -2 وBF(node ​​-> right-child) = 0، فقم بإجراء تدوير RR.

الحذف في أشجار AVL

مثال 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);
  
}

تشغيل مثال للكود أعلاه:

  1. انسخ الكود أعلاه والصقه في "avl.cpp".
  2. قم بتجميع الكود:
g++ avl.cpp -o run
  1. قم بتشغيل الكود.
./run

مثال C++ لأشجار AVL

مزايا أشجار AVL

  • يكون ارتفاع شجرة AVL متوازنًا دائمًا. لا يزيد الارتفاع أبدًا عن السجل N، حيث N هو إجمالي عدد العقد في الشجرة.
  • أنه يعطي وقت بحث أفضل كومplexity عند مقارنتها بأشجار البحث الثنائية البسيطة.
  • تتمتع أشجار AVL بقدرات التوازن الذاتي.

نبذة عامة

  • أشجار AVL هي أشجار بحث ثنائية ذاتية التوازن.
  • عامل التوازن هو السمة الأساسية لأشجار AVL
  • يتم تعريف عامل التوازن للعقدة على أنه الفرق بين ارتفاع الشجرة الفرعية اليسرى واليمنى لتلك العقدة.
  • القيم الصالحة لعامل التوازن هي -1 و0 و+1.
  • الإدراج والحذف operaتتطلب إجراء عمليات التدوير بعد انتهاك عامل التوازن.
  • الوقت كومplexإمكانية الإدراج والحذف والبحث operaنشوئها هو O (سجل N).
  • تتبع أشجار AVL جميع خصائص أشجار البحث الثنائية.
  • تحتوي الشجرة الفرعية اليسرى على عقد أقل من العقدة الجذرية. تحتوي الشجرة الفرعية اليمنى على عقد تكون دائمًا أكبر من العقدة الجذرية.
  • يتم استخدام أشجار AVL حيث يتم البحث operaيعتبر الأمر أكثر تكرارًا مقارنةً بالإدراج والحذف operaستعقد.