โปรแกรม C++ ใช้งาน AVL Tree

การใช้งาน AVL Tree ใน C++

AVL tree เป็น Binary Search Tree ที่ปรับสมดุลเอง (self-balancing) โดยความสูงของ subtree ซ้ายและขวาแตกต่างกันไม่เกิน 1 สำหรับทุกโหนด

Tree rotation เป็นการดำเนินการเปลี่ยนโครงสร้างโดยไม่กระทบลำดับขององค์ประกอบใน AVL tree ย้ายโหนดหนึ่งขึ้น และอีกโหนดหนึ่งลง ใช้เปลี่ยนรูปร่างต้นไม้ ลดความสูงโดยย้าย subtree ที่เล็กกว่าลง และ subtree ที่ใหญ่กว่าขึ้น ทำให้การดำเนินการต่างๆ มีประสิทธิภาพมากขึ้น ทิศทางของการหมุนขึ้นอยู่กับด้านที่โหนดถูกเลื่อน

คำอธิบายฟังก์ชัน:

• height(avl *): คำนวณความสูงของ AVL tree ที่กำหนด
• difference(avl *): คำนวณความต่างความสูงของ subtree ซ้ายและขวา
• avl *rr_rotat(avl *): หมุนขวา-ขวา (right-right rotation)
• avl *ll_rotat(avl *): หมุนซ้าย-ซ้าย (left-left rotation)
• avl *lr_rotat(avl*): หมุนซ้าย-ขวา (left-right rotation)
• avl *rl_rotat(avl *): หมุนขวา-ซ้าย (right-left rotation)
• avl *balance(avl *): ทำการปรับสมดุลต้นไม้ด้วย balance factor
• avl *insert(avl*, int): แทรกค่าในต้นไม้
• show(avl*, int): แสดงค่าของต้นไม้
• inorder(avl *): เรียงลำดับ in-order
• preorder(avl *): เรียงลำดับ pre-order
• postorder(avl*): เรียงลำดับ post-order

ตัวอย่างโค้ด

#include <iostream>
#include <cstdio>
#include <sstream>
#include <algorithm>
#define pow2(n) (1 << (n))
using namespace std;

struct avl {
    int d;
    struct avl *l;
    struct avl *r;
} *r;

class avl_tree {
public:
    int height(avl *);
    int difference(avl *);
    avl *rr_rotat(avl *);
    avl *ll_rotat(avl *);
    avl *lr_rotat(avl*);
    avl *rl_rotat(avl *);
    avl *balance(avl *);
    avl *insert(avl*, int);
    void show(avl*, int);
    void inorder(avl *);
    void preorder(avl *);
    void postorder(avl*);
    avl_tree() { r = NULL; }
};

int avl_tree::height(avl *t) {
    int h = 0;
    if (t != NULL) {
        int l_height = height(t->l);
        int r_height = height(t->r);
        int max_height = max(l_height, r_height);
        h = max_height + 1;
    }
    return h;
}

int avl_tree::difference(avl *t) {
    int l_height = height(t->l);
    int r_height = height(t->r);
    int b_factor = l_height - r_height;
    return b_factor;
}

avl *avl_tree::rr_rotat(avl *parent) {
    avl *t = parent->r;
    parent->r = t->l;
    t->l = parent;
    cout << "Right-Right Rotation";
    return t;
}

avl *avl_tree::ll_rotat(avl *parent) {
    avl *t = parent->l;
    parent->l = t->r;
    t->r = parent;
    cout << "Left-Left Rotation";
    return t;
}

avl *avl_tree::lr_rotat(avl *parent) {
    avl *t = parent->l;
    parent->l = rr_rotat(t);
    cout << "Left-Right Rotation";
    return ll_rotat(parent);
}

avl *avl_tree::rl_rotat(avl *parent) {
    avl *t = parent->r;
    parent->r = ll_rotat(t);
    cout << "Right-Left Rotation";
    return rr_rotat(parent);
}

avl *avl_tree::balance(avl *t) {
    int bal_factor = difference(t);
    if (bal_factor > 1) {
        if (difference(t->l) > 0) t = ll_rotat(t);
        else t = lr_rotat(t);
    } else if (bal_factor < -1) {
        if (difference(t->r) > 0) t = rl_rotat(t);
        else t = rr_rotat(t);
    }
    return t;
}

avl *avl_tree::insert(avl *r, int v) {
    if (r == NULL) {
        r = new avl;
        r->d = v;
        r->l = NULL;
        r->r = NULL;
        return r;
    } else if (v < r->d) {
        r->l = insert(r->l, v);
        r = balance(r);
    } else if (v >= r->d) {
        r->r = insert(r->r, v);
        r = balance(r);
    }
    return r;
}

void avl_tree::show(avl *p, int l) {
    int i;
    if (p != NULL) {
        show(p->r, l + 1);
        cout << " ";
        if (p == r) cout << "Root -> ";
        for (i = 0; i < l && p != r; i++) cout << " ";
        cout << p->d;
        show(p->l, l + 1);
    }
}

void avl_tree::inorder(avl *t) {
    if (t == NULL) return;
    inorder(t->l);
    cout << t->d << " ";
    inorder(t->r);
}

void avl_tree::preorder(avl *t) {
    if (t == NULL) return;
    cout << t->d << " ";
    preorder(t->l);
    preorder(t->r);
}

void avl_tree::postorder(avl *t) {
    if (t == NULL) return;
    postorder(t->l);
    postorder(t->r);
    cout << t->d << " ";
}

int main() {
    int c, i;
    avl_tree avl;
    while (1) {
        cout << "1.Insert Element into the tree" << endl;
        cout << "2.show Balanced AVL Tree" << endl;
        cout << "3.InOrder traversal" << endl;
        cout << "4.PreOrder traversal" << endl;
        cout << "5.PostOrder traversal" << endl;
        cout << "6.Exit" << endl;
        cout << "Enter your Choice: ";
        cin >> c;
        switch (c) {
            case 1:
                cout << "Enter value to be inserted: ";
                cin >> i;
                r = avl.insert(r, i);
                break;
            case 2:
                if (r == NULL) {
                    cout << "Tree is Empty" << endl;
                    continue;
                }
                cout << "Balanced AVL Tree:" << endl;
                avl.show(r, 1);
                cout << endl;
                break;
            case 3:
                cout << "Inorder Traversal:" << endl;
                avl.inorder(r);
                cout << endl;
                break;
            case 4:
                cout << "Preorder Traversal:" << endl;
                avl.preorder(r);
                cout << endl;
                break;
            case 5:
                cout << "Postorder Traversal:" << endl;
                avl.postorder(r);
                cout << endl;
                break;
            case 6:
                exit(1);
                break;
            default:
                cout << "Wrong Choice" << endl;
        }
    }
    return 0;
}

ผลลัพธ์

1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 13
...
Inorder Traversal: 4 5 8 10 11 13 15 16
Preorder Traversal: 10 5 4 8 13 11 15 16
Postorder Traversal: 4 8 5 11 16 15 13 10