পোস্টটি পড়া হয়েছে 5,641 বার
Data Structure in Bengali

ট্রি ডেটা স্ট্রাকচার – ৪ [Binary Search Tree Traversal]

Hasan Abdullahবাইনারি সার্চ ট্রি - BST

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

ট্রি ডেটা স্ট্রাকচার সিরিজের তৃতীয় পর্বে Binary Search Tree এর নোডগুলোর ইনসার্ট অপারেশন দেখানো হয়েছিল। আরো দেখানো হয়েছিল ট্রি এর মধ্য থেকে কোনো একটা value সার্চ করে বের করার কোড। এই পর্বে BST এর traversal দেখানো হবে।

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

অ্যারে, স্ট্যাক, কিউ বা লিংকড লিস্ট হচ্ছে লিনিয়ার ডেটা স্ট্রাকচার। কিন্তু ট্রি নন-লিনিয়ার ডেটা স্ট্রাকচার। Linear Data Structure এর ক্ষেত্রে পুরো স্ট্রাকচারে traverse করা একদম সোজা কাজ। যেহেতু ডেটাগুলো সিরিয়াল্যি থাকে তাই একটার পর একটা ডেটাগুলোতে অ্যাক্সেস করা যায়। অ্যাক্সেসের ধরণও একই হয়। Singly Linked List এর ক্ষেত্রে ধরো, পুরোটা লিংকড লিস্ট প্রিন্ট করতে চাইলে কিন্তু এক ভাবেই প্রিন্ট করা সম্ভব। বা যে কোনো valid code এর জন্য আউটপুট একই আসবে।

ট্রি ট্রাভার্সের সাথে লিনিয়ার ডেটা স্ট্রাকচারের ট্রাভার্সের পার্থক্যটা এখানেই। আগের পোস্ট থেকে দেখেছো যে ট্রির প্রতি নোডে এক বা একাধিক ডেটা থাকে। আর left child ও right child এর মেমরি অ্যাড্রেস থাকে। যদি তোমাকে ট্রি প্রিন্ট করতে বলি তাহলে তুমি কিভাবে প্রিন্ট করব? রুট থেকে লুপ চালিয়ে প্রতিটা নোডে যাবা আর ডেটাগুলো প্রিন্ট করবা, সিম্পল তাই না? একটু চিন্তা করো! কোনো একটা নোডে গিয়ে আগে এই নোডের ডেটা প্রিন্ট করবা নাকি তার বাচ্চাকাচ্চাদের ডেটা প্রিন্ট করবা? তুমি হয়ত আগে নোডের ডেটা প্রিন্ট করবা, এরপর বামের চাইল্ডের ডেটা এরপর ডানের চাইল্ডের ডেটা। আরেক জন দেখা যাবে প্রিন্ট করছে, আগে নোডের বাচ্চাকাচ্চাদের ডেটা। এরপর নোডের নিজের ডেটা। উভয় ক্ষেত্রেই কিন্তু ট্রি এর ডেটাই প্রিন্ট হচ্ছে। শুধু ডেটাগুলো আগে-পিছে প্রিন্ট হচ্ছে। এই ভিন্নতাগুলো সবগুলোই valid. এই আগে পরে প্রিন্টের ব্যাপারটা নিয়েই এখন কথা বলব। DFS – Depth Search Algorithm এর সাহায্যে একটা বাইনারি ট্রি ট্রাভার্স করার তিনটি পদ্ধতি রয়েছে। সেগুলো হচ্ছেঃ

  • Pre-order traversal
  • In-order traversal
  • Post-order traversal

DFS এর মাধ্যমে ট্রি ট্রাভার্সের একটা মূলনীতি আছে। তা হচ্ছে কোনো একটা নোডের siblings এ সার্চ করার আগে ঐ নোডের মাধ্যমে ট্রি এর যতটা deep এ যাওয়া যায় ততটা deep এ যেতে হবে। ধরো রুটের চাইল্ড হচ্ছে A, B. A এর চাইল্ড হচ্ছে C, D. C এর চাইল্ড E, F. এখানে A, B কিন্তু siblings (আপন মায়ের পেটের ভাইবোন)। তুমি যখন A নোডে এসে একটা ডেটা খুঁজে পেলে না, তখন B নোডে গিয়ে খুঁজতে পারবা না। A এর বাচ্চাকাচ্চার মধ্যে খুঁজতে হবে। A থেকে গেলে C তে। C তে খুঁজে না পেলে C এর চাইল্ড D এর কাছে গিয়ে খুঁজতে হবে। এভাবে ট্রি এর গভীর থেকে গভীরে নেমে যেতে হবে। যখন একটা NULL node পাওয়া যাবে তখন বাকি থাকা siblings এর মধ্যে একে একে খুঁজতে হবে। মূলনীতির কনসেপ্ট এটাই।

General recursive pattern for traversing a binary tree

একটা non-empty বাইনারি ট্রি এর যে কোনো নোড N হলে তাতে নিচের তিনটা ঘটনা ঘটতে পারেঃ

(L) – recursively এই N নোডের left subtree তে ট্রাভার্স করবা। Left subtree ট্রাভার্স করা হয়ে গেলে তুমি আবার N এর কাছেই ফিরে আসবা
(R) – recursively এই N নোডের right subtree তে ট্রাভার্স করবা। Right subtree ট্রাভার্স করা হয়ে গেলে তুমি আবার N এর কাছেই ফিরে আসবা
(N) – নোড N-কে প্রসেস করবা।

L-R-N এর কোনটার কাজ আগে করবা কোনটাকে পরে করবা সেই ক্রমই হচ্ছে pre-order, in-order আর post-order. একটা ট্রি প্রিন্ট করার উদাহরণ দিয়ে এই ব্যাপারগুলো ব্যাখ্যা করা হচ্ছে।

ধরো একটা BST-তে এই ডেটাগুলো যথাক্রমে ইনসার্ট করা হবে। 45 হচ্ছে এই ট্রি এর root. BST আঁকা যায় এভাবেঃ
45, 54, 40, 49, 38, 70, 30, 39, 41, 45, 44

Binary Search Tree – BST

Pre-order Traversal

উপরের তিনটা প্রসেসের ক্রম হবে এক্ষেত্রে N-L-R.
অর্থাৎ, N নোডটি NULL না হলে শুরুতেই তাকে প্রসেস করা হবে বা নোডের ডেটাকে প্রিন্ট করে দেয়া হবে। এরপর recursively left subtree এবং right subtree. যদি N নোডটি NULL হয় তাহলে ফাংশন return করবে। কারণ NULL হওয়ার মানে এই নোডটি ট্রিতে exist করে না।

Binary Tree traversal in Pre-order.
Binary Tree traversal in Pre-order. Output: F, B, A, D, C, E, G, I, H.
void preOrderPrint(node *rootNode)
{
    if(rootNode==NULL)
        return;

    printf("%d ", rootNode->number);

    preOrderPrint(rootNode->leftChild);
    preOrderPrint(rootNode->rightChild);
}

কোডে দেখো, প্রথমেই নোডের ডেটা প্রিন্ট করে দেয়া হয়েছে। এরপর রিকার্সিভ কল হয়েছে। Fig 1.1 এ যেই ট্রি এর ছবি দেয়া হয়েছে এটার জন্য pre-order traversal এ আউটপুট আসবে এটাঃ 45 40 38 30 39 41 45 44 54 49 70

In-order Traversal

এক্ষেত্রে কাজের ক্রম হবে L-N-R.
প্রথমে N নোডের left subtree তে recursively ট্রাভার্স করবে এরপর নোড N-কে প্রসেস করা হবে অর্থাৎ N এর ডেটাকে প্রিন্ট করা হবে। অতঃপর right subtree তে ট্রাভার্স করবে।

Sorted_binary_tree_inorder
BST in In-order. Output: A, B, C, D, E, F, G, H, I.
void inOrderPrint(node *rootNode)
{
    if(rootNode==NULL)
        return;

    inOrderPrint(rootNode->leftChild);

    printf("%d ", rootNode->number);

    inOrderPrint(rootNode->rightChild);
}

Fig 1.1 এর ট্রির আউটপুটঃ 30 38 39 40 41 44 45 45 49 54 70

Post-order Traversal

প্রসেসগুলোর ক্রম হবে L-R-N.
postOrderTraverse(node *N) নামের যদি কোনো ফাংশন থাকে তাহলে তাকে N নোডের left child দিয়ে recursive call করার মাধ্যমে left subtree-তে ট্রাভার্স করবে। এরপর একই ফাংশনকে আবার রিকার্সন কল করা হবে N এর right child দিয়ে। তাহলে right subtree এর সবগুলো নোড ট্রাভার্স করা হবে (নোডগুলোর ডেটা প্রিন্ট করবে)। এরপর গিয়ে N এর ডেটা প্রিন্ট করা হবে।

Binary Tree traversal in Post-order.
Binary Tree traversal in Post-order. Output: A, C, E, D, B, H, I, G, F.
void postOrderPrint(node *rootNode)
{
    if(rootNode==NULL)
        return;

    postOrderPrint(rootNode->leftChild);
    postOrderPrint(rootNode->rightChild);

    printf("%d ", rootNode->number);

}

Fig 1.1 এর ট্রির আউটপুটঃ 30 39 38 44 45 41 40 49 70 54 45

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

উপরের এই তিনটি পদ্ধতিতে Binary Search Tree traverse করা যায়। আগামী পর্বে দেখানো হবে BST এর maximum ও minimum value কিভাবে বের করা যায়।