C++ का उपयोग करके दी गई ऊंचाई वाले AVL ट्री में नोड्स की न्यूनतम संख्या।

समस्या कथन

AVL ट्री की ऊंचाई को देखते हुए, कार्य यह पता लगाना है कि पेड़ में कितने नोड्स हो सकते हैं।

If height = 0 then AVL tree can have one 1 node
If height = 5 then AVL tree can have minimum 20 nodes

एल्गोरिदम

AVL ट्री में, हमें हाइट बैलेंस प्रॉपर्टी को बनाए रखना होता है, यानी बाएं और दाएं सबट्री की ऊंचाई में अंतर प्रत्येक नोड के लिए -1, 0 या 1 से अधिक नहीं हो सकता है। इस गुण का उपयोग करके, हम नीचे पुनरावर्तन संबंध बना सकते हैं -

1. If height = 0 then return 1
2. If height = 1 then return 2
3. If height > 1 then return (1 + getMinAVLNodes(h – 1) + getMinAVLNodes(h – 2))

उदाहरण

#include <iostream>
using namespace std;
int getMinAVLNodes(int h){
   if (h < 0) {
      return 0;
   }
   if (h == 0 || h == 1) {
      return h + 1;
   }
   return 1 + getMinAVLNodes(h - 1) + getMinAVLNodes(h -2);
}
int main(){
   int h = 5;
   cout << "Minimum nodes for " << h << " height = " << getMinAVLNodes(h) << endl;
   return 0;
}

आउटपुट

जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्न आउटपुट उत्पन्न करता है -

Minimum nodes for 5 height = 20