C++ ব্যবহার করে দেওয়া উচ্চতার AVL ট্রির ন্যূনতম নোড সংখ্যা

সমস্যা বিবরণ

একটি AVL ট্রির উচ্চতা দেওয়া আছে। ট্রিটি ন্যূনতম কতগুলো নোড রাখতে পারে তা বের করতে হবে।

যদি height = 0 হয় তবে AVL ট্রিতে ১টি নোড থাকতে পারে
যদি height = 5 হয় তবে AVL ট্রিতে ন্যূনতম ২০টি নোড থাকতে পারে

এলগরিদম

AVL ট্রিতে হাইট ব্যালেন্স প্রোপার্টি মেনে চলতে হয়, অর্থাৎ বাম ও ডান সাবট্রির উচ্চতার পার্থক্য প্রতিটি নোডের জন্য -১, ০ বা ১ হতে পারে। এই প্রোপার্টি ব্যবহার করে নিচের রিকারেন্স রিলেশন তৈরি করা যায়:

1. যদি height = 0 হয় তবে রিটার্ন ১
2. যদি height = 1 হয় তবে রিটার্ন ২
3. যদি height > 1 হয় তবে রিটার্ন (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