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

বাইনারি ট্রি (Binary Trees)

এমন একটা ফ্যামিলি ট্রি, যেখানে বাবা-মায়ের সর্বোচ্চ দুজন করেই সন্তান থাকতে পারে
traverse: O(n)space: O(h), যেখানে h = ট্রির উচ্চতা

একটা ফ্যামিলি ট্রি বা বংশলতিকার কথা চিন্তা করুন — তবে এখানে নিয়মটা একটু কড়াকড়ি। এই পরিবারে প্রতিটা মানুষের সর্বোচ্চ দুজন সন্তান থাকতে পারবে: একজন বাঁ দিকের সন্তান (Left child) এবং একজন ডান দিকের সন্তান (Right child)। এটাই হলো বাইনারি ট্রি!

একদম ওপরে যে বসে থাকে, তাকে বলা হয় রুট (Root) বা শেকড়। আর একদম নিচে যাদের কোনো সন্তান-সন্ততি নেই, তাদের বলা হয় লিফ (Leaf) বা পাতা। এর মাঝামাঝি যারা থাকে, তারা সবাই হলো ইন্টারনাল নোড (Internal node)।

জরুরি কিছু শব্দ (Vocabulary)

  • রুট (Root) — একদম ওপরের নোড, যেখান থেকে সবকিছুর শুরু।
  • প্যারেন্ট (Parent) — এমন নোড যার নিচে সন্তান আছে।
  • চাইল্ড (Child) — প্যারেন্টের ঠিক নিচেই যে নোড থাকে।
  • লিফ (Leaf) — এমন নোড যার কোনো সন্তান নেই (বংশ এখানেই শেষ!)।
  • উচ্চতা (Height) — রুট থেকে একটা লিফ পর্যন্ত সবচেয়ে লম্বা রাস্তায় কতগুলো এজ বা লাইন আছে, তার সংখ্যা।
  • গভীরতা (Depth) — একটা নোড রুট থেকে ঠিক কত ধাপ নিচে আছে।

বাইনারি ট্রি কেন এত গুরুত্বপূর্ণ?

কম্পিউটার সায়েন্সের দুনিয়ায় বাইনারি ট্রি সব জায়গায় ছড়িয়ে আছে। আমাদের ফোল্ডার বা ফাইল এক্সপ্লোরার, কম্পাইলার, ডেটাবেস — সবাই এই ট্রি স্ট্রাকচার ব্যবহার করে। আর এই "সর্বোচ্চ ২ সন্তান"-এর নিয়মের কারণেই এদের বোঝা এবং কোড করা অনেক সহজ ও স্পিডি হয়ে যায়।

◈ ট্রাভার্সাল (Traversal) বা ঘোরাঘুরিগুলো দেখুন

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

সব নোড ঘুরে দেখার ৪টা উপায়

"ট্রাভার্সাল (Traversal)" মানে হলো গাছের প্রতিটা নোডে গিয়ে অন্তত একবার উঁকি দিয়ে আসা বা ভিজিট করা। আপনি কোন নিয়মে যাবেন, তার ওপর নির্ভর করে কোন নোড কখন আপনার সামনে পড়বে। অনেকটা বই পড়ার মতো ব্যাপার — আপনি কি আগে চ্যাপ্টারের নাম পড়েন, নাকি সরাসরি ভেতরে ঢুকে যান?

প্রি-অর্ডার (Pre-order): রুট → লেফট → রাইট

সন্তানদের কাছে যানয়ার আগেই রুটকে ভিজিট করা। অনেকটা চ্যাপ্টার পড়ার আগে সূচিপত্র বা টেবিল অফ কন্টেন্টস পড়ার মতো। একটা ট্রি হুবহু কপি করতে বা ফাইল আকারে সেভ (serialize) করতে এটা দারুণ কাজে লাগে।

pseudocode
1
2
3
4
pre_order(node):
  visit(node)
  pre_order(node.left)
  pre_order(node.right)

ইন-অর্ডার (In-order): লেফট → রুট → রাইট

প্রথমে বাঁিকের অংশ, তারপর রুট এবং শেষে ডান দিকের অংশ দেখা। একটা Binary Search Tree (BST)-এর ক্ষেত্রে আপনি যদি ইন-অর্ডার ট্রাভার্স করেন, তবে ম্যাজিকের মতো সবগুলো ডেটা একদম ছোট থেকে বড় হিসেবে সাজানেন (Sorted) অবস্থায় পেয়ে যাবেন!

pseudocode
1
2
3
4
in_order(node):
  in_order(node.left)
  visit(node)
  in_order(node.right)

পোস্ট-অর্ডার (Post-order): লেফট → রাইট → রুট

প্যারেন্টের কাছে যানয়ার আগে সন্তানদের কাজ সেরে ফেলা। যখন আপনার প্যারেন্টকে কিছু করার আগে সন্তানদের ডিলিট বা প্রসেস করতে হয়—যেমন একটা ফোল্ডারের টোটাল সাইজ বের করার আগে ভেতরের সাব-ফোল্ডারগুলোর সাইজ জানা দরকার হয়—তখন এটা দারুণ কাজে দেয়।

pseudocode
1
2
3
4
post_order(node):
  post_order(node.left)
  post_order(node.right)
  visit(node)

লেভেল-অর্ডার (Level-order): BFS বা তলা ধরে আগানো

এক তালা, দোতলা করে লেভেল অনুযায়ী বাঁ থেকে ডানে যানয়া — অনেকটা আমরা যেভাবে প্যারাগ্রাফ বা লাইন বাই লাইন পড়ি। এখানে রিকার্শনের বদলে একটা কিউ (Queue) ব্যবহার করা হয়। সবচেয়ে ছোট রাস্তা খোঁজার জন্য বা ট্রি-টাকে স্ক্রিনে সুন্দর করে ছাপানোর জন্য এটা বেস্ট।

pseudocode
1
2
3
4
5
6
7
level_order(root):
  queue = [root]
  while queue:
    node = queue.dequeue()
    visit(node)
    if node.left:  queue.enqueue(node.left)
    if node.right: queue.enqueue(node.right)
দ্রষ্টব্য: মনে রাখার দারুণ ট্রিক: Pre/In/Post শব্দগুলো দিয়ে আসলে বোঝায় আপনি রুট (ROOT)-কে কখন ভিজিট করবেন। Pre মানে সবার আগে রুট। In মানে রুট থাকবে মাঝখানে। আর Post মানে রুটকে ভিজিট করবেন সবার শেষে।

Complexity

প্রি-অর্ডার (Pre-order)
প্রতিটা নোডকে একবার করে দেখা হয়
লিনিয়ার O(n)
ইন-অর্ডার (In-order)
প্রতিটা নোড একবার দেখা হয় — BST-তে সর্টেড ডেটা পাওয়া যায়
লিনিয়ার O(n)
পোস্ট-অর্ডার (Post-order)
প্রতিটা নোডকে একবার করে দেখা হয়
লিনিয়ার O(n)
লেভেল-অর্ডার (BFS)
সব নোড একবার দেখা হয়, O(w) সাইজের কিউ লাগে (w = সবচেয়ে চওড়া লেভেল)
লিনিয়ার O(n)
জায়গা বা Space (কল স্ট্যাক)
ব্যালান্সড ট্রির জন্য h=log n, আর বাঁকা বা ডিজেটেরেট ট্রির জন্য h=n
উচ্চতা (Height) O(h)

ফুল, কমপ্লিট এবং পারফেক্ট ট্রি

বাইনারি ট্রি-র শেপ বা আকারের ওপর ভিত্তি করে এদের কিছু স্পেশাল নাম আছে:

  • ফুল বাইনারি ট্রি (Full binary tree) — প্রতিটা নোডের হয় ০ টা, নয়তো ঠিক ২ টা সন্তান থাকবে (কখনোই ১ টা নয়)।
  • কমপ্লিট বাইনারি ট্রি (Complete binary tree) — একদম শেষের লেভেলটা বাদে বাকি সব লেভেল কানায় কানায় পূর্ণ থাকবে, আর শেষের লেভেলে নোডগুলো সবসময় একদম বাঁ দিক থেকে বসতে শুরু করবে। হিপ (Heaps) এই শেপটা ব্যবহার করে।
  • পারফেক্ট বাইনারি ট্রি (Perfect binary tree) — ভেতরের সব নোডের ২টো করে সন্তান থাকবে এবং সব লিফ বা পাতা একদম একই লেভেলে বা তলায় থাকবে। h উচ্চতার একটা পারফেক্ট ট্রিতে ঠিক 2^(h+1) - 1 টা নোড থাকে।

উচ্চতা এবং ব্যালান্স (Height and balance)

একটা ট্রির উচ্চতা ঠিক করে দেয় এর রাস্তাগুলো কত বড় হবে। একটা ব্যালান্সড বা ভারসাম্যপূর্ণ ট্রি এর উচ্চতাকে সবসময় log₂(n)-এর কাছাকাছি ধরে রাখে, যার ফলে সব কাজ চোখের পলকে হয়। কিন্তু একটা আনব্যালান্সড বা তেড়া-বাঁকা ট্রির উচ্চতা বাড়তে বাড়তে n হয়ে যেতে পারে (তখন সেটা দেখতে একটা লিংকড লিস্টের মতো হয়), যার ফলে স্ট্যাক ভরে গিয়ে খোঁজাখুঁজি অনেক স্লো হয়ে যায়।

Challenge

ছোট কুইজ

এমন একটা ট্রি আছে যার রুট হলো ৪, আর বাঁ দিকের সাব-ট্রিতে আছে {২,১,৩} এবং ডান দিকের সাব-ট্রিতে আছে {৬,৫,৭}। এই ট্রি-টাকে ইন-অর্ডার ট্রাভার্স (In-order) করলে কী পাবো?

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