নন-লিনিয়ার ডেটা স্ট্রাকচার: ট্রি, গ্রাফ

নন-লাইনিয়ার ডেটা স্ট্রাকচার হলো এমন ডেটা স্ট্রাকচার যেখানে উপাদানগুলো একটি সরল রেখায় সাজানো থাকে না। এর মধ্যে ট্রি (Tree) এবং গ্রাফ (Graph) অন্তর্ভুক্ত, যা জটিল সম্পর্ক এবং হায়ারার্কি মডেলিংয়ের জন্য ব্যবহৃত হয়।

নিচে ট্রি এবং গ্রাফের বিস্তারিত আলোচনা করা হলো:

1. ট্রি (Tree)

ট্রি হলো একটি হায়ারার্কিকাল ডেটা স্ট্রাকচার, যেখানে প্রতিটি উপাদান (নোড) একটি পিতামাতা নোড এবং এক বা একাধিক সন্তানের সাথে যুক্ত থাকে। একটি ট্রির মধ্যে একটি মূল (root) নোড থাকে, যা ট্রির শীর্ষে অবস্থিত।

বৈশিষ্ট্য:

• নোড: ট্রির প্রতিটি উপাদান, যা ডেটা ধারণ করে এবং তার সন্তানের রেফারেন্স থাকে।
• মূল (Root): ট্রির প্রথম নোড, যা কোনও পিতামাতা নোড নেই।
• পাতা (Leaf): এমন নোড, যার কোনও সন্তান নেই।
• ডেপ্থ: মূল নোড থেকে নোড পর্যন্ত পথের দৈর্ঘ্য।
• হাইট: কোনও নোডের সর্বোচ্চ সন্তানদের দৈর্ঘ্য।

উদাহরণ (C++):

#include <iostream>

struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int value) : data(value), left(nullptr), right(nullptr) {} // কনস্ট্রাক্টর
};

// ইনঅর্ডার ট্রাভার্সাল
void inorder(TreeNode* node) {
    if (node == nullptr) return;
    inorder(node->left);
    std::cout << node->data << " ";
    inorder(node->right);
}

int main() {
    TreeNode* root = new TreeNode(1); // মূল নোড
    root->left = new TreeNode(2);      // বাম সন্তান
    root->right = new TreeNode(3);     // ডান সন্তান
    root->left->left = new TreeNode(4); // বাম সন্তানের বাম সন্তান

    std::cout << "Inorder Traversal: ";
    inorder(root); // আউটপুট: 4 2 1 3
    return 0;
}

2. গ্রাফ (Graph)

গ্রাফ হলো একটি নোড (বা ভেরটেক্স) এবং তাদের মধ্যে সংযোগ (এজ) নিয়ে গঠিত ডেটা স্ট্রাকচার। গ্রাফগুলি বিভিন্ন সমস্যা সমাধানে ব্যবহৃত হয়, যেমন নেটওয়ার্ক মডেলিং, রাস্তাঘাটের ম্যাপ ইত্যাদি। গ্রাফের দুইটি প্রধান ধরন হলো:

• অরডিনারি গ্রাফ (Undirected Graph): যেখানে এজের দিক নেই, অর্থাৎ A থেকে B যাওয়া মানে B থেকে A যাওয়াও সম্ভব।
• ডিরেক্টেড গ্রাফ (Directed Graph): যেখানে এজের একটি দিক থাকে, অর্থাৎ A থেকে B যাওয়া মানে B থেকে A যাওয়া সম্ভব নয়।

বৈশিষ্ট্য:

• ভেরটেক্স (Vertex): গ্রাফের একটি নোড।
• এজ (Edge): দুটি ভেরটেক্সের মধ্যে সংযোগ।
• ওজন (Weight): এজে একটি সংখ্যা, যা দুটি ভেরটেক্সের মধ্যে সম্পর্কের শক্তি বা দূরত্ব নির্দেশ করে।

উদাহরণ (C++):

#include <iostream>
#include <vector>

class Graph {
public:
    int vertices; // ভেরটেক্সের সংখ্যা
    std::vector<std::vector<int>> adjList; // অ্যাডজাসেন্সি লিস্ট

    Graph(int v) : vertices(v), adjList(v) {} // কনস্ট্রাক্টর

    void addEdge(int u, int v) {
        adjList[u].push_back(v); // অরডিনারি গ্রাফে সংযোগ
        adjList[v].push_back(u); // যেহেতু এটি অরডিনারি গ্রাফ
    }

    void printGraph() {
        for (int i = 0; i < vertices; ++i) {
            std::cout << "Vertex " << i << ": ";
            for (int j : adjList[i]) {
                std::cout << j << " ";
            }
            std::cout << std::endl;
        }
    }
};

int main() {
    Graph graph(5); // 5 ভেরটেক্স নিয়ে একটি গ্রাফ তৈরি
    graph.addEdge(0, 1);
    graph.addEdge(0, 4);
    graph.addEdge(1, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);

    graph.printGraph(); // গ্রাফের তথ্য প্রদর্শন
    return 0;
}

সারাংশ

1. ট্রি (Tree): একটি হায়ারার্কিকাল ডেটা স্ট্রাকচার, যা নোডের মধ্যে পিতামাতা-সন্তানের সম্পর্ক নিয়ে গঠিত।
2. গ্রাফ (Graph): একটি নোড (ভেরটেক্স) এবং তাদের মধ্যে সংযোগ (এজ) নিয়ে গঠিত, যা বিভিন্ন জটিল সম্পর্ক এবং সমস্যা সমাধানে ব্যবহৃত হয়।

নন-লাইনিয়ার ডেটা স্ট্রাকচারগুলো জটিল সম্পর্ক এবং ডেটা সংগঠনে কার্যকরী। এগুলো বিভিন্ন অ্যালগরিদম এবং ডেটা ম্যানেজমেন্টের জন্য অপরিহার্য।