एक बाइनरी सर्च ट्री एक सॉर्टेड बाइनरी ट्री है जिसमें सभी नोड्स में निम्नलिखित दो गुण होते हैं -
एक नोड का राइट सब-ट्री उसके पैरेंट नोड की कुंजी से अधिक सभी कुंजियों को रखता है।
एक नोड का लेफ्ट सब-ट्री उसके पैरेंट नोड की कुंजी से कम सभी कुंजियों को रखता है। प्रत्येक नोड में दो से अधिक चाइल्ड नहीं होने चाहिए।
ट्री रोटेशन एक ऑपरेशन है जो बाइनरी ट्री पर एलिमेंट्स के क्रम में हस्तक्षेप किए बिना संरचना को बदलता है। यह एक नोड को ट्री में ऊपर ले जाता है और एक नोड को नीचे। इसका उपयोग ट्री के आकार को बदलने के लिए किया जाता है, और छोटे सबट्री को नीचे और बड़े सबट्री को ऊपर ले जाकर इसकी ऊंचाई को कम करता है, जिसके परिणामस्वरूप कई ट्री ऑपरेशंस के प्रदर्शन में सुधार होता है। रोटेशन की दिशा उस तरफ निर्भर करती है जिस तरफ ट्री नोड्स शिफ्ट होते हैं जबकि अन्य कहते हैं कि यह इस पर निर्भर करता है कि कौन सा चाइल्ड रूट की जगह लेता है। यह बाइनरी सर्च ट्री पर लेफ्ट रोटेशन करने के लिए एक 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;
}
};
// ... (पूर्ण कार्यान्वयन - AVL ट्री प्रोग्राम के समान)
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
...
Left-Left Rotation
...
Right-Right Rotation
...
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
