ট্রি ডেটা স্ট্রাকচার

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

আজকের টপিক হচ্ছে বাইনারি সার্চ ট্রি এর যে কোনো একটা নোড কিভাবে delete করা যায়। তুমি যেহেতু লিংকড লিস্ট সম্পর্কে ভাল ধারণা রাখো তাই এই টপিকটা তোমার বুঝতে খুব বেশি সমস্যা হবে না। যদি লেখাটা বুঝতে সমস্যা বোধ করো তাহলে লিংকড লিস্টের উপর লেখা পোস্টগুলো দেখে আসতে পারো।

লিংকড লিস্ট ছিল Linear Data Structure. তাই লিস্টের মাঝ থেকে কোনো একটা নোড ডিলেট করতে চাইলে তার আগের নোডের সাথে পরের নোডের লিংক করে দিলেই কাজ হয়ে যেত। ট্রি এর ক্ষেত্রে একটু জটিলতা আছে। ধাপে ধাপে ডিলেট করার প্রসেসগুলো দেখাব। আশা করি পোস্ট শেষে যখন সব বুঝে যাবা তখন প্রশ্ন করবা “জটিল পার্টটুকু কুতায়?”

Binary Search Tree – BST এর কোনো একটা নোড ডিলেট করার সময় তিনটা সিচুয়েশন handle করতে হবে। সিচুয়েশনগুলো ভাগ করছি যে কোনো নোডের child এর সংখ্যা দিয়ে। BST এর যে কোনো নোডকে child এর সংখ্যার হিসাবে তিন ভাগে ভাগ করা যায়। যথাঃ

১। 0 child – এমন নোড যার কোনো child নাই। আর জানোই তো এ ধরণের নিঃসন্তান নোডকে বলা হয় leaf.
২। 1 child – যেই নোডের ১ টা মাত্র child আছে। সেটা left child বা right child যে কোনোটাই হতে পারে।
৩। 2 child – যে নোডের ২ টা বাচ্চা আছে।

যেহেতু আমরা কাজ করছি BST নিয়ে তাই আমাদের স্লোগান হতে পারে “দুটি চাইল্ডের বেশি নয়, একটি হলে ভাল হয়!” 😀

এই তিন ধরণের নোডকে ডিলেট করার জন্য ভিন্ন ভিন্ন তিনটি পদ্ধতি অবলম্বন করতে হবে। সেগুলো পর্যায়ক্রমে উল্লেখ করছি।

Node has 0 child

নিঃসন্তান নোডকে ভ্যানিশ করে দেয়া সবচেয়ে সহজ। কারণ এই বেচারার কোনো পিছুটান নাই। ছেলে-মেয়ে, নাতি-নাতনীর সাথে কোনো বন্ধন নাই। যদি এমন নিঃসন্তান নোডকে ডিলেট করার দরকার হয় তাহলে সেই নোডে NULL assign করে দিলেই কিসসা খতম! কোডটা দেখে ফেলিঃ

if(currentNode->leftChild == NULL && currentNode->rightChild == NULL)
currentNode = NULL;

উপরের দেয়া ছবিতে কয়টা leaf node আছে? এখানে থাকা leaf node-গুলো হচ্ছে 30, 39, 41, 44, 46, 49 এবং 59. অর্থাৎ হলুদ রঙের নোডের প্রত্যেকটিকে উপরের এক লাইন কোডের মাধ্যমে delete করে দেয়া যাবে।

Node has 1 child

এই ট্রিতে ১ মাত্র child আছে এমন নোডের সংখ্যা একটি। সেটিকে দেখানো হয়েছে আকাশী রঙ দিয়ে। ট্রি থেকে যদি 70 ডিলেট করতে চাই আর উপরের কোডের মত করে ঐ নোডের মান NULL করে দেই তাহলে কি ডিলেট হবে? উত্তর হচ্ছে নোডটা তো ডিলেট হবেই সাথে তার চাইল্ডও ডিলেট হবে। কারণ 70 নোডের মান NULL করে দেয়ার মানে হচ্ছে 70 এর parent (54) তার right child হিসেবে NULL কে পয়েন্ট করে থাকবে। ফলে 70 এবং 70 এর left child (59) উভয়েই ট্রি থেকে ডিলেট হয়ে যাবে। কিন্তু আমাদের তো লক্ষ্য 70 কে ডিলেট করা। 70 টা শুধু ডিলেট হবে, 59 ঠিকই ট্রির সাথে থাকবে।

এক্ষেত্রে আমরা লিংকড লিস্টের কোনো আইটেম ডিলেট করার সিসটেমটা ফলো করব। তা হচ্ছে 54 এর right child হিসেবে বসিয়ে দিব 59 এর মান। তাহলে 70 কে কেউ পয়েন্ট করছে না। এটা এমনিতেই ডিলেট হয়ে যাবে। নিচের ছবিটা দেখলে আরো ক্লিয়ার হবে।

Source Code:

// node has only right child
if(currentNode->leftChild == NULL)
    currentNode = currentNode->rightChild;
// node has only left child
else if(currentNode->rightChild == NULL) 
    currentNode = currentNode->leftChild;

যদি নোডের right child থেকে থাকে তাহলে প্রথম IF BLOCK কাজ করবে অন্যথায় দ্বিতীয়টা কাজ করবে। উদাহরণের ক্ষেত্রে কাজ করবে দ্বিতীয় ব্লক। 70 কে hold করছে যেই নোড সেটাকে currentNode নাম দিলে currentNode->rightChild == NULL সত্য হবে। তাই রুটকে ডিলেট করতে চাইলে currentNode এর মধ্যে এর leftChild-কে assign করে দিলেই কাজ শেষ। 70 এর leftChild হচ্ছে 59. তাই 70 এর মেমরি অ্যাড্রেস হয়ে যাবে 59 এর মেমরি অ্যাড্রেস। আর এই মেমরি অ্যাড্রেসকে পয়েন্ট করবে 54 এর rightChild.

Node has 2 childred

কমলা রঙের নোডগুলোর প্রত্যেকের দুটি করে children আছে। ধরো আমরা 43 কে ডিলেট করতে চাই। 43 এর নোডকে যদি NULL করে দেই তাহলে এই পুরো subtree-টাই ডিলেট হয়ে যাবে। তাই এমন ভাবে ডিলেট করতে হবে যেন শুধু এই নোডটাই ডিলেট হয়। বাকি নোডগুলো ট্রি এর সাথেই সাথে। এখন প্রশ্ন হচ্ছে 43 কে ডিলেট করার পর তার ঐ স্থানে কাকে বসাবো? 43 এর left child নাকি right child. ধরো right child 45 কে বসালাম 43 এর স্থলে। তাহলে 45 এর তো নিজের দুইটা চাইল্ড আছে সেটা তো থাকবেই, 43 এর left child 41 কোথায় বসবে? একটু চিন্তা ভাবনা করো। আমি ততক্ষণে এক মগ চিনি ছাড়া গ্রীন টি বানিয়ে নিয়ে আসি… 🙂

আচ্ছা… শুরু করা যাক!
আমরা জানি যে BST এর বৈশিষ্ট্য হচ্ছে এর মধ্যকার যে কোনো left subtree হবে parent এর চেয়ে ছোট বা সমান। আর right subtree হবে parent এর চেয়ে বড়। আমরা যখন কোনো একটা নোডকে ডিলেট করব বা কোনো একটা নোড insert করব উভয় ক্ষেত্রেই মাথায় রাখতে হবে যেন এই বৈশিষ্ট্য অক্ষুণ্ণ থাকে। অর্থাৎ কোনো নোড insert করার সময় এমন ভাবে করতে হবে যেন এটা যোগ করার ফলে BST এর বৈশিষ্ট্য নষ্ট না হয়। একই ভাবে যখন কোনো নোডকে ডিলেট করব তখনো এমন ভাবে নোডগুলোকে লিংক করতে হবে যেন BST এর properties ঠিক থাকে। এবার চলো, দেখি দুই বাচ্চাওয়ালা নোডকে কিভাবে ডিলেট করা যায়।

দুটি চাইল্ড আছে এমন নোড ডিলেট করার অ্যালগরিদমঃ
১। নোডটির right subtree এর minimum value বের করতে হবে।
২। Minimum value টা ঐ নোডে replace করতে হবে। (রিপ্লেস করলে কিন্তু নোডের আগের মানটা গায়েব হয়ে যাবে)
৩। Minimum value আগে যেই নোডে ছিল সেই নোডকে delete করতে হবে (তা না হলে তো duplicate মান থেকে যাবে ট্রি তে!)

মাথা ঘুরান্টি দিছে? কোনো তালগোল পাচ্ছ না কেনো এই তিনটা স্টেপ ফলো করতে হবে? দাঁড়াও বলছি…

আমাদেরকে যেহেতু 43 কে ডিলেট করতে বলা হয়েছে তাই এই নোডের মানের জায়গায় অন্য যে কোনো মান বসালে এই নোডের মান কিন্তু ডিলেট হয়েই গেল। প্রশ্ন হচ্ছে এই নোডের মানের জায়গায় কেন right subtree এর minimum value বসাবো? কারণ হচ্ছে BST এর বৈশিষ্ট্য অক্ষুণ্ণ রাখার জন্য। চিন্তা করে দেখ… 43 এর right subtree এর সবগুলো মান 43 এর চেয়ে বড়। আমরা যদি randomly 46 কে 43 এর জায়গায় বসাই তাহলে কিন্তু BST এর বৈশিষ্ট্য ঠিক থাকে না। 46 এর right child হবে তখন 45. Right এ তো parent এর চেয়ে ছোট মান থাকতে পারে না। কিন্তু আমরা যদি রাইট সাবট্রি এর সব চেয়ে ছোট মানটা 43 এর জায়গায় বসাই এবং আদী minimum value এর নোডটা ডিলেট করি তাহলে কিন্তু সব বৈশিষ্ট্য ঠিক থাকে।

একই লজিক দিয়ে আরেকটু ভিন্ন ভাবেও কাজ করানো যায়। তা হচ্ছে নোডের right subtree এর minimum value না নিয়ে left subtree এর maximum value দিয়ে নোডের মানটা রিপ্লেস করা এবং maximum value এর নোডটাকে ডিলেট করা। চিন্তা করে দেখো, উভয় ক্ষেত্রেই কিন্তু BST এর properties ঠিক থাকছে। আশা করি বুঝেছ। হয়ত একটু কনফিউশন থাকতে পারে। কোড দেখলে সেটাও দূর হবে। আর এখানে পুরো delete function-টাই দেখানো হচ্ছে। যেটা 0 child, 1 child এবং 2 child আছে অর্থাৎ সকল নোডের ক্ষেত্রেই কাজ করবে।

node * deleteNode(node *currentNode, int value)
{
    if(currentNode==NULL) // empty tree
        return NULL;
    else if(value < currentNode->number) // value is less than node's number. so go to left subtree
        currentNode->leftChild = deleteNode(currentNode->leftChild, value);
    else if(value > currentNode->number) // value is greater than node's number. so go to right subtree
        currentNode->rightChild = deleteNode(currentNode->rightChild, value);
    else // node found. Let's delete it!
    {
        //node has no child
        if(currentNode->leftChild == NULL && currentNode->rightChild == NULL)
        {
            currentNode = NULL;
        }
        else if(currentNode->leftChild == NULL) // node has only right child
        {
            currentNode = currentNode->rightChild;
        }
        else if(currentNode->rightChild == NULL) // node has only left child
        {
            currentNode = currentNode->leftChild;
        }
        else // node has two children
        {
            node *tempNode = findMinimum(currentNode->rightChild);
            currentNode->number = tempNode->number;
            currentNode->rightChild = deleteNode(currentNode->rightChild, tempNode->number);
        }

    }

    return currentNode;
}

কোডের প্রথমাংশ আগেই আলোচনা করা হয়েছে। একদম শেষের ELSE block টা দেখো। যদি currentNode এর দুইটা চাইল্ড থাকে তাহলে findMinimum() function call করে currentNode এর right subtree এর minimum value আছে যেই নোডে তার memory address বের করা হয়েছে। findMinimum() function কিভাবে কাজ করে তা গত পর্বে আলোচনা করা হয়েছে।

tempNode এ এখন minimum value এর নোডটার অ্যাড্রেস আছে। আমরা চাই এই নোডের ভ্যালুটা (number variable) currentNode এর ভ্যালু হিসেবে বসে যাক। সেটাই করা হয়েছে currentNode->number = tempNode->number; এই লাইনের মাধ্যমে। ডিলেট করার অ্যালগরিদমের প্রথম দুইটা স্টেপের কাজ শেষ। এখন ডুপ্লিকেট হয়ে যাওয়া নোডটা ডিলেট করতে হবে।

Delete a node of BST. Step by step procedure.

currentNode->rightChild = deleteNode(currentNode->rightChild, tempNode->number); এই লাইনের মাধ্যমে রিকার্সিভ কল করা হয়েছে minimum value এর নোডটা NULL করে দেয়ার জন্য। 43 কে ডিলেট করার ক্ষেত্রে এই লাইনে থাকা ফাংশনের প্যারামিটার হিসাবে যাচ্ছে 45 এর মেমরি অ্যাড্রেস ও 44. Parameter এ 44 পাঠানোর কারণ হচ্ছে ডুপ্লিকেট মানটা ডিলেট করা। এই ফাংশন যখন কল হবে তখন ফাংশন বডির ৫ নাম্বার লাইনের ELSE IF এর ব্লকটা কাজ করবে। কারণ বর্তমান নোডের মান 45 কিন্তু value তে আছে 44. তখন আবারো ফাংশন কল হবে 45 এর leftChild এর memory location ও 44 দিয়ে। 45 এর leftChild এ এসে দেখা গেল ৫ ও ৭ নাম্বার লাইনের কন্ডিশন মিথ্যা। কারণ value এর মান currentNode->number এর চেয়ে ছোটও না বড়ও না। তার মানে সমান! আমরা যেই নোডটাকে খুঁজছি সেটাকে পাওয়া গেছে। তখন ৯ নাম্বার লাইনের ELSE block কাজ করবে। যেহেতু 44 একটা leaf অর্থাৎ এর কোনো বাচ্চাকাচ্চ নাই তাই ১২ নাম্বার লাইনের condition true হবে। তখন স্বাভাবিক ভাবেই currentNode = NULL করে দেয়ার মাধ্যমে এই নোডটাকে ভ্যানিশ করে দেয়া হল।

ওয়েট! কাজ এখনো শেষ হয় নাই। যেহেতু রিকার্সিভ কল করা হয়েছে আরো কয়েক জন বসে আছে ফাংশনের রিটার্ন ভ্যালুর জন্য। 44 এর নোডকে NULL করার পর ৩৩ নাম্বার লাইনের মাধ্যমে 45 এর কাছে ফাংশনের রিটার্ন টাইপ হিসাবে নোডের অ্যাড্রেস NULL রিটার্ন করবে। এই NULL value বসে যাবে 45 এর leftChild এ। কেননা আগে ৬ নাম্বার লাইনে currentNode->leftChild = deleteNode(root->leftChild, value); কল হয়েছিল। তাই NULL ভ্যালুটা currentNode->leftChild এ assign হবে।

২৮ নাম্বার লাইনে currentNode->rightChild = deleteNode(currentNode->rightChild, tempNode->number); কল করা হয়েছিল। 45 এর অ্যাড্রেস বসে যাবে 44 এর rightChild pointer variable এ। 45 এর নতুন হওয়া parent 44 তার নিজের মেমরি লোকেশন রিটার্ন করবে 44 এর parent 40 এর কাছে। 40 তার নিজের লোকেশন রিটার্ন করবে 47 এর কাছে। 47 হচ্ছে এই ট্রির রুট। 47 তার নিজের লোকেশন রিটার্ন করবে main function এর কাছে। কারণ main function থেকে root = deleteNode(root, 43); কল করা হয়েছিল।

এই ছিল বিএসটি এর ডিলেট অপারেশন। কোডগুলো অবশ্যই নিজে টাইপ করে রান করবে। তা না হলে কনসেপ্ট ক্লিয়ার হবে না।

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