Binary Trees এবং Tree Traversal

Haskell এ Binary Trees এবং Tree Traversal

Binary Trees এবং Tree Traversal হল ডেটা স্ট্রাকচার এবং অ্যালগরিদমের গুরুত্বপূর্ণ অংশ, যা বিভিন্ন প্রোগ্রামিং সমস্যার সমাধান করতে ব্যবহৃত হয়। Haskell এর মধ্যে এই কনসেপ্টগুলো কার্যকরভাবে প্রয়োগ করা যায়, কারণ এটি ফাংশনাল প্রোগ্রামিংয়ের মৌলিক ধারণাগুলি অনুসরণ করে এবং সহজেই রিকর্শন (recursion) ও মডুলার কোডে কাজ করতে সহায়ক।

১. Binary Tree কী?

Binary Tree এমন একটি ডেটা স্ট্রাকচার যেখানে প্রতিটি নোডে সর্বাধিক দুটি সন্তান নোড থাকতে পারে। একটি বাইনারি ট্রি সাধারণত তিনটি অংশে বিভক্ত থাকে:

1. Root: মূল নোড যা ট্রির শীর্ষে অবস্থান করে।
2. Left Subtree: মূল নোডের বাম পাশের সন্তান।
3. Right Subtree: মূল নোডের ডান পাশের সন্তান।

Binary Tree বিভিন্ন ধরনের হতে পারে, যেমন:

• Full Binary Tree: যেখানে প্রতিটি নোডের দুটি করে সন্তান থাকে, অথবা এটি একটি পাতলা নোড (leaf node) হতে পারে।
• Complete Binary Tree: যেখানে প্রতিটি স্তরে পুর্ণ নোড থাকে, তবে নীচের স্তরে কিছু পাতলা নোড থাকতে পারে।
• Perfect Binary Tree: যেখানে সমস্ত পাতা এক স্তরের গভীরে থাকে এবং প্রতিটি অভ্যন্তরীণ নোডে দুটি সন্তান থাকে।

২. Binary Tree ডেটা টাইপ তৈরি করা

Haskell এ একটি বাইনারি ট্রি ডেটা টাইপ সাধারণত নিম্নরূপে তৈরি করা হয়:

data Tree a = Empty                -- শূন্য গাছ
            | Node a (Tree a) (Tree a)  -- একটি নোড যা একটি মান এবং দুটি সন্তান ধারণ করে

এখানে:

• Tree a হল একটি বাইনারি ট্রি টাইপ, যেখানে a একটি কাস্টম টাইপ (যেমন Int, String, ইত্যাদি)।
• Empty একটি শূন্য গাছ, যা কোনও নোড ধারণ করে না।
• Node একটি নোড যা একটি মান এবং দুটি সন্তান ধারণ করে: একটি বাম এবং একটি ডান।

উদাহরণ:

treeExample :: Tree Int
treeExample = Node 1
                (Node 2
                    (Node 4 Empty Empty)
                    (Node 5 Empty Empty))
                (Node 3
                    Empty
                    (Node 6 Empty Empty))

এখানে একটি বাইনারি ট্রি তৈরি করা হয়েছে:

        1
       / \
      2   3
     / \    \
    4   5    6

৩. Tree Traversal (ট্রি ট্র্যাভার্সাল)

Tree Traversal হল একটি ট্রির সমস্ত নোডকে একটি নির্দিষ্ট ক্রমে পরিদর্শন করার প্রক্রিয়া। বাইনারি ট্রির জন্য সাধারণত তিনটি প্রধান ট্র্যাভার্সাল স্টাইল ব্যবহৃত হয়:

1. Pre-order Traversal
2. In-order Traversal
3. Post-order Traversal

এগুলি সমস্তই recursive প্রক্রিয়া, এবং প্রতিটি ট্র্যাভার্সাল পদ্ধতি ভিন্নভাবে ট্রির নোডগুলোকে পরিদর্শন করে।

৪. Pre-order Traversal

Pre-order Traversal এ, প্রথমে রুট নোডটি পরিদর্শন করা হয়, তারপর বাম সাবট্রিতে চলে যাওয়া হয়, এবং পরে ডান সাবট্রিটে। এর সাধারণ পদক্ষেপগুলি:

1. Root node
2. Left subtree (recursive traversal)
3. Right subtree (recursive traversal)

উদাহরণ:

preOrder :: Tree a -> [a]
preOrder Empty = []
preOrder (Node x left right) = [x] ++ preOrder left ++ preOrder right

ব্যবহার:

Prelude> preOrder treeExample
[1, 2, 4, 5, 3, 6]

এখানে, প্রথমে 1 (root), তারপর 2 (left subtree), তারপর 4, 5, 3, এবং শেষে 6 (right subtree) পরিদর্শন করা হয়েছে।

৫. In-order Traversal

In-order Traversal এ, প্রথমে বাম সাবট্রিটে পরিদর্শন করা হয়, তারপর রুট নোডটি পরিদর্শন করা হয়, এবং শেষে ডান সাবট্রিটে পরিদর্শন করা হয়। এই ট্র্যাভার্সালটি সাধারণত sorted order (যতটা বাইনারি সার্চ ট্রি আছে) জন্য ব্যবহৃত হয়।

1. Left subtree (recursive traversal)
2. Root node
3. Right subtree (recursive traversal)

উদাহরণ:

inOrder :: Tree a -> [a]
inOrder Empty = []
inOrder (Node x left right) = inOrder left ++ [x] ++ inOrder right

ব্যবহার:

Prelude> inOrder treeExample
[4, 2, 5, 1, 3, 6]

এখানে, প্রথমে বাম সাবট্রিট (4, 2, 5), তারপর রুট (1), তারপর ডান সাবট্রিট (3, 6) পরিদর্শন করা হয়েছে।

৬. Post-order Traversal

Post-order Traversal এ, প্রথমে বাম সাবট্রিটে পরিদর্শন করা হয়, তারপর ডান সাবট্রিটে, এবং শেষে রুট নোডটি পরিদর্শন করা হয়।

1. Left subtree (recursive traversal)
2. Right subtree (recursive traversal)
3. Root node

উদাহরণ:

postOrder :: Tree a -> [a]
postOrder Empty = []
postOrder (Node x left right) = postOrder left ++ postOrder right ++ [x]

ব্যবহার:

Prelude> postOrder treeExample
[4, 5, 2, 6, 3, 1]

এখানে, প্রথমে বাম সাবট্রিট (4, 5), তারপর ডান সাবট্রিট (6, 3), এবং শেষে রুট (1) পরিদর্শন করা হয়েছে।

৭. Level-order Traversal

Level-order Traversal (বা Breadth-First Traversal) একটি ট্রির সকল নোডকে স্তর (level) অনুযায়ী পরিদর্শন করে। অর্থাৎ, প্রথমে রুট, তারপর তার সরাসরি সন্তান, এরপর তাদের সন্তান, ইত্যাদি।

উদাহরণ:

levelOrder :: Tree a -> [a]
levelOrder tree = levelOrderHelper [tree]

levelOrderHelper :: [Tree a] -> [a]
levelOrderHelper [] = []
levelOrderHelper (Empty:xs) = levelOrderHelper xs
levelOrderHelper ((Node x left right):xs) = [x] ++ levelOrderHelper (xs ++ [left, right])

ব্যবহার:

Prelude> levelOrder treeExample
[1, 2, 3, 4, 5, 6]

এখানে, levelOrder ফাংশনটি প্রথমে রুট 1, তারপর স্তর অনুযায়ী (2, 3), এবং শেষ পর্যন্ত (4, 5, 6) পরিদর্শন করেছে।

৮. Summary

উপসংহার

Haskell এ Binary Trees এবং Tree Traversal ব্যবহার করা অত্যন্ত কার্যকরী, বিশেষ করে যখন গাছের কাঠামোর সাথে সম্পর্কিত কাজ করতে হয়। Pre-order, In-order, Post-order, এবং Level-order ট্র্যাভার্সালগুলি গাছের সমস্ত নোড পরিদর্শন করার জন্য ব্যবহৃত হয় এবং প্রতিটি প্রক্রিয়া আলাদা আলাদা পরিস্থিতিতে উপকারী। Haskell এর recursive প্রকৃতি এবং pattern matching এর সাহায্যে ট্রি ডেটা স্ট্রাকচার এবং তার ট্র্যাভার্সাল অনেক সহজভাবে পরিচালনা করা যায়।