C++ প্রোগ্রাম: বাইনারি ট্রি AVL ট্রি কিনা যাচাই

AVL ট্রি কী?

AVL ট্রি একটি সেলফ-ব্যালেন্সিং বাইনারি সার্চ ট্রি (BST) যেখানে প্রতিটি নোডের জন্য লেফট ও রাইট সাবট্রির উচ্চতার পার্থক্য সর্বোচ্চ ১ হতে পারে। অর্থাৎ, |height(left) - height(right)| <= 1 সব নোডের জন্য।

এলগরিদম

রিকার্শিভ ফাংশন `isAVL(node*)` লিখুন।
বেস কেস: `node == nullptr` → `true` ফেরত দিন।
লেফট ও রাইট সাবট্রির উচ্চতা (`height`) নির্ণয় করুন।
যদি পার্থক্য > ১ হয় → `false`।
অন্যথায়, লেফট ও রাইট সাবট্রি দুটোই AVL কিনা রিকার্শিভলি চেক করুন।

উদাহরণ কোড

#include <iostream>
#include <algorithm>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

int height(Node* node) {
    if (!node) return 0;
    return 1 + max(height(node->left), height(node->right));
}

bool isAVL(Node* root) {
    if (!root) return true;

    int lh = height(root->left);
    int rh = height(root->right);

    if (abs(lh - rh) <= 1 && isAVL(root->left) && isAVL(root->right))
        return true;
    return false;
}

// Helper: ইনসার্ট ফাংশন (টেস্টের জন্য)
Node* insert(Node* root, int val) {
    if (!root) return new Node(val);
    if (val < root->data) root->left = insert(root->left, val);
    else root->right = insert(root->right, val);
    return root;
}

int main() {
    // AVL ট্রি উদাহরণ
    Node* root1 = nullptr;
    root1 = insert(root1, 7);
    root1 = insert(root1, 6);
    root1 = insert(root1, 12);
    root1 = insert(root1, 4);
    root1 = insert(root1, 5);
    root1 = insert(root1, 13);

    cout << (isAVL(root1) ? "AVL Tree" : "Not AVL Tree") << "\n";

    // Non-AVL ট্রি উদাহরণ
    Node* root2 = nullptr;
    root2 = insert(root2, 7);
    root2 = insert(root2, 6);
    root2 = insert(root2, 12);
    root2 = insert(root2, 4);
    root2 = insert(root2, 5);
    root2 = insert(root2, 13);
    root2 = insert(root2, 26); // Extra node causes imbalance

    cout << (isAVL(root2) ? "AVL Tree" : "Not AVL Tree") << "\n";
    return 0;
}

আউটপুট

AVL Tree
Not AVL Tree

ব্যাখ্যা

প্রোগ্রামটি প্রতিটি নোডের জন্য ব্যালেন্স ফ্যাক্টর চেক করে। প্রথম ট্রিতে সব নোড ব্যালেন্সড, দ্বিতীয় ট্রিতে নোড ১৩-র রাইট চাইল্ড ২৬ যোগ করলে ব্যালেন্স ফ্যাক্টর ২ হয়ে যায়, তাই সেটি AVL নয়। দক্ষতা বেড়ানোর জন্য `height` ক্যালকুলেশনকে `isAVL`-এ মেযার্জ করা যায় (O(n) টাইমে)।