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

বাইনারি সার্চ ট্রি (Binary Search Tree)

সাজানেন-গোছানো গাছ — বাঁয়ে ছোটরা, ডানে বড়রা
search: O(log n) গড়ে / O(n) সবচেয়ে খারাপ অবস্থায়insert: O(log n) গড়েdelete: O(log n) গড়েspace: O(n)

একটা বাইনারি সার্চ ট্রি (BST) হলো এমন একটা বাইনারি ট্রি, যেখানে মাত্র একটা বাড়তি নিয়ম মেনে চলা হয়। আর এই একটা নিয়মই একে এতটা কাজের বানিয়েছে: এই গাছের যেকোনো নোডের জন্য, তার বাঁ দিকের (left) সব ভ্যালু তার চেয়ে ছোট হতে হবে, আর ডান দিকের (right) সব ভ্যালু তার চেয়ে বড় হতে হবে।

এটাকে লাইব্রেরির সুন্দর করে সাজানেন বইয়ের তাকের মতো ভাবতে পারেন। প্রতিটা মোড়ে গিয়ে আপনাকে শুধু একটা সহজ প্রশ্ন করতে হবে: "আমি যেটা খুঁজছি সেটা কি এর চেয়ে ছোট, নাকি বড়?" এই একটা প্রশ্নের কারণেই প্রতি ধাপে আপনার খোঁজার জায়গা অর্ধেক হয়ে যায়।

BST-এর জাদু

pseudocode
1
2
3
যেকোনো নোড N-এর জন্য:
  N-এর বাঁ দিকের সবার মান  < N-এর মান
  N-এর ডান দিকের সবার মান > N-এর মান

এই নিয়মটা শুধু রুটের জন্যই নয়, গাছের প্রতিটা নোডের জন্যই সত্যি হতে হবে। এটা হলো ভেতরে ভেতরে ঘুরে ফিরে আসা একটা গ্যারান্টি।

◈ যোগ করা আর খোঁজা

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

BST-তে খোঁজা (Search)

খোঁজাখুঁজি সবসময় রুট (Root) থেকে শুরু হয় এবং প্রতিটা নোডে গিয়ে একটাই প্রশ্ন করা হয়: "আমি যেটা খুঁজছি সেটা কি এই নোডের চেয়ে ছোট, বড়, নাকি সমান?"

  • সমান — পেয়ে গেছি!
  • ছোট — তাহলে বাঁয়ে চলুন।
  • বড় — তাহলে ডানে চলুন।
  • চলতে চলতে null বা শূন্য জায়গায় চলে আসছি — তার মানে এটা গাছে নেই।

এখানে প্রতিবার তুলনা করার ফলে বাকি থাকা খোঁজার জায়গা প্রায় অর্ধেক হয়ে যায়। একটা ব্যালান্সড বা সুন্দর আকারের গাছে খুঁজতে O(log n) সময় লাগে — অনেকটা সর্ট করা অ্যারেতে বাইনারি সার্চ করার মতো, কিন্তু এখানে সেটা গাছের আকারে হচ্ছে।

BST-তে নতুন কিছু বসানো (Insert)

বসানোর কাজটাও ঠিক খোঁজার রাস্তা ধরেই হাঁটে। আপনি ছোট/বড় ওই একই নিয়ম মেনে গাছের ডাল ধরে নিচে নামতে থাকবেন, যতক্ষণ না একটা খালি জায়গা (empty slot) পাচ্ছেন। খালি জায়গা পেলেই সেখানে নতুন নোডটা বসিয়ে দেবেন। এতে করে BST-এর ওই জাদুকরী নিয়মটা অটোম্যাটিক ঠিক থাকে।

pseudocode
1
2
3
4
5
insert(node, val):
  if node is null: return new Node(val)
  if val < node.val: node.left  = insert(node.left,  val)
  if val > node.val: node.right = insert(node.right, val)
  return node

BST থেকে ডিলিট করা

কাউকে মুছে ফেলার ক্ষেত্রে তিন ধরনের পরিস্থিতি তৈরি হতে পারে (ডিপেন্ড করে ওই নোডের কয়টা বাচ্চা আছে তার ওপর):

  1. বাচ্চাকাচ্চা নেই (Leaf) — জাস্ট মুছে ফেললেই হলো।
  2. একটা বাচ্চা আছে — মুছে ফেলা নোডের জায়গায় তার ওই বাচ্চাটাকে বসিয়ে দিন।
  3. দুটো বাচ্চা আছে — এটা একটু ঝামেলার। আপনাকে in-order successor বা ডান দিকের অংশ থেকে সবচেয়ে ছোট ভ্যালুটাকে খুঁজে বের করতে হবে। তারপর সেই ভ্যালুটা এনে আপনার মুছে ফেলার নোডে বসিয়ে দিন, আর সবশেষে ডান দিকের ওই ছোট ভ্যালুর আসল নোডটাকে মুছে ফেলুন।

ইন-অর্ডার ট্রাভার্সাল (In-order) দেয় সর্টেড লিস্ট

BST-এর সবচেয়ে বড় সুপারপাওয়ার হলো: এটাকে ইন-অর্ডার ট্রাভার্স (In-order traversal) (লেফট → রুট → রাইট) করলে সবসময় ছোট থেকে বড় হিসেবে সাজানেন (sorted) লিস্ট পাওয়া যায়। যেমন, {৫, ৩, ৮, ১, ৪} ভ্যালুওয়ালা একটা BST-তে ইন-অর্ডার ঘোরাঘুরি করলে আপনি পাবেন ১, ৩, ৪, ৫, ৮ — একদম পারফেক্টভাবে সাজানেন!

দ্রষ্টব্য: BST হলো একটা অটো-সর্টেড ফোনবুক, যেখানে নতুন কোনো নাম ঢোকালেই সে নিজে নিজে ঠিক জায়গায় গিয়ে বসে যায়। এখানে যেকোনো কিছু খোঁজা, বসানো বা মুছতে গেলে শুধু ওই ছোট্ট "বাঁয়ে যাব নাকি ডানে?" নিয়মটা মানলেই হয়।

Complexity

খোঁজা (ব্যালান্সড হলে)
প্রতি ধাপে খোঁজার জায়গা অর্ধেক হয়ে যায়
ফাস্ট O(log n)
খোঁজা (সবচেয়ে খারাপ অবস্থা)
নষ্ট বা ডিজেটেরেট ট্রি দেখতে একটা লিংকড লিস্টের মতো হয়ে যায়
স্লো O(n)
বসানো বা Insert (ব্যালান্সড)
খোঁজার রাস্তা ধরে হেঁটে খালি জায়গায় বসানো হয়
ফাস্ট O(log n)
ডিলিট (ব্যালান্সড)
নোড খুঁজে বের করা + ইন-অর্ডার সাক্সেসর দিয়ে ঠিকঠাক করা
ফাস্ট O(log n)
ইন-অর্ডার (In-order) ঘোরা
সব ডেটাকে সাজানেন (Sorted) অবস্থায় বের করে আনে
লিনিয়ার O(n)
জায়গা (Space)
প্রতিটা ভ্যালুর জন্য একটা করে নোড থাকে
লিনিয়ার O(n)

BST কখন খারাপ হয়ে যায়?

যদি আপনি একটার পর একটা ডেটা সাজানেন বা সর্টেড অবস্থাতেই গাছে ঢোকাতে থাকেন (যেমন: ১, ২, ৩, ৪, ৫...), তাহলে প্রতিটা নতুন নোড তার আগেরটার ডান দিকে গিয়ে বসতে থাকবে। এর ফলে পুরো গাছটা একটা সোজা লাইন হয়ে যাবে — যেটা আসলে একটা লিংকড লিস্ট ছাড়া আর কিছুই নয়। তখন সব কাজের স্পিড O(log n) থেকে কমে গিয়ে বিরক্তিকর O(n) হয়ে যাবে!

আর ঠিক এই সমস্যা ঠেকানোর জন্যই ব্যালান্সড BST (Balanced BSTs) (যেমন AVL Trees বা Red-Black Trees)-এর জন্ম — এরা এই ধরনের খারাপ অবস্থা থেকে বাঁচার জন্য নিজে নিজেই নিজেদের ডালপালা সাজিয়ে গাছটাকে ব্যালান্সড রাখে।

কোথায় কাজে লাগে?

  • এমন জায়গায়, যেখানে ডেটা সবসময় সাজানেন অবস্থায় রাখতে হয়, আবার বারবার নতুন জিনিস ঢোকানো বা মুছে ফেলার দরকার পড়ে।
  • রেঞ্জ কুয়েরি করতে (যেমন X থেকে Y-এর মাঝের সব ভ্যালু বের করা)।
  • সাজানেন ডেটার ওপর ইন-অর্ডার ইটারেট বা লুপ চালানোর জন্য।
  • AVL Trees, Red-Black Trees, এবং Treaps বানানোর মূল ভিত্তি হিসেবে।
Challenge

ছোট কুইজ

আপনি একটা BST-তে ৭ (7) খুঁজছেন। গাছের রুট হলো ১০ (10)। ১০-এর বাঁয়ে আছে ৫ (5), আর ৫-এর ডানে আছে ৭। ৭-কে পেতে আপনাকে কয়বার তুলনা (comparisons) করতে হবে?

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

বাইনারি ট্রি (Binary Trees)
এমন একটা ফ্যামিলি ট্রি, যেখানে বাবা-মায়ের সর্বোচ্চ দুজন করেই সন্তান থাকতে পারে
→
বিএসটি ব্যালান্সিং (BST Balancing)
আনব্যালান্সড বিএসটি (BST) আসলে একটা বাঁশের মতো লম্বা লিংকড লিস্ট ছাড়া আর কিছুই না!
→
এভিএল ট্রি (AVL Tree)
নিজে থেকেই ব্যালান্স ঠিক রাখা ট্রি — যতই কাটাকাটি করুন, ও ঠিকই সোজা হয়ে দাঁড়াবে
→
Databases: SQL vs NoSQLSystem Design
Structured tables or flexible documents — pick your weapon
→
রেড-ব্ল্যাক ট্রি (Red-Black Tree)
নিজে নিজে ব্যালান্স হওয়া জাদুকরী ট্রি — জাভার (Java) ট্রি-ম্যাপ বা সি++ (C++)-এর ম্যাপের পেছনের হিরো
→