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