ট্রি ডেটা স্ট্রাকচার – ৫ [BST: Find maximum and minimum value]

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

Tree Data Structure সিরিজের তৃতীয় পর্বে বাইনারি সার্চ ট্রির insert ও search অপারেশন দেখানো হয়েছিল। চতুর্থ পর্বে BST এর tree traversal দেখানো হয়েছিল। এর মাধ্যমে আমরা এখন BST কে pre-order, in-order ও post-order এ প্রিন্ট করতে শিখেছিলাম। যে কোনো ডেটা স্ট্রাকচার শেখার সময় আরেকটি কমন অপারেশন শেখানো হয়। তা হচ্ছে maximum ও minimum সংখ্যাটাকে খুঁজে বের করা। এটাও যেহেতু একটা সার্চিং অপারেশন তাই একটা Binary Search Tree এর সর্বোচ্চ বা সর্বনিম্ন মানটি search করার complexity হচ্ছে O(log n).

BST এর properties হচ্ছে এর যে কোনো নোডের left subtree এর সবগুলো নোড হবে ঐ নোডের চেয়ে ছোট বা সমান এবং right subtree এর নোডগুলো হবে বড়। এই বৈশিষ্ট্য থেকে কিন্তু খুব সহজেই বুঝা যায় একদম ছোট মানটা Tree এর কোন পজিশনে থাকবে। যেহেতু বামের নোডগুলোর মান ছোট তাই রুট থেকে যদি ক্রমাগত প্রতিটা নোডের left child এ যেতে থাকি তাহলে সর্বশেষ নোডটার মানই সবচেয়ে ছোট। আর সর্বোচ্চ মানের জন্য যেতে হবে প্রতিটা নোডের ডান right child এ।

উপরের ছবিতে দেখো। সবচেয়ে ছোট মানটা (30) আছে left most node এ। আর সর্বোচ্চ মান (70) আছে right most node এ। তাই সর্বনিম্ন মান খুঁজার জন্য আমরা recursively বা লুপ চালিয়ে সর্ববামের node এ চলে যাব। আর বড় মান খুঁজার জন্য যাব সর্বডানের node এ।

Find Maximum value of BST

Maximum ও minimum সংখ্যা বের করার জন্য recursive ও iterative দুই ভাবেই কোড করা যায়। উভয় কোডই দেখব। maximum বের করব recursively আর minimum বের করব iteratively.

node * findMaxRecursive(node *root)
{
    if(root->rightChild==NULL)
        return root;

    return findMaxRecursive(root->rightChild);
}

প্রথমে বেজ কেস চেক করা হচ্ছে। যদি কোনো নোডে গিয়ে দেখা যায় তার right child নাই তার মানে বুঝতে হবে এটাই এই ট্রি এর সবচেয়ে বড় সংখ্যা। তাই যেই নোডে গিয়ে right child পাওয়া যাচ্ছে না সেই নোডটাকেই main function এর কাছে return করা হচ্ছে। আর যদি rightChild==NULL সত্য না হয়, অর্থাৎ right child থাকে তাহলে ঐ rightChild এর অ্যাড্রেসটা দিয়ে এই ফাংশনকে আবার কল করা হচ্ছে। আশা করি বুঝে গেছ। তুমি এবার উপরের কোডটাকে একটু edit করে সর্বনিম্ন মান বের করার জন্য একটা ফাংশন লিখে ফেল।

উল্লেখ্য, এই ফাংশন কিন্তু সর্বনিম্ন মানকে রিটার্ন করছে না। বরং যেই নোডটাতে সর্বনিম্ন মান রয়েছে সেই নোডের memory address রিটার্ন করছে। main function থেকে এই অ্যাড্রেসের মানটাকে প্রিন্ট করতে হবে। তবে তুমি চাইলে এই ফাংশনের return type পয়েন্টার না দিয়ে int-ও দিতে পারো। সেক্ষেত্রে এই নোডের মানটাই main function এর কাছে পাঠিয়ে দিবে।

Find Minimum value of BST

Iterative way -তে একটা BST এর সর্বনিম্ন সংখ্যা বের করতে হবে।

node * findMinIterative(node *root)
{
    if(root==NULL)
        return root;

    while(root->leftChild != NULL)
    {
        root = root->leftChild;
    }

    return root;
}

Function parameter হিসেবে root এর মেমরি অ্যাড্রেস পাঠানো হয়েছে। যদি কোনো empty tree এর সর্বনিম্ন সংখ্যা বের করার জন্য এই ফাংশনকে কল করা হয় তখন ফাংশন বডির ভিতরে শুরুর IF blockটা execute হবে। অর্থাৎ আমাদের রুটের মেমরি অ্যাড্রেস যদি NULL হয় তাহলে এই NULL ই রিটার্ন করা হবে। কিন্তু যদি root==NULL মিথ্যা হয় তাহলে ফাংশনের বাকি অংশ কাজ করবে।

আমাদের উদ্দেশ্য হচ্ছে সর্বনিম্ন সংখ্যা বের করা। ছোট সংখ্যাগুলো যেহেতু ট্রির left subtree তে থাকে তাই লুপ ঘুরিয়ে বারবার ট্রি এর বাম দিনের নোডগুলোতে traverse করা হচ্ছে। while এর condition হিসাবে দেয়া হয়েছে root->leftChild != NULL. অর্থাৎ যদি root এর leftChild এর memory address NULL না হয় তাহলে লুপ ঘুরতে থাকবে। লুপের বডিতে বলা হয়েছে root = root->leftChild; অর্থাৎ root এর যেহেতু leftChild বিদ্যমান তাই root এর মধ্যে assign করা হচ্ছে রুটের left child এর মেমরি লোকেশন। এভাবে একে একে ট্রি এর left most node এ পৌঁছে যাব। Left most node এ আসার পর while এর কন্ডিশন মিথ্যা হয়ে যাবে। কারণ left most node এর leftChild এ কোনো child node থাকবে না। যেহেতু কোনো leftChild থাকবে না তাই leftChild != NULL এটা মিথ্যা হবে, কেননা leftChild = NULL। তখন loop break করবে। এরপর return করবে root এর মেমরি অ্যাড্রেস।

মনে করিয়ে দেয়ার জন্য বলি, এই root কিন্তু ট্রি এর সত্যিকারের রুট না। প্রতিবার লুপ ঘুরাতে কিন্তু এই রুটের মান পরিবর্তন হয়েছে। এটা একটা local variable যার lifetime শুধু এই ফাংশনের ভিতরেই থাকবে। রিটার্ন করার পর main function থেকে নোডের অ্যাড্রেসটা receive করে ঐ অ্যাড্রেসের মাধ্যমে নোডের মানটা প্রিন্ট করতে পারো। আশা করি এটা বুঝতেও কোনো সমস্যা নাই। তুমি এখন maximum সংখ্যাটা বের করার জন্য iterative code লিখে ফেল।

রিকার্সিভ ও ইটারেটিভ উভয় কোড সহ পুরো কোডটা পাওয়া যাবে গিটহাব রিপোজিটরিতে।

আগামী পর্বে Binary Search Tree এর যে কোনো একটা নোড কিভাবে ডিলেট করা যায় সে সম্পর্কে আলোচনা করব।

এই পোস্ট নিয়ে ট্রি এর মোট ৫ টা পোস্ট প্রকাশিত হয়েছে। কিন্তু দুঃখজনক ভাবে তোমাদের কোনো ফিডব্যাক পাই নি। আদৌ লেখাগুলো কোনো কাজে আসছে কিনা বা লেখার স্টাইল ঠিক আছে কিনা বুঝতে পারছি না। পজেটিভ-নেগেটিভ যে কোনো ধরনের মন্তব্য, মতামত পরামর্শ পেলে আমার নিজেকে জাজ করতে সুবিধা হবে। তোমাদের পরামর্শ ও মন্তব্যের অপেক্ষায় রইলাম। ধন্যবাদ। 🙂