AVL ট্রি একটি সেলফ-ব্যালেন্সিং বাইনারি সার্চ ট্রি যেখানে যেকোনো নোডের বাম ও ডান সাবট্রির উচ্চতার পার্থক্য একের বেশি হতে পারে না।
ট্রি রোটেশন একটি অপারেশন যা এলিমেন্টের অর্ডার ছাড়া ছাড়া ট্রির কাঠামো পরিবর্তন করে। এটি এক নোডকে ট্রিতে উপরে এবং অন্যটিকে নিচে আনয়ে। এটি ট্রির আকার পরিবর্তন করে এবং উচ্চতা কমিয়ে বড় সাবট্রি উপরে এবং ছোট সাবট্রি নিচে আনয়ে, ফলে অনেক ট্রি অপারেশনের পারফরম্যান্স উন্নত হয়। রোটেশনের দিক ট্রি নোডগুলো কোন পাশে শিফট করা হয়েছে বা কোন চাইল্ড রুটের জায়গা নেয় সেটার ওপর নির্ভর করে। এটি AVL ট্রি ইমপ্লিমেন্ট করার একটি C++ প্রোগ্রাম।
ফাংশন বর্ণনা:
height(avl *): দেওয়া AVL ট্রির উচ্চতা গণনা করে।
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): ইন্সার্ট অপারেশন করে। এই ফাংশন ব্যবহার করে ট্রিতে মান যোগ করা হয়।
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 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;
}আউটপুট
(মেনু-চালিত ইন্টারঅ্যাক্টিভ আউটপুট, রোটেশন টাইপ সহ ট্রাভার্সাল ফলাফল দেখানো হয়েছে)
