Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

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

समस्या कथन

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
  1. - C++ में दो स्ट्रिंग्स को समान बनाने के लिए दिए गए ऑपरेशन के न्यूनतम नंबर

    समस्या कथन दो स्ट्रिंग्स str1 और str2 दी गई हैं, दोनों में a और b वर्ण हैं। दोनों स्ट्रिंग्स समान लंबाई की हैं। दोनों स्ट्रिंग्स में एक _ (खाली स्थान) है। पहले स्ट्रिंग को दूसरी स्ट्रिंग में बदलने के लिए निम्न ऑपरेशन का उपयोग करके न्यूनतम ऑपरेशन की संख्या ढूंढें: यदि _ स्थिति i पर है तो _ को स्

  1. - C++ में N को 25 से विभाज्य बनाने के लिए दिए गए मूव्स की न्यूनतम संख्या

    समस्या कथन अग्रणी शून्य के बिना एक संख्या N दी गई है। N को 25 से विभाज्य बनाने के लिए आवश्यक न्यूनतम मूव्स की संख्या ढूंढें। प्रत्येक मूव में, कोई भी दो आसन्न अंकों को स्वैप कर सकता है और यह सुनिश्चित करना होगा कि किसी भी समय संख्या में कोई अग्रणी शून्य न हो। यदि N को 25 से विभाज्य बनाना संभव नहीं ह

  1. - C++ में किसी संख्या के गुणनखंडों का न्यूनतम योग ढूंढना

    यहां हम देखेंगे कि किसी दी गई संख्या के गुणनखंडों का न्यूनतम योग कैसे प्राप्त करें। मान लीजिए एक संख्या 12 है। हम इसे अलग-अलग तरीकों से गुणनखंडित कर सकते हैं: 12 = 12 × 1 (12 + 1 = 13) 12 = 2 × 6 (2 + 6 = 8) 12 = 3 × 4 (3 + 4 = 7) 12 = 2 × 2 × 3 (2 + 2 + 3 = 7) न्यूनतम योग 7 है। हम