Computer Programming বাইনারি ট্রি (Binary Tree in C) গাইড ও নোট

বাইনারি ট্রি হল একটি ডেটা স্ট্রাকচার যেখানে প্রতিটি নোডে সর্বাধিক দুইটি সন্তান থাকে, অর্থাৎ, প্রতিটি নোডের একটি বাম সন্তান এবং একটি ডান সন্তান থাকতে পারে। বাইনারি ট্রি ডেটা সংগঠনের জন্য ব্যবহৃত হয় এবং এটি বিভিন্ন এলগরিদম এবং সমস্যার সমাধানে গুরুত্বপূর্ণ।

১. বাইনারি ট্রির গঠন

১.১ নোডের গঠন

একটি বাইনারি ট্রির একটি নোড সাধারণত নিম্নলিখিত গঠন নিয়ে থাকে:

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;
}

Binary Tree হল একটি ডেটা স্ট্রাকচার যেখানে প্রতিটি নোডে সর্বাধিক দুটি সন্তান (left এবং right) থাকতে পারে। এটি একটি গঠন যা ডেটা সংগঠনের জন্য ব্যবহৃত হয় এবং বিভিন্ন এলগরিদম এবং সমস্যার সমাধানে গুরুত্বপূর্ণ ভূমিকা পালন করে। নিচে বাইনারি ট্রির মৌলিক ধারণা, গঠন, প্রকারভেদ এবং ট্রাভার্সাল পদ্ধতির বিশ্লেষণ করা হলো।

১. Binary Tree এর গঠন

১.১ Node Structure

একটি বাইনারি ট্রির নোড সাধারণত তিনটি অংশ নিয়ে গঠিত:

1. ডেটা (Data): নোডের মধ্যে সংরক্ষিত মান।
2. বাম সন্তান (Left Child): নোডের বাম দিকে অবস্থিত শিশু নোড।
3. ডান সন্তান (Right Child): নোডের ডান দিকে অবস্থিত শিশু নোড।

typedef struct Node {
    int data;               // নোডের ডেটা
    struct Node *left;     // বাম সন্তান
    struct Node *right;    // ডান সন্তান
} Node;

১.২ Binary Tree এর গঠন

বাইনারি ট্রি সাধারণত একটি হেড নোড দ্বারা শুরু হয়, এবং প্রতিটি নোডে দুটি সন্তানের জন্য স্থান বরাদ্দ থাকে।

২. Binary Tree এর প্রকারভেদ

২.১ পূর্ণ বাইনারি ট্রি (Full Binary Tree)

এটি এমন একটি বাইনারি ট্রি যেখানে প্রতিটি নোডের শূন্য বা দুটি সন্তান থাকে।

২.২ সম্পূর্ণ বাইনারি ট্রি (Complete Binary Tree)

এটি একটি বাইনারি ট্রি যেখানে সব স্তরের নোড সম্পূর্ণভাবে পূর্ণ থাকে, তবে শেষ স্তরের নোড বামদিকে পূর্ণ থাকে।

২.৩ ব্যালেন্সড বাইনারি ট্রি (Balanced Binary Tree)

এটি এমন একটি ট্রি যেখানে প্রতিটি নোডের বাম এবং ডান সাবট্রির উচ্চতার মধ্যে সর্বাধিক এক স্তরের পার্থক্য থাকে।

২.৪ বাইনারি অনুসন্ধান ট্রি (Binary Search Tree)

এটি একটি বিশেষ ধরনের বাইনারি ট্রি যেখানে প্রতিটি নোডের বাম সন্তানের মান তার নিজস্ব মানের থেকে ছোট এবং ডান সন্তানের মান বড় হয়।

৩. Binary Tree এর ট্রাভার্সাল পদ্ধতি

বাইনারি ট্রির নোডগুলিকে এক বা একাধিকভাবে পরিদর্শন করতে তিনটি প্রধান পদ্ধতি রয়েছে:

৩.১ ইনঅর্ডার ট্রাভার্সাল (In-Order Traversal)

• প্রক্রিয়া: বাম শিশু -> মূল নোড -> ডান শিশু
• এটি একটি বাইনারি অনুসন্ধান ট্রির জন্য সাজানো ডেটা প্রদান করে।

৩.২ প্রি-অর্ডার ট্রাভার্সাল (Pre-Order Traversal)

• প্রক্রিয়া: মূল নোড -> বাম শিশু -> ডান শিশু
• এটি ডেটা কাঠামোর সংরক্ষণের জন্য ব্যবহৃত হয়।

৩.৩ পোস্ট-অর্ডার ট্রাভার্সাল (Post-Order Traversal)

• প্রক্রিয়া: বাম শিশু -> ডান শিশু -> মূল নোড
• এটি নোড মুছে ফেলার সময় ব্যবহার করা হয়।

৩.৪ স্তর অনুযায়ী ট্রাভার্সাল (Level Order Traversal)

• এই পদ্ধতিতে, ট্রি স্তর অনুযায়ী পরিদর্শন করা হয়। প্রথমে শিকড়, তারপর প্রথম স্তর, তারপরে দ্বিতীয় স্তর ইত্যাদি।

বাইনারি ট্রির নোডগুলি পরিদর্শন করার জন্য বিভিন্ন পদ্ধতি রয়েছে। এই পদ্ধতিগুলি হল ইনঅর্ডার, প্রি-অর্ডার, এবং পোস্ট-অর্ডার। প্রতিটি পদ্ধতি নোডগুলিকে ভিন্নভাবে পরিদর্শন করে।

১. ইনঅর্ডার ট্রাভার্সাল (Inorder Traversal)

১.১ ধারণা

ইনঅর্ডার ট্রাভার্সাল পদ্ধতিতে নোডগুলি নিম্নরূপ পরিদর্শন করা হয়:

1. বাম শিশু -> মূল নোড -> ডান শিশু

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

• বাইনারি অনুসন্ধান ট্রি (BST) হলে, ইনঅর্ডার ট্রাভার্সাল গঠন করে সাজানো ডেটা।
• যখন সাজানো ডেটা প্রয়োজন, তখন এই পদ্ধতি ব্যবহার করা হয়।

১.৩ C তে উদাহরণ

#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;
}

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

int main() {
    Node* root = createNode(4);
    root->left = createNode(2);
    root->right = createNode(5);
    root->left->left = createNode(1);
    root->left->right = createNode(3);

    printf("Inorder Traversal: ");
    inOrderTraversal(root); // আউটপুট: 1 2 3 4 5
    printf("\n");

    return 0;
}

২. প্রি-অর্ডার ট্রাভার্সাল (Preorder Traversal)

২.১ ধারণা

প্রি-অর্ডার ট্রাভার্সাল পদ্ধতিতে নোডগুলি নিম্নরূপ পরিদর্শন করা হয়:

1. মূল নোড -> বাম শিশু -> ডান শিশু

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

• এই পদ্ধতি ব্যবহৃত হয় গাছের কপি তৈরি করার জন্য অথবা অভিব্যক্তি গাছের প্রিফিক্স এক্সপ্রেশন পেতে।
• এটি পিতৃ নোডকে প্রথমে প্রক্রিয়া করে।

২.৩ C তে উদাহরণ

// প্রি-অর্ডার ট্রাভার্সাল
void preOrderTraversal(Node* root) {
    if (root != NULL) {
        printf("%d ", root->data);      // মূল নোড
        preOrderTraversal(root->left);  // বাম subtree
        preOrderTraversal(root->right); // ডান subtree
    }
}

int main() {
    Node* root = createNode(4);
    root->left = createNode(2);
    root->right = createNode(5);
    root->left->left = createNode(1);
    root->left->right = createNode(3);

    printf("Preorder Traversal: ");
    preOrderTraversal(root); // আউটপুট: 4 2 1 3 5
    printf("\n");

    return 0;
}

৩. পোস্ট-অর্ডার ট্রাভার্সাল (Postorder Traversal)

৩.১ ধারণা

পোস্ট-অর্ডার ট্রাভার্সাল পদ্ধতিতে নোডগুলি নিম্নরূপ পরিদর্শন করা হয়:

1. বাম শিশু -> ডান শিশু -> মূল নোড

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

• এই পদ্ধতি গাছটি মুছে ফেলতে ব্যবহৃত হয়, কারণ এটি নিশ্চিত করে যে শিশুর নোডগুলি পিতৃ নোডের আগে প্রক্রিয়া করা হয়।
• এটি পোস্টফিক্স এক্সপ্রেশন পেতে ব্যবহার হয়।

৩.৩ C তে উদাহরণ

// পোস্ট-অর্ডার ট্রাভার্সাল
void postOrderTraversal(Node* root) {
    if (root != NULL) {
        postOrderTraversal(root->left);  // বাম subtree
        postOrderTraversal(root->right); // ডান subtree
        printf("%d ", root->data);      // মূল নোড
    }
}

int main() {
    Node* root = createNode(4);
    root->left = createNode(2);
    root->right = createNode(5);
    root->left->left = createNode(1);
    root->left->right = createNode(3);

    printf("Postorder Traversal: ");
    postOrderTraversal(root); // আউটপুট: 1 3 2 5 4
    printf("\n");

    return 0;
}

৪. সারাংশ

• ইনঅর্ডার ট্রাভার্সাল: বাম -> মূল -> ডান। সাজানো ডেটা পাওয়ার জন্য কার্যকরী।
• প্রি-অর্ডার ট্রাভার্সাল: মূল -> বাম -> ডান। গাছের কপি তৈরি করতে ব্যবহৃত হয়।
• পোস্ট-অর্ডার ট্রাভার্সাল: বাম -> ডান -> মূল। গাছ মুছে ফেলার সময় ব্যবহৃত হয়।

এই ট্রাভার্সাল পদ্ধতিগুলি বাইনারি ট্রির সাথে কাজ করার জন্য গুরুত্বপূর্ণ, এবং বিভিন্ন অ্যালগরিদম বাস্তবায়নে ব্যবহৃত হয়।

বাইনারি সার্চ ট্রি (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 ব্যবহার করে ডেটার সংগঠন এবং কার্যকরী অনুসন্ধানের জন্য এটি অত্যন্ত গুরুত্বপূর্ণ।

AVL Tree একটি বিশেষ ধরনের Balanced Binary Tree যা বাইনারি সার্চ ট্রির উপর ভিত্তি করে তৈরি হয়। AVL Tree গঠন করে যখন প্রতিটি নোডের বাম এবং ডান সন্তানের উচ্চতার মধ্যে পার্থক্য সর্বাধিক ১ হয়, তখন এটি একটি ব্যালেন্সড ট্রি হয়। এই বৈশিষ্ট্যের কারণে AVL Tree দ্রুত অনুসন্ধান, ইনসার্ট, এবং ডিলিট অপারেশন সমর্থন করে।

১. AVL Tree এর মৌলিক ধারণা

১.১ AVL Tree এর গঠন

• নোড: প্রতিটি নোডে ডেটা, বাম সন্তান, ডান সন্তান এবং উচ্চতা (height) তথ্য থাকে।
• ব্যালেন্স ফ্যাক্টর: প্রতিটি নোডের জন্য, ব্যালেন্স ফ্যাক্টর হল বাম subtree এর উচ্চতা এবং ডান subtree এর উচ্চতার মধ্যে পার্থক্য। এটি -1, 0 বা 1 হতে পারে।

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

• AVL Tree সর্বদা ব্যালেন্সড থাকে, অর্থাৎ প্রতিটি নোডের জন্য ব্যালেন্স ফ্যাক্টর -1, 0, বা 1 হতে হবে।
• উচ্চতা O(log n) তে থাকে, যেখানে n হল নোডের সংখ্যা।

২. AVL Tree এর অপারেশন

AVL Tree এ ইনসার্ট, ডিলিট, এবং সার্চ অপারেশনগুলি করা হয়, এবং এগুলি ডেটা সঠিকভাবে সঞ্চয় এবং দ্রুত অনুসন্ধানের জন্য অত্যন্ত কার্যকরী।

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

নতুন নোড যোগ করার সময়, যদি ট্রি ব্যালেন্সড না থাকে, তবে রোটেশন (rotation) করা হয়। সাধারণত তিন ধরনের রোটেশন হয়:

1. লেফট রোটেশন (Left Rotation)
2. রাইট রোটেশন (Right Rotation)
3. লেফট-রাইট রোটেশন (Left-Right Rotation)
4. রাইট-লেফট রোটেশন (Right-Left Rotation)

২.২ সার্চ (Search)

সার্চ অপারেশনটি BST এর মতোই হয় এবং O(log n) সময়ে সম্পন্ন হয়।

২.৩ ডিলিট (Delete)

একটি নোড মুছে ফেলার সময়, ট্রি আবার ব্যালেন্স করা হয়, যাতে এটি AVL Tree হিসেবে অবশিষ্ট থাকে।

৩. Balanced Binary Tree এর ব্যবহার

৩.১ AVL Tree এর ব্যবহার

• ডেটাবেস সিস্টেম: AVL Tree দ্রুত অনুসন্ধানের জন্য ব্যবহৃত হয়, যেখানে ডেটা সঠিকভাবে সংরক্ষিত থাকে।
• ফাইল সিস্টেম: ফাইল সংরক্ষণের জন্য এবং দ্রুত অ্যাক্সেসের জন্য AVL Tree ব্যবহার করা হয়।
• ইন্ডেক্সিং: ডেটাবেস এবং সার্চ ইঞ্জিনে দ্রুত অনুসন্ধানের জন্য।

৩.২ Balanced Binary Tree এর ব্যবহার

• অ্যালগরিদম: বিভিন্ন অ্যালগরিদম যেমন ট্রি সাইটিং অ্যালগরিদমে ব্যালেন্সড ট্রি ব্যবহার করা হয়।
• মেমরি ব্যবস্থাপনা: স্থান এবং মেমরি দক্ষতার জন্য।
• ডেটা স্ট্রাকচার: স্থানীয়ভাবে ব্যালেন্সড থাকার কারণে ডেটা সঞ্চয়ের জন্য।

৪. উপসংহার

AVL Tree একটি বিশেষ ধরনের Balanced Binary Tree যা দ্রুত ডেটা অনুসন্ধান এবং সঠিকভাবে ডেটা সঞ্চয় করতে সাহায্য করে। এটি বিভিন্ন ক্ষেত্রে যেমন ডেটাবেস সিস্টেম, ফাইল সিস্টেম, এবং অ্যালগরিদমে ব্যবহার করা হয়। AVL Tree এর বৈশিষ্ট্য এবং অপারেশনগুলি ডেটার কার্যকরী পরিচালনার জন্য অত্যন্ত গুরুত্বপূর্ণ।