ট্রি ডেটা স্ট্রাকচার – ৩ [বাইনারি সার্চ ট্রি – BST]

Post updated on 31st January, 2017 at 04:16 pm

ট্রি ডেটা স্ট্রাকচার সিরিজের প্রথম পর্বে ট্রি এর ব্যাসিক ধারণা দেয়া হয়েছিল। দ্বিতীয় পর্বে বেশ কয়েক রকমের ট্রি সম্পর্কে আলোচনা করা হয়েছে। এই পর্বে সরাসরি চলে যাব BST বা Binary Search Tree এর implementation এ।

BST – Binary Search Tree

বাইনারি সার্চ অ্যালগরিদম শেখার সময় আমরা দেখেছি, যদি একটা অ্যারের মানগুলো সর্টেড থাকে তাহলে তাতে বাইনারি সার্চ অ্যালগরিদম ব্যবহার করে কোনো ডেটা সার্চ করলে এর রান টাইম হয় O(log n). Binary Search Algorithm এ যেমন আমরা অ্যারের ঠিক মধ্যখানের ডেটার সাথে সার্চিং আইটেমের তুলনা করে সিদ্ধান্ত নিই যে কোন অংশকে বাদ দিব। BST এর ক্ষেত্রেও একই ধরনের একটা আইডিয়া কাজ করবে।

অ্যারের মত এই ট্রি থেকেও কোনো একটা মান সার্চ করতে O(log n) running time দরকার হবে। তাই এই ট্রি এর নাম দেয়া হয়েছে বাইনারি সার্চ ট্রি।

বাইনারি সার্চ ট্রির ডেটাগুলো একটা বিশেষ ফ্যাশনে সর্টেড হয়ে থাকে। তা হচ্ছে যে কোনো নোডের left sub-tree এর সবগুলো নোডের মান হবে ঐ নোডের চেয়ে ছোট বা সমান। আর right sub-tree এর সবগুলো নোডের মান হবে ঐ নোডের মানের চেয়ে বড়। এভাবে ডেটাগুলো সাজানো থাকলে worst case এর ক্ষেত্রেও O(log n) টাইমে যে কোনো ডেটা সার্চ করা সম্ভব।

এই সর্টেড হয়ে থাকাটা যেমন রুটের ক্ষেত্রে প্রযোজ্য, একই ভাবে অন্যান্য সকল নোডের ক্ষেত্রেও প্রযোজ্য। একটা বাইনারি সার্চ ট্রির root এর বাম পাশের সকল নোডগুলো হবে রুটের মানের চেয়ে ছোট বা সমান। ডানপাশের সকল নোডের মান হবে রুটের মানের চেয়ে বড়। একই ভাবে রুটের বাম পাশের চাইল্ডের ক্ষেত্রেও এটা সত্য হবে। এই চাইল্ডের যদি আরো চাইল্ড থাকে তাহলে দেখা যাবে এই চাইলের বামের সকল নোডগুলো এর চেয়ে ছোট বা সমান। ডানেরগুলো বড়। BST এর দারুণ একটা visualization দেখতে পারো এখান থেকে।  কয়েকটা integer value ইনসার্ট করে নিও।

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

Prerequisites: কোড করার জন্য নিচের টপিকগুলো সম্পর্কে ধারনা থাকতে হবে। তা না হলে এই পোস্টের বাকি অংশ বুঝতে সমস্যা হবে।

• Structure
• Recursion
• Linked List

Operations of Tree

অন্যান্য ডেটা স্ট্রাকচারের মত ট্রি এরও কিছু ব্যাসিক অপারেশন রয়েছে। সেগুলো হচ্ছেঃ

• Insert – নতুন কোনো child ট্রিতে যুক্ত করা
• Search – কোনো একটা item ট্রিতে সার্চ করে দেখা
• Delete – কোনো একটা child ট্রি থেকে মুছে দেয়া
• In-order Traversal – প্রথমে left sub-tree ভিজিট করবে, এরপর root, অতঃপর right sub-tree ভিজিট করবে
• Pre-order Traversal – প্রথমেই root ভিজিট হবে, এরপর যথাক্রমে left sub-tree ও right sub-tree ভিজিট হবে
• Post-order Traversal – প্রথমে left sub-tree, এরপর ভিজিট হবে right sub-tree. সবার শেষে ভিজিট হবে root.

Implementation of Binary Search Tree – BST

Create a node

এটা যেহেতু বাইনারি ট্রি তাই প্রতিটা নোডে সর্বোচ্চ দুটি চাইল্ড থাকতে পারে। সুতরাং একটা স্ট্রাকচার বানাতে হবে যাতে ডেটা হিসাবে থাকবে একটা int type এর variable. আর child node এর মেমরি অ্যাড্রেস স্টোর করার জন্য দুটি pointer type variable.

Main function এর বাইরে globally একটা স্ট্রাকচার বানানো হল এবং root declare করা হল।

typedef struct tree
{
    int number;
    struct tree *leftChild;
    struct tree *rightChild;

} node;
node *root=NULL;

আপাতত রুটের মান NULL করে রাখা হয়েছে। insert করার function এর ভিতরে রুটের জন্য memory allocate করা হবে।

Insert a node

ইনসার্টের জন্য একটা ফাংশন লিখা হবে। ফাংশন বডির শুরুতেই একটা temporary node এর জন্য memory allocate করা হবে। ফাংশনের প্যারামিটারে পাঠানো ভ্যালুটা নতুন নোডের number ভ্যারিয়েবলে assign করে child দুটির মান NULL করে রাখা হবে। কারণ আমরা এই নোডের ব্যাপারেই এই মুহুর্তে আগ্রহী। এর বাচ্চাকাচ্চা নেয়ার চিন্তা আপাতত নাই।

void insertNode(int value)
{
    node *tempNode;
    node *currentNode=NULL;
    node *parentNode=NULL;

    tempNode = (node *) malloc(sizeof(node));
    tempNode->number = value;

    //For the very first call
    if(root==NULL)
    {
        root = tempNode;
    }
    else
    {
        currentNode = root;
        parentNode = NULL;

        while(1)
        {
            parentNode = currentNode;

            if(value <= parentNode->number)
            {
                currentNode = currentNode->leftChild;

                if(currentNode==NULL)
                {
                    parentNode->leftChild = tempNode;
                    return;
                }
            }
            else
            {
                currentNode = currentNode->rightChild;

                if(currentNode==NULL)
                {
                    parentNode->rightChild = tempNode;
                    return;
                }
            }

        }
    }
}

এরপর চেক করা হবে রুট নোডের মান NULL কিনা। প্রথমবার যখন এই ফাংশনকে কল করা হবে তখন এই IF সত্য হবে। তখন এই নতুন বানানো নোডটাকেই রুট নোড হিসাবে assign করে দেয়া হচ্ছে। আর যদি এই IF সত্য না হয় তাহলে কিছু হিসাব নিকাশ করে নোডটা ট্রি এর সাথে জুড়ে দিতে হবে। যেহেতু কিছু শর্ত (left child এর মান ছোট বা সমান, right child এর মান বড়) মানতে হবে তাই এই নোডটাকে যে কোনো নোডের বাচ্চা হিসেবে জুড়ে দেয়া যাবে না।

ELSE block এর শুরুতে currentNode আর parentNode নামের দুটি নোডে NULL assign করা হয়েছে। আমাদের উদ্দেশ্য হচ্ছে রুট থেকে ট্রিতে ট্রাভার্স করা শুরু করব। ফাংশন প্যারামিটার হিসাবে যেই ভ্যালু পাঠানো হয়েছে সেই ভ্যালুর সাথে প্রতিটা নোডের ভ্যালুকে চেক করব। যদি দেখা যায় value এর মান ঐ নোডের number এর চেয়ে ছোট বা সমান তাহলে ঐ নোডের leftChild এ যেতে হবে। leftChild এ যাওয়ার পর এটাই কিন্তু আমাদের currentNode হয়ে যাবে। এবার আবার চেক করব value এই নতুন হওয়া currentNode এর number এর চেয়ে ছোট নাকি বড়। ছোট বা সমান হলে আবার এই নোডের leftChild এ যাব, অন্যথায় rightChild এ যাব। leftChild এর মাধ্যমে কোনো একটা নোডে যাওয়ার পর যদি দেখা যায় ঐ নোডটা (currentNode) NULL (কোডের ২৮ নাম্বার লাইন) তাহলে কী বুঝব? বুঝব parentNode আসলে একটা leaf. এই নোডের এখনো কোনো বাচ্চাকাচ্চা হয় নাই। parentNode এর leftChild এর মেমরি অ্যাড্রেস hold করছে আমাদের currentNode. এই নোড তাই এখনো NULL. আমরা যেই নতুন নোডটা বানিয়েছি সেটাই হবে parentNode নোডের বাম পাশের বাচ্চা বা leftChild. আর যদি parentNode এর rightChild এর মেমরি অ্যাড্রেস NULL পাওয়া যায় (কোডের ৩৮ নাম্বার লাইন) তখন নতুন নোডের memory address-কে পয়েন্ট করবে parentNode এর rightChild.

যতক্ষণ পর্যন্ত কোনো NULL node পাওয়া না যাবে ততক্ষণ লুপ ঘুরতে থাকবে। কোনো নোডের child এর মেমরি অ্যাড্রেস NULL পাওয়া গেলে নতুন নোডটাকে সেখানে উপরের মত করে জুড়ে দিয়ে ফাংশনের কাজ return; কীওয়ার্ডের এর মাধ্যমে শেষ করতে হবে।

এভাবে যদি কোনো একটা ট্রিতে মান ইনসার্ট হতে থাকে তাহলে সব সময় যে কোনো নোডের leftChild এর number এর মান সেই নোডের চেয়ে ছোট বা সমান হবে এবং rightChild এর number এর মান বড় হবে।

ফাংশনের কোডটা বেশ বড়। নিজে হাতে কোড না লিখে কপি-পেস্ট করে রান করলে কোডগুলো বুঝতে সমস্যা হবে। তাই পরামর্শ রইলো প্রয়োজনে দেখে দেখে নিজ হাতে টাইপ করার। এতে প্রতি লাইন বাই লাইন কোড বুঝতে সুবিধা হবে।

Search on BST

উপরের এত আয়োজন শুধু আমাদের ডেটাগুলোকে sorted রাখার জন্য। অ্যারেতে ডেটা ইনসার্ট করা সহজ। কিন্তু একটা সর্টেড অ্যারেতে ডেটা ইনসার্ট করে সেটাকে সর্ট করা কিন্তু বেশ costly. তোমাকে অ্যারের নির্দিষ্ট ইনডেক্স খুঁজে বের করতে হবে যেখানে তোমার নতুন ডেটা ইনসার্ট করতে হবে। এরপর সেই ইনডেক্স থেকে অ্যারের শেষ পর্যন্ত সবগুলো ইনডেক্সের ডেটাগুলোকে এক ইনডেক্স করে ডানে সরিয়ে ফাঁকা হওয়া ইনডেক্সে নতুন মান assign করতে হবে। Worst case এর ক্ষেত্রে (যদি অ্যারের শুরুতে কোনো মান ইনসার্ট করার দরকার হয়) শুধু সর্ট করার জন্যেই O(n) সময় লাগবে। এরপর সার্চের জন্য ধরো আরো O(log n). এই সময়টা বাঁচানোর জন্যেই BST. সর্ট করতে worst case এর ক্ষেত্রেও সময় লাগছে O(log n). কারণ আমরা সব ডেটাকে চেক করছি না বা সরাচ্ছি না। প্রতি iteration এ ডেটার পরিমাণ অর্ধেক হয়ে যাচ্ছে। অর্ধেক হতে হতে এক পর্যায়ে গিয়ে আমাদের নতুন ডেটা ইনসার্ট হয়। তাই অ্যারের O(n) এর তুলনায় এর efficiency অনেক ভাল (O(log n)).

Insert করার ফাংশন বুঝে গিয়ে থাকলে সার্চ করার ফাংশনও বুঝবা। একই আইডিয়া কাজে লাগিয়ে প্রতি iteration এ ক্ষুদ্র থেকে ক্ষুদ্রতর sub-tree তে ট্রাভার্স করে আমাদের কাংক্ষিত আইটেম খুঁজে বের করব।

void searchOnTree(int value)
{
    node *currentNode = root;
    int flag = 0;

    while(1)
    {
        if(value == currentNode->number)
        {
            flag = 1;
            break;
        }
        else if(value<=currentNode->number)
            currentNode = currentNode->leftChild;
        else
            currentNode = currentNode->rightChild;

        if(currentNode==NULL)
            break;

    }

    if(flag==1)
        printf("\n%d is found on Tree.\n\n", currentNode->number);
    else
        printf("\n%d is not found on Tree.\n\n", value);
}

root node থেকে সবগুলো নোডে ট্রাভার্স করব, যতক্ষণ না পর্যন্ত আইটেম পাওয়া যায় এবং কোনো নোডের মেমরি অ্যাড্রেস NULL না হয়। যদি নোডের number ও value সমান হয় তাহলে flag = 1 করে লুপ ব্রেক করতে হবে। লুপের বাইরে flag এর মানের উপর ভিত্তি করে decision নেয়া হচ্ছে value-টা ট্রিতে পাওয়া গেছে কিনা।

লুপের ভিতরে যদি কোনো একটা স্টেজে currentNode->number==value না হয় তাহলে চেক করতে হবে value টা নোডের number এর চেয়ে ছোট নাকি বড়। যদি value ছোট বা সমান হয় তাহলে ইনসার্টের মতই currentNode এর leftChild এ গিয়ে খুঁজে দেখতে হবে, অন্যথায় rightChild এ গিয়ে খুঁজতে হবে। কোনো একটা পর্যায়ে গিয়ে যদি কোনো নোডের অ্যাড্রেস হিসাবে NULL value পাওয়া যায় তাহলে বুঝতে হবে value-টা ট্রিতে অনুপস্থিত। তখন লুপ ব্রেক করে ফাংশনের কাজ শেষ করতে হবে।

সম্পূর্ণ কোডটি পাওয়া যাবে আমার গিটহাব রিপোজিটরিতে।

ইনসার্ট আর সার্চ পর্যন্তই রইলো। আগামী পর্বে দেখানো হবে Tree Traversal. একই সাথে দেখানো হবে পুরো ট্রি-টা বিভিন্ন অর্ডারে কিভাবে প্রিন্ট করা যায়।