ต้นไม้ AVL: การหมุน การแทรก การลบด้วย C++ ตัวอย่าง

ต้นไม้ AVL คืออะไร?

ต้นไม้เอวีแอล เป็นแผนผังการค้นหาแบบไบนารีซึ่งความแตกต่างระหว่างความสูงของแผนผังย่อยด้านซ้ายและขวาเป็น -1, 0 หรือ +1

ต้นไม้ AVL เรียกอีกอย่างว่าแผนผังการค้นหาแบบไบนารีที่ปรับสมดุลในตัวเอง ต้นไม้เหล่านี้ช่วยรักษาเวลาในการค้นหาลอการิทึม ตั้งชื่อตามนักประดิษฐ์ (AVL) Adelson, Velsky และ Landis

AVL Tree ทำงานอย่างไร

เพื่อให้เข้าใจถึงความจำเป็นของแผนผัง AVL ได้ดีขึ้น เรามาดูข้อเสียบางประการของแผนผังการค้นหาแบบไบนารีอย่างง่ายกัน

พิจารณาคีย์ต่อไปนี้ที่ถูกแทรกตามลำดับที่กำหนดในต้นไม้การค้นหาแบบไบนารี

ความสูงของต้นไม้จะเพิ่มขึ้นแบบเชิงเส้นเมื่อเราใส่คีย์ตามลำดับค่าที่เพิ่มขึ้น ดังนั้น การค้นหาในกรณีที่แย่ที่สุดจะใช้ค่า O(n)

ต้องใช้เวลาเป็นเส้นตรงในการค้นหาองค์ประกอบ จึงไม่มีประโยชน์ในการใช้ ต้นไม้ค้นหาแบบไบนารี โครงสร้าง ในทางกลับกัน หากความสูงของต้นไม้สมดุล เราก็จะได้เวลาค้นหาที่ดีขึ้น

ตอนนี้เรามาดูคีย์เดียวกันแต่แทรกในลำดับที่ต่างกัน

ในกรณีนี้ กุญแจจะเหมือนกัน แต่เนื่องจากพวกมันถูกแทรกในลำดับที่ต่างกัน พวกมันจึงอยู่ในตำแหน่งที่แตกต่างกัน และความสูงของต้นไม้ยังคงสมดุล ดังนั้นการค้นหาจะใช้เวลาไม่เกิน O(log n) สำหรับองค์ประกอบใดๆ ของแผนผัง ปัจจุบันเห็นได้ชัดว่าหากแทรกอย่างถูกต้อง ความสูงของต้นไม้ก็จะสามารถรักษาสมดุลได้

ในต้นไม้ AVL เราจะตรวจสอบความสูงของต้นไม้ระหว่างการดำเนินการแทรก มีการปรับเปลี่ยนเพื่อรักษาความสูงที่สมดุลโดยไม่ละเมิดคุณสมบัติพื้นฐานของต้นไม้ค้นหาแบบไบนารี

ปัจจัยความสมดุลในต้นไม้ AVL

Balance Factor (BF) เป็นคุณลักษณะพื้นฐานของทุกโหนดในแผนผัง AVL ซึ่งช่วยในการตรวจสอบความสูงของแผนภูมิ

คุณสมบัติของตัวประกอบสมดุล

ปัจจัยความสมดุลในต้นไม้ AVL — ทรีสมดุลปัจจัย AVL

ปัจจัยความสมดุลเรียกว่าความแตกต่างระหว่างความสูงของแผนผังย่อยด้านซ้ายและแผนผังย่อยด้านขวา
ปัจจัยความสมดุล (โหนด) = ความสูง (โหนด -> ซ้าย) – ความสูง (โหนด -> ขวา)
ค่าที่อนุญาตของ BF คือ –1, 0 และ +1
ค่า –1 บ่งชี้ว่าแผนผังย่อยด้านขวามีรายการพิเศษอีกหนึ่งรายการ กล่าวคือ ต้นไม้มีน้ำหนักมาก
ค่า +1 บ่งชี้ว่าแผนผังย่อยด้านซ้ายมีรายการพิเศษรายการหนึ่ง กล่าวคือ ต้นไม้เหลือหนัก
ค่า 0 แสดงว่าต้นไม้มีโหนดเท่ากันในแต่ละด้าน กล่าวคือ ต้นไม้มีความสมดุลอย่างสมบูรณ์แบบ

การหมุน AVL

เพื่อให้ AVL Tree มีความสมดุล เมื่อมีการแทรกหรือลบโหนดออกจากแผนผัง การหมุนจะดำเนินการ

เราจะดำเนินการหมุน LL, หมุน RR, หมุน LR และหมุน RL ดังต่อไปนี้

ซ้าย – การหมุนซ้าย
ขวา - การหมุนขวา
หมุนขวา-ซ้าย
การหมุนซ้าย-ขวา

ซ้าย – การหมุนซ้าย

การหมุนนี้จะดำเนินการเมื่อมีการแทรกโหนดใหม่ที่ลูกด้านซ้ายของทรีย่อยด้านซ้าย

หมุนขวาเพียงครั้งเดียว การหมุนประเภทนี้จะถูกระบุเมื่อโหนดมีปัจจัยสมดุลเป็น +2 และลูกด้านซ้ายมีปัจจัยสมดุลเป็น +1

ขวา - การหมุนขวา

การหมุนนี้จะดำเนินการเมื่อมีการแทรกโหนดใหม่ที่ลูกด้านขวาของแผนผังย่อยด้านขวา

หมุนซ้ายเพียงครั้งเดียว การหมุนประเภทนี้จะถูกระบุเมื่อโหนดมีปัจจัยที่สมดุลเป็น -2 และลูกทางขวามีปัจจัยความสมดุลเป็น -1

หมุนขวา-ซ้าย

การหมุนนี้จะดำเนินการเมื่อมีการแทรกโหนดใหม่ที่ลูกด้านขวาของแผนผังย่อยด้านซ้าย

การหมุนนี้จะดำเนินการเมื่อโหนดมีปัจจัยความสมดุลเป็น –2 และลูกด้านขวามีปัจจัยความสมดุลเป็น +1

การหมุนซ้าย-ขวา

การหมุนนี้จะดำเนินการเมื่อมีการแทรกโหนดใหม่ที่ลูกด้านซ้ายของแผนผังย่อยด้านขวา

การหมุนนี้จะดำเนินการเมื่อโหนดมีปัจจัยความสมดุลเป็น +2 และลูกด้านซ้ายมีปัจจัยความสมดุลเป็น -1

การแทรกใน AVL Trees

การดำเนินการแทรกนั้นเกือบจะเหมือนกันกับการค้นหาแบบไบนารีแบบธรรมดา หลังจากแทรกทุกครั้ง เราจะปรับความสูงของทรีให้สมดุล การดำเนินการแทรกใช้เวลา O(log n) ซึ่งมีความซับซ้อนของเวลาที่สุด

ขั้นตอนที่ 1: แทรกโหนดในแผนผัง AVL โดยใช้อัลกอริธึมการแทรกเดียวกันกับ BST ในตัวอย่างข้างต้น ให้แทรก 160

ขั้นตอนที่ 2: เมื่อเพิ่มโหนดแล้ว ปัจจัยความสมดุลของแต่ละโหนดจะได้รับการอัปเดต หลังจากแทรก 160 แล้ว ตัวประกอบความสมดุลของทุกโหนดจะได้รับการอัปเดต

ขั้นตอนที่ 3: ตอนนี้ตรวจสอบว่าโหนดใดละเมิดช่วงของปัจจัยความสมดุลหรือไม่ หากปัจจัยด้านความสมดุลถูกละเมิด จากนั้นทำการหมุนโดยใช้กรณีด้านล่าง ในตัวอย่างข้างต้น มีการละเมิดปัจจัยความสมดุลที่ 350 และกรณีที่ 1 มีผลบังคับใช้ เราจะดำเนินการหมุน LL และต้นไม้จะมีความสมดุลอีกครั้ง

ถ้า BF(node) = +2 และ BF(node -> left-child) = +1 ให้ดำเนินการหมุน LL
ถ้า BF(node) = -2 และ BF(node -> right-child) = 1 ให้ดำเนินการหมุนเวียน RR
ถ้า BF(node) = -2 และ BF(node -> right-child) = +1 ให้ดำเนินการหมุน RL
ถ้า BF(node) = +2 และ BF(node -> left-child) = -1 ให้ดำเนินการหมุน LR

การลบใน AVL Trees

การลบยังตรงไปตรงมามาก เราลบโดยใช้ตรรกะเดียวกันกับในแผนผังการค้นหาแบบไบนารีธรรมดา หลังจากลบ เราจะปรับโครงสร้างต้นไม้ใหม่ หากจำเป็น เพื่อรักษาความสูงที่สมดุล

ขั้นตอนที่ 1: ค้นหาองค์ประกอบในแผนภูมิ

ขั้นตอนที่ 2: ลบโหนด ตามการลบ BST

ขั้นตอนที่ 3: เป็นไปได้ 2 กรณี คือ:-

กรณีฮิต: การลบออกจากทรีย่อยที่ถูกต้อง

1เอ ถ้า BF(node) = +2 และ BF(node -> left-child) = +1 ให้ดำเนินการหมุน LL
1B. ถ้า BF(node) = +2 และ BF(node -> left-child) = -1 ให้ดำเนินการหมุน LR
1ซี ถ้า BF(node) = +2 และ BF(node -> left-child) = 0 ให้ดำเนินการหมุน LL

2 กรณี: กำลังลบจากแผนผังย่อยด้านซ้าย

2เอ ถ้า BF(node) = -2 และ BF(node -> right-child) = -1 ให้ดำเนินการหมุนเวียน RR
2B. ถ้า BF(node) = -2 และ BF(node -> right-child) = +1 ให้ดำเนินการหมุน RL
2ซี. ถ้า BF(node) = -2 และ BF(node -> right-child) = 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 จะสมดุลเสมอ ความสูงไม่เคยสูงเกิน log N โดยที่ N คือจำนวนโหนดทั้งหมดในแผนผัง
ทำให้มีความซับซ้อนของเวลาในการค้นหาดีขึ้นเมื่อเปรียบเทียบกับการค้นหาแบบไบนารีแบบธรรมดา
ต้นไม้ AVL มีความสามารถในการปรับสมดุลในตัวเอง

สรุป

ต้นไม้ AVL เป็นแผนผังการค้นหาแบบไบนารีที่ปรับสมดุลในตัวเอง
ปัจจัยสมดุลเป็นคุณลักษณะพื้นฐานของแผนผัง AVL
ปัจจัยความสมดุลของโหนดถูกกำหนดให้เป็นความแตกต่างระหว่างความสูงของแผนผังย่อยด้านซ้ายและขวาของโหนดนั้น
ค่าที่ถูกต้องของตัวประกอบความสมดุลคือ -1, 0 และ +1
การดำเนินการแทรกและการลบต้องดำเนินการหมุนหลังจากละเมิดปัจจัยสมดุล
ความซับซ้อนของเวลาในการแทรก การลบ และการค้นหาคือ O(log N)
ทรี AVL เป็นไปตามคุณสมบัติทั้งหมดของ Binary Search Trees
ทรีย่อยด้านซ้ายมีโหนดที่น้อยกว่าโหนดรูท ทรีย่อยที่ถูกต้องมีโหนดที่ใหญ่กว่าโหนดรูทเสมอ
มีการใช้ต้นไม้ AVL ในกรณีที่การดำเนินการค้นหาเกิดขึ้นบ่อยกว่าเมื่อเทียบกับการแทรกและการลบ

ที่คุณอาจชอบ: