समस्या कथन
AVL ट्री की ऊंचाई दी गई है, कार्य ट्री में न्यूनतम नोड्स की संख्या ढूंढना है जो ट्री में हो सकते हैं।
यदि ऊंचाई = 0 तो AVL ट्री में 1 नोड हो सकता है यदि ऊंचाई = 5 तो AVL ट्री में न्यूनतम 20 नोड्स हो सकते हैं
एल्गोरिदम
AVL ट्री में, हमें ऊंचाई संतुलन गुण बनाए रखना होता है, यानी बाएं और दाएं सबट्री की ऊंचाई में अंतर प्रत्येक नोड के लिए -1, 0 या 1 से अधिक नहीं हो सकता। इस गुण का उपयोग करके, हम नीचे दिए गए पुनरावृत्ति संबंध बना सकते हैं:
1. यदि ऊंचाई = 0 तो 1 लौटाएं 2. यदि ऊंचाई = 1 तो 2 लौटाएं 3. यदि ऊंचाई > 1 तो (1 + getMinAVLNodes(h-1) + getMinAVLNodes(h-2)) लौटाएं
C++ उदाहरण
#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