โปรแกรม C++ ใช้ Self-Balancing Binary Search Tree (AVL Tree)

บทนำ

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

นี่คือโปรแกรม C++ ใช้ Self-Balancing Binary Search Tree

คำอธิบายคลาส

Begin class avl_tree ประกาศฟังก์ชัน:
  balance() = ทำให้ต้นไม้สมดุลด้วย balance factor คำนวณ diff ใน bal_factor
    ถ้า bal_factor > 1 ทำให้ left subtree สมดุล
    ถ้า bal_factor < -1 ทำให้ right subtree สมดุล
  insert() = แทรกข้อมูลในต้นไม้:
    ถ้าต้นไม้ว่าง ใส่ data เป็น root
    ถ้าต้นไม้ไม่ว่าง และ data > root ใส่เป็น left child
    มิฉะนั้น ใส่เป็น right child
End.

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

#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;
} *root;

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() { root = 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 == root) cout << "Root -> ";
        for (i = 0; i < l && p != root; 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;
                root = avl.insert(root, i);
                break;
            case 2:
                if (root == NULL) {
                    cout << "Tree is Empty" << endl;
                    continue;
                }
                cout << "Balanced AVL Tree:" << endl;
                avl.show(root, 1);
                cout << endl;
                break;
            case 3:
                cout << "Inorder Traversal:" << endl;
                avl.inorder(root);
                cout << endl;
                break;
            case 4:
                cout << "Preorder Traversal:" << endl;
                avl.preorder(root);
                cout << endl;
                break;
            case 5:
                cout << "Postorder Traversal:" << endl;
                avl.postorder(root);
                cout << endl;
                break;
            case 6:
                exit(1);
            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
... (ตัวอย่างการทำงานต่อไป รวมถึงการหมุน Left-Left, Right-Right)