AVL ट्री एक सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री है जहां बाएं और दाएं सबट्री की ऊंचाई का अंतर सभी नोड्स के लिए एक से अधिक नहीं हो सकता।
यह एक C++ प्रोग्राम है जो जांचता है कि दिया गया बाइनरी ट्री AVL ट्री है या नहीं।
एल्गोरिदम
Begin function AVL() दिए गए ट्री के AVL होने पर सच लौटाता है अन्यथा गलत। if(root == NULL) return 1 leftheight = height(root->left) rightheight = height(root->right) if(abs(leftheight-rightheight) <= 1 && AVL(root->left) && AVL(root->right)) return 1 return 0 End
उदाहरण
#include <bits/stdc++.h> using namespace std; class nod { //नोड घोषणा public: int data; nod* l; nod* r; }; nod* newNod(int d) { //नया नोड बनाना nod* Nod = new nod(); Nod->data = d; Nod->l = NULL; Nod->r = NULL; return(Nod); } int max(int x, int y) { //दो मानों के बीच अधिकतम लौटाएं return (x >= y)? x: y; } int height(nod* node) { //ऊंचाई प्राप्त करें मतलब रूट नोड से सबसे दूर के लीफ नोड तक सबसे लंबे पाथ पर नोड्स की संख्या। if(node == NULL) return 0; return 1 + max(height(node->l), height(node->r)); } bool AVL(nod *root) { int lh; int rh; if(root == NULL) return 1; lh = height(root->l); // बाएं ऊंचाई rh = height(root->r); // दाएं ऊंचाई if(abs(lh-rh) <= 1 && AVL(root->l) && AVL(root->r)) return 1; return 0; } int main() { //ट्री के नोड्स को इनपुट के रूप में लें nod *root = newNod(7); root->l = newNod(6); root->r = newNod(12); root->l->l = newNod(4); root->l->r = newNod(5); root->r->r = newNod(13); if(AVL(root)) cout << "The Tree is AVL Tree"<<endl; else cout << "The Tree is not AVL Tree "<<endl; nod *root1 = newNod(7); root1->l = newNod(6); root1->r = newNod(12); root1->l->l = newNod(4); root1->l->r = newNod(5); root1->r->r = newNod(13); root1->r->r->r = newNod(26); if(AVL(root1)) cout << "The Tree is AVL Tree"<<endl; else cout << "The Tree is not AVL Tree "<<endl; return 0; }
आउटपुट
The Tree is AVL Tree The Tree is not AVL Tree
