Computer Programming Binary Search Tree (BST) এবং তার অপারেশন গাইড ও নোট

বাইনারি সার্চ ট্রি (BST) হল একটি বিশেষ ধরনের বাইনারি ট্রি, যেখানে প্রতিটি নোডের বাম সন্তানের মান তার নিজের মানের চেয়ে ছোট এবং ডান সন্তানের মান বড় হয়। এই গঠনটি ডেটাকে সঠিকভাবে সংরক্ষণ এবং অনুসন্ধান করার জন্য খুব কার্যকর।

১. বাইনারি সার্চ ট্রির মৌলিক ধারণা

১.১ BST এর গঠন

• নোড: প্রতিটি নোডে একটি মান (data), একটি বাম শিশু (left child) এবং একটি ডান শিশু (right child) থাকে।
• শিকড় (Root): ট্রির উপরের নোডকে শিকড় বলা হয়।

১.২ বৈশিষ্ট্য

• প্রতিটি নোডে সর্বাধিক দুটি সন্তান থাকতে পারে (বাম এবং ডান)।
• বাম subtree-এ থাকা সমস্ত মান মূল মানের চেয়ে কম।
• ডান subtree-এ থাকা সমস্ত মান মূল মানের চেয়ে বেশি।

২. BST এর অপারেশন

বাইনারি সার্চ ট্রির মধ্যে বিভিন্ন মৌলিক অপারেশন রয়েছে, যেমন ইনসার্ট, সার্চ, ডিলিট এবং ট্র্যাভার্সাল। নিচে প্রতিটি অপারেশনের ব্যাখ্যা ও C তে উদাহরণ দেওয়া হল।

২.১ ইনসার্ট (Insert)

একটি নতুন নোড যুক্ত করার জন্য ইনসার্ট ফাংশন ব্যবহার করা হয়।

C তে ইনসার্ট অপারেশন উদাহরণ

Node* insert(Node* node, int data) {
    // যদি ট্রি খালি হয়, নতুন নোড তৈরি করুন
    if (node == NULL) {
        return createNode(data);
    }

    // ডেটার সাথে তুলনা করুন এবং বাম বা ডান দিকে ইনসার্ট করুন
    if (data < node->data) {
        node->left = insert(node->left, data);
    } else {
        node->right = insert(node->right, data);
    }
    return node;
}

২.২ সার্চ (Search)

নির্দিষ্ট মান খুঁজে বের করার জন্য সার্চ ফাংশন ব্যবহার করা হয়।

C তে সার্চ অপারেশন উদাহরণ

int search(Node* root, int key) {
    // যদি ট্রি খালি হয়
    if (root == NULL) {
        return 0; // মান পাওয়া যায়নি
    }

    // যদি কী মূল মানের সাথে সমান হয়
    if (key == root->data) {
        return 1; // মান পাওয়া গেছে
    }

    // বাম বা ডান দিকে অনুসন্ধান করুন
    if (key < root->data) {
        return search(root->left, key);
    } else {
        return search(root->right, key);
    }
}

২.৩ ডিলিট (Delete)

একটি নোড মুছে ফেলার জন্য ডিলিট ফাংশন ব্যবহার করা হয়।

C তে ডিলিট অপারেশন উদাহরণ

Node* deleteNode(Node* root, int key) {
    // যদি ট্রি খালি হয়
    if (root == NULL) return root;

    // ডেটার সাথে তুলনা করুন এবং বাম বা ডান দিকে চলে যান
    if (key < root->data) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->data) {
        root->right = deleteNode(root->right, key);
    } else {
        // নোড পাওয়া গেছে
        // যদি নোডের একটিমাত্র সন্তান থাকে
        if (root->left == NULL) {
            Node* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            Node* temp = root->left;
            free(root);
            return temp;
        }

        // দুইটি সন্তান থাকলে ইনঅর্ডার পূর্ববর্তী নোড খুঁজুন
        Node* temp = root->right; // সাধারণত ডান subtree থেকে ন্যূনতম
        while (temp && temp->left != NULL) {
            temp = temp->left;
        }
        root->data = temp->data; // মুছে ফেলার জন্য ডেটা কপি করুন
        root->right = deleteNode(root->right, temp->data); // মুছে ফেলা
    }
    return root;
}

২.৪ ট্র্যাভার্সাল (Traversal)

বাইনারি সার্চ ট্রির ট্র্যাভার্সাল অপারেশন যেমন ইনঅর্ডার, প্রি-অর্ডার, এবং পোস্ট-অর্ডার ট্র্যাভার্সাল প্রয়োগ করা যায়।

C তে ইনঅর্ডার ট্রাভার্সাল উদাহরণ

void inOrderTraversal(Node* root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        printf("%d ", root->data);
        inOrderTraversal(root->right);
    }
}

৩. সম্পূর্ণ প্রোগ্রাম উদাহরণ

#include <stdio.h>
#include <stdlib.h>

// নোডের গঠন
typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;

// নতুন নোড তৈরি করা
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// ইনসার্ট অপারেশন
Node* insert(Node* node, int data) {
    if (node == NULL) {
        return createNode(data);
    }
    if (data < node->data) {
        node->left = insert(node->left, data);
    } else {
        node->right = insert(node->right, data);
    }
    return node;
}

// সার্চ অপারেশন
int search(Node* root, int key) {
    if (root == NULL) return 0; // মান পাওয়া যায়নি
    if (key == root->data) return 1; // মান পাওয়া গেছে
    return (key < root->data) ? search(root->left, key) : search(root->right, key);
}

// ডিলিট অপারেশন
Node* deleteNode(Node* root, int key) {
    if (root == NULL) return root;
    if (key < root->data) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->data) {
        root->right = deleteNode(root->right, key);
    } else {
        if (root->left == NULL) {
            Node* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            Node* temp = root->left;
            free(root);
            return temp;
        }
        Node* temp = root->right;
        while (temp && temp->left != NULL) {
            temp = temp->left;
        }
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

// ইনঅর্ডার ট্রাভার্সাল
void inOrderTraversal(Node* root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        printf("%d ", root->data);
        inOrderTraversal(root->right);
    }
}

int main() {
    Node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    printf("Inorder Traversal: ");
    inOrderTraversal(root); // আউটপুট: 20 30 40 50 60 70 80
    printf("\n");

    root = deleteNode(root, 20);
    printf("Inorder Traversal after deleting 20: ");
    inOrderTraversal(root); // আউটপুট: 30 40 50 60 70 80
    printf("\n");

    root = deleteNode(root, 30);
    printf("Inorder Traversal after deleting 30: ");
    inOrderTraversal(root); // আউটপুট: 40 50 60 70 80
    printf("\n");

    root = deleteNode(root, 50);
    printf("Inorder Traversal after deleting 50: ");
    inOrderTraversal(root); // আউটপুট: 40 60 70 80
    printf("\n");

    return 0;
}

৪. উপসংহার

বাইনারি সার্চ ট্রি (BST) একটি শক্তিশালী ডেটা স্ট্রাকচার যা ডেটা সংরক্ষণ এবং অনুসন্ধানের জন্য কার্যকরী। ইনসার্ট, সার্চ, ডিলিট, এবং ট্র্যাভার্সাল অপারেশনগুলি BST এর মৌলিক কার্যকারিতা। BST ব্যবহার করে ডেটার সংগঠন এবং কার্যকরী অনুসন্ধানের জন্য এটি অত্যন্ত গুরুত্বপূর্ণ।