C++ ব্যবহার করে প্রদত্ত উচ্চতা সহ একটি AVL গাছে নোডের ন্যূনতম সংখ্যা।

সমস্যা বিবৃতি

একটি AVL গাছের উচ্চতার পরিপ্রেক্ষিতে, কাজটি হল গাছটিতে ন্যূনতম কতগুলি নোড থাকতে পারে তা খুঁজে বের করা৷

যদি উচ্চতা =0 তাহলে AVL গাছে একটি 1 নোড থাকতে পারেযদি উচ্চতা =5 হয় তাহলে AVL গাছে ন্যূনতম 20টি নোড থাকতে পারে

অ্যালগরিদম

একটি AVL গাছে, আমাদের উচ্চতার ভারসাম্য বৈশিষ্ট্য বজায় রাখতে হবে, অর্থাৎ বাম এবং ডান সাবট্রির উচ্চতার পার্থক্য প্রতিটি নোডের জন্য -1, 0 বা 1-এর বেশি হতে পারে না। এই সম্পত্তি ব্যবহার করে, আমরা নীচের পুনরাবৃত্তি সম্পর্ক −

তৈরি করতে পারি <পূর্ব>1. উচ্চতা =0 হলে 12 ফেরত দিন। উচ্চতা =1 হলে 23 দিন। উচ্চতা> 1 হলে ফেরত দিন (1 + getMinAVLNodes(h – 1) + getMinAVLNodes(h – 2))

উদাহরণ

#include নেমস্পেস ব্যবহার করে std;int getMinAVLNodes(int h){ if (h <0) { ফেরত 0; } যদি (h ==0 || h ==1) { ফেরত h + 1; } রিটার্ন 1 + getMinAVLNodes(h - 1) + getMinAVLNodes(h -2);}int main(){ int h =5; cout <<"" <