ট্রিপড়তে ৫ মিনিট লাগবে

এন-অ্যারি ট্রি (N-ary Trees)

যখন একটা নোডের বাপের যেকোনো সংখ্যক বাচ্চা থাকতে পারে — ফাইল সিস্টেম, ডম (DOM), বা অর্গানোগ্রাম
traverse: O(n)space: O(n)

এন-অ্যারি ট্রি (N-ary tree) হলো এমন এক ধরনের ট্রি, যেখানে একটা নোডের যত খুশি তত সংখ্যক বাচ্চা বা চাইল্ড থাকতে পারে — শুধু দুটো নয়। বাইনারি ট্রিতে যেমন নিয়ম থাকে যে একটা বাপের সর্বোচ্চ দুটোই বাচ্চা (ডান আর বাঁ) থাকতে পারবে, এন-অ্যারি ট্রিতে এমন বাঁধার কোনো বালাই নেই।

আমাদের দৈনন্দিন জীবনে এর ভুরি ভুরি উদাহরণ আছে:

  • ফাইল সিস্টেম (File system) — একটা ফোল্ডারের ভেতর যেকোনো সংখ্যক ফাইল বা সাব-ফোল্ডার থাকতে পারে।
  • এইচটিএমএল ডম (HTML DOM) — একটা <div> ট্যাগের ভেতর ডজনখানেক চাইল্ড এলিমেন্ট থাকতে পারে।
  • ট্রাই (Trie) — স্ট্রিং প্রিফিক্স সার্চের জন্য বিশেষায়িত আরেকটি এন-অ্যারি ট্রি।
  • কোম্পানির অর্গানোগ্রাম (Org chart) — একজন ম্যানেজারের আন্ডারে যেকোনো সংখ্যক কর্মী কাজ করতে পারে।
  • কমেন্ট থ্রেড (Comment threads) — ফেসবুকে বা ব্লগে একটা কমেন্টের নিচে যত্তো খুশি রিপ্লাই পড়া সম্ভব।
  • জেসন/এক্সএমএল (JSON/XML) — এগুলোর নোডেও যেকোনো সংখ্যক চাইল্ড থাকতে পারে।

এর ভেতরের স্ট্রাকচার কেমন?

একটা এন-অ্যারি নোড দেখতে সাধারণত এরকম হয়:

pseudocode
1
2
3
4
class Node:
  def __init__(self, val):
    self.val = val
    self.children = []  # বাচ্চাদের রেফারেন্স রাখার একটা লিস্ট বা অ্যারে

এই children লিস্টটা দরকারের সময় নিজে নিজেই বড় হয় — একটা নোডের যদি ৩টা বাচ্চা থাকে, তবে ওই লিস্টে ৩ জনের রেফারেন্স থাকবে। আর লতা বা পাতা (leaf node)-র ক্ষেত্রে এই লিস্টটা একদম ফাঁকা থাকে।

◈ Explore N-ary tree

← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন

এন-অ্যারি ট্রিতে ঘোরার উপায় (Traversing)

বাইনারি ট্রির মতোই এখানে ঘোরাঘুরি বা ট্রাভার্স করার নিয়ম একই, শুধু পয়েন্টার দুটোর বদলে লিস্ট ধরে আগাতে হয়:

প্রি-অর্ডার (Pre-order / DFS)

আগে বর্তমান বা বাপ নোডটাকে দেখুন, তারপর তার সব বাচ্চাদের সিরিয়াল অনুযায়ী একে একে দেখতে থাকো:

pseudocode
1
2
3
4
5
def preorder(node):
  if node is None: return
  visit(node)  # আগে বাপকে দেখুন
  for child in node.children:
    preorder(child)  # এরপর বাচ্চাদের খোঁজে যান

পোস্ট-অর্ডার (Post-order / DFS)

আগে সবগুলো বাচ্চার কাজ শেষ করুন, তারপর বর্তমান বা বাপ নোডের কাছে আসুন:

pseudocode
1
2
3
4
5
def postorder(node):
  if node is None: return
  for child in node.children:
    postorder(child)  # আগে বাচ্চাদের কাজ শেষ করুন
  visit(node)  # তারপর বাপের কাজ

লেভেল-অর্ডার (Level-order / BFS)

একটা কিউ (queue) ব্যবহার করে একদম লেভেল বা তলা ধরে ধরে আগানো — এটা বাইনারি ট্রির বিএফএস-এর (BFS) মতোই, শুধু লুপ চালিয়ে ২টার বদলে সব বাচ্চাকে কিউতে ঢোকাতে হয়:

pseudocode
1
2
3
4
5
6
def levelorder(root):
  queue = [root]
  while queue:
    node = queue.pop(0)
    visit(node)
    queue.extend(node.children)  # সব বাচ্চাকে একসাথে কিউতে দিয়ে দিন

সিরিয়ালাইজেশন (Serialization)

একটা এন-অ্যারি ট্রিকে হার্ডডিস্কে সেভ করতে বা ইন্টারনেটে পাঠাতে গেলে তাকে সিরিয়ালাইজ (serialize) বা স্ট্রিং বানাতে হয়। একটা কমন স্টাইল হলো: আগে নোডের ভ্যালু, তারপর তার কয়টা বাচ্চা আছে সেই সংখ্যাটা লেখা। আরেকটা উপায় হলো: লেভেল-অর্ডার করে স্পেশাল একটা 'নাল (null)' মার্কার দিয়ে ভাইবোনদের বা বাচ্চাদের লিস্ট আলাদা করা (লিটকোড (LeetCode)-এ সাধারণত এই স্টাইলটাই ব্যবহার করা হয়)।

দ্রষ্টব্য: মজার ব্যাপার হলো, যেকোনো এন-অ্যারি ট্রিকে চাইলে একটা বাইনারি ট্রিতে কনভার্ট করা যায়। এই টেকনিকের নাম 'লেফট-চাইল্ড রাইট-সিবলিং (left-child right-sibling)': অর্থাৎ বাপের বাঁ দিকের পয়েন্টারটা সব বাচ্চাদের মধ্যে প্রথম জনকে দেখায়, আর ডান দিকের পয়েন্টারটা তার ঠিক পরের ভাই বা বোনকে দেখায়। অনেক পুরোনো ফাইল সিস্টেম ভেতরে ভেতরে ঠিক এভাবেই কাজ করতো!

এন-অ্যারি ট্রি বনাম বাইনারি ট্রি

কখন কোনটা ব্যবহার করবেন?

  • বাইনারি ট্রি ব্যবহার করবেন যখন প্রবলেমে কোনো কিছুর স্পষ্ট "দুই ভাগ (two-way split)" থাকবে (যেমন: ছোট/বড়, হ্যাঁ/না), অথবা যখন আপনার বাইনারি সার্চ ট্রি (BST)-এর মতো কোনো স্পেশাল সার্চ সুবিধার দরকার হবে।
  • এন-অ্যারি ট্রি ব্যবহার করবেন যখন বাস্তবেই কোনো কিছুর অসংখ্য বাচ্চা থাকার সম্ভাবনা থাকে (যেমন: ফাইল সিস্টেম, কোম্পানির চার্ট, বা এইচটিএমএল ডম)।

উচ্চতা (Height) বা গভীরতা (Depth)

ডালপালা বা ব্রাঞ্চিং ফ্যাক্টর (branching factor) যদি k হয়, তবে একটা ব্যালান্সড এন-অ্যারি ট্রির উচ্চতা হয় O(log_k n) — যেটা বাইনারি ট্রির O(log₂ n)-এর চেয়ে অনেক অনেক ছোট হতে পারে। ধরুন ফোল্ডারের গড় সাইজ ২০ (branching factor 20), এমন একটা ফাইল সিস্টেমে মাত্র ৪-৫ লেভেলের উচ্চতাতেই লাখ লাখ ফাইল ধরে যায়!

Complexity

ট্রাভার্সাল (যেকোনো অর্ডারে)
প্রতিটা নোডকে ঠিক একবার ঘুরে দেখা হয়
লিনিয়ার O(n)
ভ্যালু দিয়ে নোড খোঁজা
এটা BST না হওয়ায় কোনো সিরিয়াল নেই — তাই লুপ চালিয়ে সব চেক করতে হয়
লিনিয়ার O(n)
নতুন বাচ্চা বা চাইল্ড ঢোকানো
বাপের children লিস্টের শেষে জাস্ট append করে দিলেই হয়
সাথে সাথে O(1)
জায়গা (Space)
প্রতিটা নোড এবং তাদের বাচ্চাদের লিস্ট মিলিয়ে
লিনিয়ার O(n)
Challenge

ছোট কুইজ

একটা ফাইল সিস্টেম ফোল্ডারে ৪টা লেভেল মিলিয়ে ১০০০টা ফাইল আর সাব-ফোল্ডার আছে। প্রতিটা ফোল্ডারের মোট সাইজ মেগাবাইটে বের করার জন্য আপনি কোন ট্রাভার্সাল (Traversal) পদ্ধতিটা ব্যবহার করবেন?

পড়া চালিয়ে যান