সি-তে বাইনারি ট্রি: একটি সম্পূর্ণ শিক্ষানবিস নির্দেশিকা

ইনফরমেটেক ডিজিটাল » অ্যালগরিদম » সি-তে বাইনারি ট্রি: নতুনদের জন্য একটি সম্পূর্ণ নির্দেশিকা

সি-তে বাইনারি ট্রি সম্পর্কিত এই বিস্তৃত নির্দেশিকায় আপনাকে স্বাগতম। এই প্রবন্ধে, আমরা বাইনারি ট্রির মূল বিষয়গুলি এবং সি প্রোগ্রামিং ভাষায় কীভাবে সেগুলি বাস্তবায়ন করতে হয় তা অন্বেষণ করব। আপনি যদি প্রোগ্রামিংয়ে নতুন হন বা আপনার সি দক্ষতা উন্নত করতে চান, তাহলে এই নির্দেশিকাটি আপনার জন্য।

বাইনারি ট্রি কম্পিউটার বিজ্ঞানের একটি মৌলিক ডেটা স্ট্রাকচার এবং এটি বিভিন্ন ধরনের অ্যাপ্লিকেশনে ব্যবহৃত হয়। এটি কীভাবে কাজ করে এবং কীভাবে এটি প্রয়োগ করতে হয় তা বুঝলে, আপনি আরও দক্ষতার সাথে ও সুন্দরভাবে জটিল সমস্যা সমাধান করতে পারবেন।

এই নিবন্ধ জুড়ে আমরা বাইনারি ট্রি-এর মৌলিক বিষয়গুলো নিয়ে আলোচনা করব, যার মধ্যে রয়েছে এর গঠন, নোড সংযোজন ও অপসারণ, ট্রাভার্সাল এবং এলিমেন্ট সার্চ। আমরা সি প্রোগ্রামিং ভাষায় কিছু বাস্তব উদাহরণও দেব , যাতে আপনারা দেখতে পারেন এই ধারণাগুলো বাস্তবে কীভাবে প্রয়োগ করা হয়।

চল শুরু করা যাক!

বাইনারি ট্রি কি?

বাইনারি ট্রি হলো আন্তঃসংযুক্ত নোডের সমন্বয়ে গঠিত হায়ারার্কিকাল ডেটা স্ট্রাকচার। প্রতিটি নোডে সর্বাধিক দুটি চাইল্ড নোড থাকতে পারে: একটি বাম দিকে এবং একটি ডান দিকে। এই দুই-শাখার কাঠামোই বাইনারি ট্রিকে অন্যান্য ডেটা স্ট্রাকচার থেকে আলাদা করে।

একটি বাইনারি ট্রিতে, প্রথম নোডটিকে রুট নোড বলা হয়। চাইল্ড নোডগুলিকে চাইল্ড নোড বলা হয়, এবং চাইল্ডবিহীন নোডগুলিকে লিফ নোড বলা হয়। একই স্তরের নোডগুলিকে ভাইবোন নোড বলা হয়।

বাইনারি গাছের সুবিধা

দক্ষ ডেটা স্টোরেজ এবং অনুসন্ধানের ক্ষেত্রে বাইনারি ট্রি বেশ কিছু সুবিধা প্রদান করে। কিছু প্রধান সুবিধার মধ্যে রয়েছে:

1. দক্ষ অনুসন্ধানবাইনারি ট্রি রানটাইমে উপাদানগুলিকে লিঙ্কড তালিকার মতো অন্যান্য ডেটা স্ট্রাকচারের তুলনায় দ্রুত অনুসন্ধান করতে দেয়। এটি গাছের শ্রেণিবিন্যাস কাঠামো এবং ডেটা সেটকে দ্রুত বিভাজন করার ক্ষমতার কারণে।
2. নমনীয় সন্নিবেশ এবং অপসারণবাইনারি ট্রি নোড সন্নিবেশ এবং মুছে ফেলার ক্রিয়াকলাপের সাথে অত্যন্ত অভিযোজিত। অ্যারের মতো স্ট্যাটিক ডেটা স্ট্রাকচারের বিপরীতে, বাইনারি ট্রিগুলি বৃদ্ধি পেতে পারে এবং তাদের কাঠামো গতিশীলভাবে পরিবর্তন করতে পারে।
3. শ্রেণিবদ্ধ সম্পর্কের প্রতিনিধিত্ববাইনারি ট্রিগুলি উপাদানগুলির মধ্যে শ্রেণিবদ্ধ সম্পর্ক উপস্থাপনের জন্য বিশেষভাবে কার্যকর। উদাহরণস্বরূপ, একটি ফাইল ডিরেক্টরি কাঠামোতে, প্রতিটি ডিরেক্টরি গাছের মধ্যে একটি নোড হিসাবে উপস্থাপন করা যেতে পারে, সাবডিরেক্টরি এবং ফাইলগুলিকে এর চাইল্ড নোড হিসাবে উপস্থাপন করা যেতে পারে।

একটি বাইনারি গাছের গঠন

সি-তে বাইনারি ট্রি বাস্তবায়নে ডুব দেওয়ার আগে, তাদের মৌলিক কাঠামো বোঝা গুরুত্বপূর্ণ। একটি বাইনারি ট্রির প্রতিটি নোডে একটি মান থাকে এবং এর বাম এবং ডান চাইল্ড নোডের রেফারেন্স থাকে, যদি থাকে।

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

বাইনারি নোড
বীরত্ব
বাম নোড
ডান নোড

প্রতিটি নোড যেকোনো ধরণের ডেটা সংরক্ষণ করতে পারে, যেমন পূর্ণসংখ্যা, অক্ষর, অথবা আরও জটিল কাঠামো। মূল নোড হল গাছের শুরুর বিন্দু, এবং এটি থেকে আমরা অন্যান্য সমস্ত নোড অ্যাক্সেস করতে পারি।

সি-তে বাইনারি ট্রি বাস্তবায়ন করা

এখন যেহেতু বাইনারি ট্রি সম্পর্কে আমাদের একটি প্রাথমিক ধারণা হয়েছে, তাই C প্রোগ্রামিং ভাষায় এগুলো বাস্তবায়ন করার সময় এসেছে । এরপরে, আমরা দেখব কিভাবে C-তে একটি বাইনারি ট্রি কাঠামো ঘোষণা এবং ব্যবহার করতে হয়।

বাইনারি ট্রি স্ট্রাকচার ঘোষণা করা

C তে, আমরা একটি কাঠামো এবং পয়েন্টার ব্যবহার করে একটি বাইনারি গাছের কাঠামো ঘোষণা করতে পারি। কাঠামোর মৌলিক ঘোষণা এখানে দেওয়া হল:

struct NodoArbol {
    int valor;
    struct NodoArbol* izquierdo;
    struct NodoArbol* derecho;
};

এই কাঠামোতে, valor নোডে সংরক্ষিত মান প্রতিনিধিত্ব করে, এবং izquierdo y derecho যথাক্রমে বাম এবং ডান চাইল্ড নোডের দিকে নির্দেশক।

একটি নতুন নোড তৈরি করা হচ্ছে

বাইনারি ট্রিতে একটি নতুন নোড তৈরি করতে, আমাদের নোডের জন্য মেমরি বরাদ্দ করতে হবে এবং এর মান সেট করতে হবে। এখানে একটি C ফাংশন রয়েছে যা একটি নতুন নোড তৈরি করে:

struct NodoArbol* crearNodo(int valor) {
    struct NodoArbol* nodo = (struct NodoArbol*)malloc(sizeof(struct NodoArbol));
    nodo->valor = valor;
    nodo->izquierdo = NULL;
    nodo->derecho = NULL;
    return nodo;
}

ফাংশন malloc এটি নোডে গতিশীল মেমরি বরাদ্দ করতে ব্যবহৃত হয়। এরপর আমরা নোডের মান সেট করি এবং তৈরি নোডটি ফেরত দেই।

নোড ঢোকানো হচ্ছে

বাইনারি ট্রিতে নোড সন্নিবেশ একটি মৌলিক প্রক্রিয়া। নোড মানের উপর ভিত্তি করে সঠিক অবস্থানে গাছে নতুন উপাদান যোগ করার অনুমতি দেয়। বাইনারি ট্রিতে নোড সন্নিবেশ করার জন্য নিচে একটি C ফাংশন দেওয়া হল:

struct NodoArbol* insertarNodo(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL) {
        return crearNodo(valor);
    }

    if (valor < raiz->valor) {
        raiz->izquierdo = insertarNodo(raiz->izquierdo, valor);
    } else if (valor > raiz->valor) {
        raiz->derecho = insertarNodo(raiz->derecho, valor);
    }

    return raiz;
}

এই ফাংশনটি গাছের মূলের দিকে একটি পয়েন্টার এবং সন্নিবেশ করানো নোডের মান গ্রহণ করে। যদি root null হয়, তাহলে এর অর্থ হল ট্রিটি খালি এবং আমরা root-এ একটি নতুন নোড তৈরি করব। অন্যথায়, আমরা নোডের মান রুটের মানের সাথে তুলনা করব এবং সিদ্ধান্ত নেব যে নোডটি বাম দিকে বা ডান দিকে সন্নিবেশ করানো হবে কিনা।

নোড মুছে ফেলা হচ্ছে

বাইনারি ট্রিতে নোড মুছে ফেলা একটু বেশি জটিল হতে পারে। এটি বিভিন্ন ক্ষেত্রে নির্ভর করে, যেমন যে নোডটি মুছে ফেলা হবে তাতে সন্তান আছে কিনা। বাইনারি ট্রিতে নোড মুছে ফেলার জন্য নিচে একটি C ফাংশন দেওয়া হল:

struct NodoArbol* eliminarNodo(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL) {
        return raiz;
    }

    if (valor < raiz->valor) {
        raiz->izquierdo = eliminarNodo(raiz->izquierdo, valor);
    } else if (valor > raiz->valor) {
        raiz->derecho = eliminarNodo(raiz->derecho, valor);
    } else {
        if (raiz->izquierdo == NULL) {
            struct NodoArbol* temp = raiz->derecho;
            free(raiz);
            return temp;
        } else if (raiz->derecho == NULL) {
            struct NodoArbol* temp = raiz->izquierdo;
            free(raiz);
            return temp;
        }

        struct NodoArbol* sucesor = encontrarSucesor(raiz->derecho);
        raiz->valor = sucesor->valor;
        raiz->derecho = eliminarNodo(raiz->derecho, sucesor->valor);
    }

    return raiz;
}

এই ফাংশনে, আমরা পরীক্ষা করি যে নোডের মান বর্তমান রুটের মানের চেয়ে কম, বেশি, নাকি সমান। মামলার উপর নির্ভর করে, আমরা নিম্নলিখিত পদক্ষেপগুলি সম্পাদন করি:

• যদি মানটি ছোট হয়, আমরা গাছের বাম দিকে যাব।
• যদি মান বেশি হয়, আমরা গাছের ডানদিকে যাব।
• যদি মান সমান হয়, তাহলে আমরা নোডের নিকটতম উত্তরসূরী (ডান সাবট্রির সবচেয়ে ছোট নোড) খুঁজে বের করব এবং এটিকে বর্তমান নোড দিয়ে প্রতিস্থাপন করব। তারপর আমরা ডান সাবট্রি থেকে উত্তরসূরীটি সরিয়ে ফেলি।

বাইনারি ট্রিতে ট্রাভার্সাল

ট্র্যাভার্সাল হলো এমন একটি অপারেশন যা আমাদের একটি নির্দিষ্ট ক্রমে একটি বাইনারি গাছের সমস্ত নোড পরিদর্শন করতে সাহায্য করে। তিন ধরণের ট্যুর সাধারণ:

ক্রমানুসারে ট্রাভার্সাল : প্রথমে বাম সাবট্রি, তারপর বর্তমান নোড এবং সবশেষে ডান সাবট্রি পরিদর্শন করে। নিচে একটি C ফাংশন দেওয়া হলো যা একটি বাইনারি ট্রির ক্রমানুসারে ট্রাভার্সাল সম্পাদন করে:

void inOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        inOrden(raiz->izquierdo);
        printf("%d ", raiz->valor);
        inOrden(raiz->derecho);
    }
}

প্রি-অর্ডার ট্রাভার্সাল : প্রথমে বর্তমান নোড, তারপর বাম সাবট্রি এবং সবশেষে ডান সাবট্রি পরিদর্শন করে। নিচে একটি C ফাংশন দেওয়া হলো যা একটি বাইনারি ট্রির প্রি-অর্ডার ট্রাভার্সাল সম্পাদন করে:

void preOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        printf("%d ", raiz->valor);
        preOrden(raiz->izquierdo);
        preOrden(raiz->derecho);
    }
}

পোস্ট-অর্ডার ট্রাভার্সাল : প্রথমে বাম সাবট্রি, তারপর ডান সাবট্রি এবং সবশেষে বর্তমান নোড পরিদর্শন করে। নিচে একটি C ফাংশন দেওয়া হলো যা একটি বাইনারি ট্রির পোস্ট-অর্ডার ট্রাভার্সাল সম্পাদন করে:

void postOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        postOrden(raiz->izquierdo);
        postOrden(raiz->derecho);
        printf("%d ", raiz->valor);
    }
}

উপাদানগুলির জন্য অনুসন্ধান করুন

বাইনারি ট্রিতে উপাদান অনুসন্ধান করলে আমরা ডেটা স্ট্রাকচারের মধ্যে একটি নির্দিষ্ট মান দ্রুত খুঁজে পেতে পারি। বাইনারি ট্রিতে একটি উপাদান অনুসন্ধান করার জন্য এখানে একটি C ফাংশন রয়েছে:

struct NodoArbol* buscarElemento(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL || raiz->valor == valor) {
        return raiz;
    }

    if (valor < raiz->valor) {
        return buscarElemento(raiz->izquierdo, valor);
    } else {
        return buscarElemento(raiz->derecho, valor);
    }
}

এই ফাংশনটি বাইনারি ট্রিতে একটি পুনরাবৃত্ত অনুসন্ধান সম্পাদন করে। যদি বর্তমান নোডের মান অনুসন্ধান করা মানের সমান হয়, তাহলে নোডটি ফেরত পাঠানো হবে। অন্যথায়, মানের উপর ভিত্তি করে বাম বা ডান সাবট্রি অনুসন্ধান করা হয় এবং মানটি পাওয়া না যাওয়া বা একটি নাল নোডে পৌঁছানো পর্যন্ত প্রক্রিয়াটি পুনরাবৃত্তি করা হয়।

সি-তে বাইনারি ট্রি বাস্তবায়নের উদাহরণ

এখন যেহেতু আমরা বাইনারি ট্রির মূল বিষয়গুলি এবং C তে সেগুলি কীভাবে বাস্তবায়ন করতে হয় তা কভার করেছি, আসুন কিছু ব্যবহারিক উদাহরণ দেখি।

উদাহরণ ১: একটি বাইনারি ট্রি তৈরি করা

ধরুন আমরা নিম্নলিখিত মানগুলির সাথে একটি বাইনারি ট্রি তৈরি করতে চাই: 10, 5, 15, 3, 7, 13, 18। C তে আমরা এটি কীভাবে করতে পারি তা এখানে দেওয়া হল:

int main() {
    struct NodoArbol* raiz = NULL;

    raiz = insertarNodo(raiz, 10);
    raiz = insertarNodo(raiz, 5);
    raiz = insertarNodo(raiz, 15);
    raiz = insertarNodo(raiz, 3);
    raiz = insertarNodo(raiz, 7);
    raiz = insertarNodo(raiz, 13);
    raiz = insertarNodo(raiz, 18);

    return 0;
}

এই উদাহরণে, আমরা গাছের মূলে একটি পয়েন্টার তৈরি করব এবং তারপর ফাংশনটি ব্যবহার করব insertarNodo গাছে মান যোগ করতে।

উদাহরণ ২: বাইনারি ট্রির ইন-অর্ডার ট্রাভার্সাল

বাইনারি ট্রির মান ক্রমানুসারে প্রিন্ট করার জন্য, আমরা ফাংশনটি কল করতে পারি inOrden নিম্নরূপ:

int main() {
    // Crear el árbol binario

    printf("Recorrido en orden: ");
    inOrden(raiz);
    printf("\n");

    return 0;
}

এই উদাহরণটি গাছের মানগুলিকে আরোহী ক্রমে মুদ্রণ করবে।

প্রায়শই জিজ্ঞাসিত প্রশ্নাবলী

২. বাইনারি ট্রি এবং বাইনারি সার্চ ট্রির মধ্যে পার্থক্য কী?

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

২. বাইনারি ট্রিতে কি ডুপ্লিকেট মান সহ নোড থাকতে পারে?

হ্যাঁ, একটি বাইনারি ট্রিতে ডুপ্লিকেট মান সহ নোড থাকা সম্ভব। তবে, বাইনারি ট্রির বাস্তবায়ন এবং নির্দিষ্ট নিয়মের উপর নির্ভর করে, ডুপ্লিকেট নোডগুলি মোকাবেলা করার বিভিন্ন উপায় থাকতে পারে। কিছু বাস্তবায়ন ডুপ্লিকেটের অনুমতি দিতে পারে এবং যেকোনো ক্রমে সংরক্ষণ করতে পারে, অন্যদের জন্য ডুপ্লিকেট মানগুলিকে বিশেষভাবে পরিচালনা করতে বা বাতিল করতে হতে পারে।

৩. আমি কিভাবে একটি বাইনারি ট্রি থেকে একটি নির্দিষ্ট নোড অপসারণ করতে পারি?

বাইনারি ট্রি থেকে একটি নির্দিষ্ট নোড অপসারণ করতে, আপনাকে এই পদক্ষেপগুলি অনুসরণ করতে হবে:

1. ট্রি সার্চ ব্যবহার করে আপনি যে নোডটি মুছে ফেলতে চান তা খুঁজুন।
2. নির্মূলের বিভিন্ন ঘটনা বিবেচনা করুন:
   • যদি নোডটির কোন সন্তান না থাকে, তাহলে আপনি কেবল এটি মুছে ফেলতে পারেন এবং এর মেমরি মুক্ত করতে পারেন।
   • যদি নোডটিতে শুধুমাত্র একটি চাইল্ড থাকে, তাহলে আপনি নোডটিকে তার চাইল্ড দিয়ে প্রতিস্থাপন করতে পারেন।
   • যদি নোডটিতে দুটি সন্তান থাকে, তাহলে আপনাকে অবশ্যই নিকটতম উত্তরসূরী (ডান সাবট্রির সবচেয়ে ছোট নোড) খুঁজে বের করতে হবে এবং মুছে ফেলা নোডের মানটি উত্তরসূরী এর মান দিয়ে প্রতিস্থাপন করতে হবে। তারপর গাছ থেকে উত্তরাধিকারীটি সরিয়ে ফেলুন।
3. সঠিক গাছের কাঠামো বজায় রাখার জন্য প্রয়োজন অনুসারে লিঙ্ক এবং পয়েন্টারগুলি সামঞ্জস্য করে।

৪. পূর্ণ বাইনারি ট্রি কী?

একটি পূর্ণ বাইনারি ট্রি হল একটি বিশেষ ধরণের বাইনারি ট্রি যেখানে সমস্ত স্তর, সম্ভবত শেষ স্তরটি ছাড়া, সম্পূর্ণরূপে পূর্ণ থাকে এবং শেষ স্তরের নোডগুলি যতটা সম্ভব বাম দিকে অবস্থিত থাকে। এর মানে হল যে সমস্ত নোডের দুটি সন্তান আছে, সম্ভবত শেষ স্তরের নোডগুলি ছাড়া, যার একটি সন্তান থাকতে পারে বা নাও থাকতে পারে।

৫. একটি বাইনারি গাছের উচ্চতা কত?

একটি বাইনারি গাছের উচ্চতা হল মূল থেকে পাতা পর্যন্ত দীর্ঘতম পথের দৈর্ঘ্য। অন্য কথায়, এটি গাছের মূল এবং যেকোনো পাতার মধ্যে সর্বাধিক সংখ্যক প্রান্ত। উচ্চতা পরিমাপ করা হয় স্তরের সংখ্যার ভিত্তিতে, তাই শুধুমাত্র একটি নোড বিশিষ্ট একটি গাছের উচ্চতা 0 হয় এবং একটি খালি গাছের কোনও উচ্চতা থাকে না।

৬. আমার প্রোগ্রামগুলিতে কখন বাইনারি ট্রি ব্যবহার করা উচিত?

বাইনারি ট্রি বিভিন্ন পরিস্থিতিতে কার্যকর। কিছু সাধারণ ক্ষেত্রে যেখানে আপনি বাইনারি ট্রি ব্যবহার করতে পারেন:

• দক্ষ উপাদান অনুসন্ধান: যদি আপনার ডেটা স্ট্রাকচারে দ্রুত উপাদানগুলি অনুসন্ধান করার প্রয়োজন হয়, তাহলে একটি বাইনারি ট্রি ডেটাতে দক্ষ অ্যাক্সেস প্রদান করতে পারে।
• শ্রেণিবদ্ধ সম্পর্ক উপস্থাপন করা: বাইনারি ট্রি শ্রেণিবদ্ধ সম্পর্ক উপস্থাপনের জন্য আদর্শ, যেমন একটিতে ডিরেক্টরি কাঠামো ফাইল সিস্টেম.
• ডেটা বাছাই: লগারিদমিক সময়ে ডেটা দক্ষতার সাথে সাজানো এবং অনুসন্ধান, সন্নিবেশ এবং মুছে ফেলার জন্য আপনি বাইনারি অনুসন্ধান ট্রি ব্যবহার করতে পারেন।

আপনার প্রোগ্রামগুলিতে বাইনারি ট্রি ব্যবহার করার সিদ্ধান্ত নেওয়ার আগে আপনার প্রয়োজনীয়তাগুলি মূল্যায়ন করতে এবং তাদের ক্রিয়াকলাপের জটিলতা বিবেচনা করতে ভুলবেন না।

উপসংহার

এই বিস্তৃত নির্দেশিকাটিতে, আমরা C-তে বাইনারি গাছের মৌলিক ধারণাগুলি অন্বেষণ করেছি। আমরা তাদের গঠন, নোডগুলি কীভাবে সন্নিবেশ করাতে এবং অপসারণ করতে হয়, ট্র্যাভার্সাল সম্পাদন করতে হয় এবং বাইনারি গাছের উপাদানগুলি অনুসন্ধান করতে হয় সে সম্পর্কে শিখেছি।

আমরা আশা করি এই নির্দেশিকাটি আপনাকে বাইনারি ট্রি এবং C তে সেগুলি কীভাবে বাস্তবায়ন করতে হয় সে সম্পর্কে একটি দৃঢ় ধারণা দিয়েছে। বাইনারি ট্রি হল বহুমুখী এবং শক্তিশালী ডেটা স্ট্রাকচার যা আপনাকে প্রোগ্রামিংয়ে বিস্তৃত সমস্যা সমাধানে সহায়তা করতে পারে।

সি-তে বাইনারি ট্রি সম্পর্কে আপনার বোধগম্যতা আরও জোরদার করার জন্য প্রদত্ত উদাহরণগুলি অনুশীলন এবং পরীক্ষা-নিরীক্ষা করতে ভুলবেন না। আপনার সফ্টওয়্যার শেখার এবং উন্নয়নের যাত্রায় শুভকামনা!