AVL ট্রি হলো একটি সেলফ-ব্যালেন্সিং বাইনারি সার্চ ট্রি যেখানে লেফট এবং রাইট সাবট্রির হাইটের পার্থক্য সব নোডের জন্য এক থেকে বেশি হতে পারে না।
ট্রি রোটেশন একটি অপারেশন যা এলিমেন্টের অর্ডার ছাড়া বিনা AVL ট্রির স্ট্রাকচার বদলায়। এটি একটি নোডকে ট্রিতে উপরে আনে এবং একটি নোডকে নিচে নামায়। এটি ট্রির আকৃতি বদলাতে এবং এর হাইট কমাতে ব্যবহৃত হয় ছোট সাবট্রি নিচে নেমাতে এবং বড় সাবট্রি উপরে আনে, ফলে অনেক ট্রি অপারেশনের পারফরম্যান্স উন্নত হয়। রোটেশনের ডাইরেকশন ওপরের সাইডের ওপর নির্ভর করে যেটি ট্রি নোডগুলো শিফট করা হয়ে থাকলে অন্যদের মতে সেটি নির্ভর করে কোন চাইল্ড রুটের জায়গা নেয়। এটি AVL ট্রি ইমপ্লিমেন্ট করার একটি C++ প্রোগ্রাম।
ফাংশন বিবরণ:
height(avl *) : দেওয়া AVL ট্রির হাইট ক্যালকুলেট করে।
difference(avl *): দেওয়া ট্রির সাবট্রি দুটির হাইটের পার্থক্য ক্যালকুলেট করে।
avl *rr_rotat(avl *): রাইট-রাইট রোটেশন হলো রাইট রোটেশন এরপর রাইট রোটেশনের কম্বিনেশন।
avl *ll_rotat(avl *): লेफট-লेफট রোটেশন হলো লेफট রোটেশন এরপর লeft রোটেশনের কম্বিনেশন।
avl *lr_rotat(avl*): লেফট-রাইট রোটেশন হলো লেফট রোটেশন এরপর রাইট রোটেশনের কম্বিনেশন।
avl *rl_rotat(avl *): এটি রাইট রোটেশন এরপর লেফট রোটেশনের কম্বিনেশন।
avl * balance(avl *): ব্যালেন্স ফ্যাক্টর পেয়ে ট্রিতে ব্যালেন্স অপারেশন করে।
avl * insert(avl*, int): ইনসার্ট অপারেশন করে। এই ফাংশন ব্যবহার করে ট্রিতে ভ্যালু ইনসার্ট করা হয়।
show(avl*, int): ট্রির ভ্যালুগুলো ডিসপ্লে করে।
inorder(avl *): ট্রি ইন-অর্ডার ম্যানারে ট্রাভার্স করে।
preorder(avl *): ট্রি প্রি-অর্ডার ম্যানারে ট্রাভার্স করে।
postorder(avl*): ট্রি পোস্ট-অর্ডার ম্যানারে ট্রাভার্স করে।
উদাহরণ কোড
#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;
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;
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;
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;
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 ... (মেনু চালু থাকে, বিভিন্ন ইনসার্টশন ও ট্রাভার্সেল দেখানো হয়েছে) ... Enter your Choice: 6
