অ্যালগরিদম - Algorithmsডাটা স্ট্রাকচার - Data structures

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

Binary search tree Bengali tutorial/ BST / BST Insert, Update, Delete Bangla tutorial

বাইনারি সার্চ ট্রি (Binary search tree /BST) একটি ডাটা স্ট্রাকচার (Data structure) যার মাধ্যমে আমরা দ্রুততম উপায়ে ডাটাগুলোকে সর্টেড ভাবে রাখতে পারি এবং O(log(n)) সময়ে আমরা ট্রি তে রাখা উপাদান গুলো খুঁজে বের করতে পারি। আজকের লিখায় আমরা দেখবো বাইনারি সার্চ ট্রি কি, কিভাবে কাজ করে এবং তার সাথে আমরা দেখবো এর সি প্লাস প্লাস ইমপ্লিমেন্টেশন।

এটা বাইনারি সার্চ নয়। বাইনারি সার্চ নিয়ে লিখাটি এখান থেকে পরতে পারেনটারনারি সার্চ লিখাটি এখানে পাবেন

একে বাইনারি সার্চ ট্রি (BST) কেনো বলা হচ্ছে?

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

যেসব বিশিষ্ট গুলো বাইনারি সার্চ ট্রি কে সাধারণ বাইনারি ট্রি থেকে আলাদা করেছে,

  1. বামের সাবট্রির (Left sub tree) সকল নোডের উপাদান গুলো রুট নোডের থেকে ছোট হবে।
  2. ডানের সাবট্রির (Right sub tree) সকল নোডের উপাদান গুলো রুট নোডের থেকে বড় হবে।
  3. প্রত্যেক সাবট্রিকেও আমরা আলাদা আলাদা ভাবে Binary search tree বলতে পারবো।
Binary search tree
চিত্র ১

লক্ষ করলে দেখতে পারি যে উপরের চিত্রে ডান এবং বাম সাব-ট্রি প্রত্যেকে আলাদা আলাদা ভাবে বাইনারি সার্চ ট্রি এর বৈশিষ্ট্য বহন করছে। একই সাথে আমরা দেখতে পারছি যে, রুট নোডের বামের চাইল্ড রুট নোড থেকে ছোট এবং ডানের চাইল্ড রুট নোডের থেকে বড়। একই কথা প্রতিটি সাব-ট্রি এর জন্যও প্রযোজ্য।

বাইনারি সার্চ ট্রি কিভাবে কাজ করে?

বাইনারি সার্চ ট্রি তে লিফ নোড বাদে প্রতিটা নোডের চাইল্ড নোড থাকে। আমাদের অ্যালগরিদম রুট নোডের সাথে চাইল্ড নোডের তুলনা করার মাধ্যমে ট্রি এর অপারেশন গুলো সম্পন্ন করে। প্রাথমিক ভাবে আমরা বাইনারি সার্চ ট্রি তে নিচের অপারেশন গুলো করতে পারি,

  • ইনসার্ট (Insert) অপারেশন বা ট্রি তে কিছু রাখা: ট্রি তে ইলিমেন্ট রাখার জন্য ইনসার্ট অপারেশন করতে হয়।
  • সার্চ (search) বা ট্রি তে একটি ইলিমেন্ট আছে কিনা তা বের করা: ট্রি তে একটি ইলিমেন্ট আছে কিনা তা O(log(n)) এ খুঁজে বের করা।
  • ডিলিট (Delete): ট্রি থেকে একটি নোড ডিলিট করা

O(log(n)) বলছি, তবে এটা সব সময় O(log(n)) না, বাজে কেসে তিনটি অপারেশন ই O(n) সময় নিবে।

বাইনারি সার্চ ট্রি ইনসার্ট অপারেশন

বাইনারি সার্চ ট্রি ইনসার্ট (Binary search tree insert) খুবই সোজা-সাপটা পদ্ধতি। আমরা বর্তমানে যে সাব-ট্রি তে আছি, তার রুট নোডের সাথে আমরা যেই ইলিমেন্ট ইনসার্ট করবো তার তুলনা করে দেখবো। যদি বর্তমান রুট নোড এর ইলিমেন্ট ছোট হয় তবে বাম সাব-ট্রি তে যাবো, নয়তো ডান সাব-ট্রি তে যাবো। যখন আমরা কোনও লিফ নোডের পৌছাবো তখন আমরা নতুন একটি নোড তৈরি করে সেখানে ইলিমেন্টটি রাখবো

আমরা বুঝতেই পারছি কাজটি রিকার্শনের মাধ্যমে খুব দ্রুত করা যাবে। আমরা কোড করার আগে এই প্রসেসটাকে চিত্রের মাধ্যমে দেখার চেষ্টা করছি।

ধরা যাক আমাদেরকে একটি অ্যারে দেয়া আছে যেখানে কিছু নাম্বার আছে। এই নাম্বার গুলো দিয়ে আমাদেরকে একটি বাইনারি সার্চ ট্রি তৈরি করতে হবে। আমাদের সংখ্যাগুলি হলো, 35,20,50,25,45,15,55,44,22,47,16,46 । চলুন শুরু করি।

Binary search tree insert 1
চিত্র ২

আমরা একটি বিষয় প্রথমে নির্ধারণ করে নিবো। যদি কোন সংখ্যা x, রুট নোড y থেকে ছোট অথবা সমান হয় তবে সবসময় আমরা x কে বামে নিয়ে যাবো। তা না হলে আমরা x কে ডানে নিয়ে যাবো। তারপর যদি বাম/ডানে আগে থেকেই কোনও সাব-ট্রি থাকে তবে আমরা ওই সাব-ট্রির রুটের সাথে পুনরায় একই কাজ করবো (x কে বামে অথবা ডানে নিয়ে যাবো)। যখন আমরা দেখবো আমরা কোন লিফ নোডে চলে আসছি, তখন আমরা লিফ নোডের বামে (যদি x লিফ নোডের থেকে ছোট হয়) অথবা ডানে (যদি x লিফ নোডের থেকে বড় হয়) নতুন নোড তৈরি করে সেখানে x কে রাখবো। এখন উপরের ছবিটি এবং নিচের ছবিটি মনোযোগ দিয়ে দেখুন।

Binary search tree 2
চিত্র ৩

উপরের ডায়াগ্রাম গুলির সাইড নোডের মাধ্যমে কি ঘটছে ব্যাখ্যা করার চেষ্টা করেছি। এবার আপনাদের পালা। বাকি নোড গুলো খাতায় একে ইনসার্ট করার চেষ্টা করেন। সব শেষে আমরা নিচের মতো একটি বাইনারি সার্চ ট্রি পাবো।

Binary search tree zero
চিত্র ৪

আমরা চিত্রের মাধ্যমে বুঝলাম বাইনারি সার্চ ট্রিতে ইনসার্ট কিভাবে কাজ করে। এবার আমরা দেখবো রিকার্শনের মাধ্যমে আমরা কিভাবে বাইনারি সার্চ ট্রি তৈরি করবো এবং তাতে ইনসার্ট করবো।

শুরুতে আমরা আমাদের নোড গুলো উপস্থাপন করার জন্য একটি স্ট্রাকচার তৈরি করবো। আমরা এর নাম দিবো Node । একটি নোডে ৩ টি ভেরিয়েবল থাকবে। একটি int value যেখানে আমরা নোডের মান রাখবো। আর দুইটি হলো Node *left_node এবং Node *right_node । এখানে আমরা বাম এবং ডান নোডের রেফারেন্স রাখবো।

তো আমরা এখন যে ফাংশন টা লিখবো তা একটি সংখ্যা num কে ট্রি তে ইনসার্ট করবে। আমরা রিকার্শন ব্যবহার করে কাজটি করবো।

এখানে লজিক খুব সোজা, num এর মান বর্তমান নোডের ভ্যালু থেকে কম হলে বামে যাও, নয়তো ডানে যাও। আর নোড যদি NULL হয় তার মানে আমরা শেষ প্রান্তে চলে এসেছি, আমাদের নতুন নোড তৈরি করতে হবে এবং তার এড্রেস রিকার্সিভ ভাবে ডান অথবা বাম নোডে এসাইন করে দিতে হবে।

Binary search tree: সার্চ অপারেশন

বাইনারি সার্চ ট্রি তে সার্চ করা একেবারেই সহজ। আমরা রুট নোড থেকে শুরু করবো। ধরা যাক আমরা উপরে ইনসার্ট করার মাধ্যমে মাত্র যেই ট্রি টি তৈরি করলাম সেখানে একটি সংখ্যা ৪৪ আছে কিনা বের করবো। তার জন্য আমরা যেভাবে কাজ করবো লক্ষ করি। একটা বিষয় মাথায় রাখা দরকার যে, বাইনারি সার্চ ট্রির একটা বৈশিষ্ট্য হল ডানে থাকবে রুটের চেয়ে বড় মান এবং বামে রুটের চেয়ে ছোট মান থাকবে এবং আমরা ইনসার্ট করার সময় এটা মাথায় রাখি।

  1. আমরা রুট থেকে শুরু করবো।
  2. এখানে রুট এর নোডের মান হল ৩৫, এখানে ৪৪, ৩৫ থেকে বড়। তাই আমরা বলতে পারি ৪৪ কে ৩৫ এর ডানে রাখা হয়েছে। তাই আমরা ডানে যাবো।
    1. ডানে যে সাবট্রি আছে তার রুটের মান হলো ৫০ যা ৪৪ থেকে বড়। তাই আমরা বলতে পারি আমাদের ৫০ এর বামে যেতে হবে।
      1. এবার বামের সাবট্রির রুট হলো ৪৫ যা ৪৪ থেকে বড়, তাই আবার আমরা বামে যাবো।
      2. এখন বামে এসে আমরা যেই নোডটি পাবো তার মান হলো ৪৪। আমরা ওই নোডের এড্রেস রিটার্ন করবো।

আরও পরিষ্কার বুঝার জন্য আমরা নিচের চিত্রটি দেখবো।

BST search operation
চিত্র ৫

উপরের চিত্রে আমি বাইনারি সার্চ ট্রি তে সার্চ প্রসেস টা দেখানোর চেষ্টা করেছি। এখন আমরা বাইনারি সার্চ ট্রি তে সার্চ করার কোডটি দেখবো।

বাইনারি সার্চ ট্রি তে ডিলিট অপারেশন

বাইনারি সার্চ ট্রি তে ডিলিট করার প্রসেস টা একটু জটিল, এইটা ইমপ্লিমেন্ট করতে অথবা বুঝতে হলে আমাদের জানতে হবে কিভাবে আমরা এর ভিতরের মিনিমাম অথবা ম্যাক্সিমাম বের করা যায়। তাই আমরা আগে ট্রি তে মিনিমাম বের করা দেখবো। তার পরে আপনারা ম্যাক্সিমাম বের করার চেষ্টা করবেন আপনারা।

বাইনারি সার্চ ট্রি তে মিনিমাম বের করা

শুরুতে আমরা একটি ফাংশনের প্রোটোটাইপ দেখি। এটা এমন একটি ফাংশন, যাকে আমরা একটি রুট নোড প্যারামিটার হিসেবে দিবো ফাংশনটি ওই রুট নোডের নিচে যে ট্রি টি আছে তার মিনিমাম রিটার্ন করবে। সুতরাং আমাদের প্রোটোটাইপ নিম্নরূপ,

আমরা উপরে বলেছি বাইনারি সার্চ ট্রি এর প্রতিটি সাবট্রি নিজে আলাদা ভাবে আরেকটি বাইনারি সার্চ ট্রি। আর আমরা আরও জানি বাইনারি সার্চ ট্রি এর সর্ব বামে সব চেয়ে ছোট মান থাকে এবং সর্ব ডানে সব থেকে বড় মান থাকে। একই কথা সকল সাব ট্রি এর জন্য প্রযোজ্য। একটি সাব ট্রি এর সর্ব বামে ওই সাব ট্রি এর সব থেকে ছোট মান থাকে এবং সর্ব ডানে ওই সাব ট্রিয়ের সব থেকে বড় মান থাকবে। চিত্র ৪ এ আমরা দেখতে পাই ট্রিয়ের বামে আমাদের সর্বনিম্ন মান ১৬ এবং ডানে সর্বোচ্চ মান ৫৫ আছে। আবার আমরা যদি ৫০ রুট বিশিষ্ট সাব-ট্রি টা লক্ষ করি এর সর্ব বামে এই সাব-ট্রির সর্ব নিম্ন মান ৪৪ এবং ডানে সর্বোচ্চ মান ৫৫ আছে।

তো আমরা যদি সবার বামের লিফ নোড পর্যন্ত যাই তাহলে আমরা ট্রি এর মিনিমাম পাবো। আশা করি বুঝা গেছে। চলুন মিনিমাম বের করার কোডটা দেখা যাক। এই ফাংশনটি আমাদের ট্রি এর রুট নোডের পয়েন্টার নিবে এবং মিনিমাম নোডের পয়েন্টার রিটার্ন করবে।

এখন আমরা ডিলিট করার অ্যালগরিদমটি পরতে পারি।

ট্রি তে ডিলিট করা

আপনারা যেহেতু মিনিমাম বের করার অ্যালগরিদম জানেন তাহলে এখন আমরা সার্চ ট্রি তে কিভাবে ডিলিট করবো তা দেখতে পারি।

ডিলিট করার সময় আমরা ৩ ধরনের নোড দেখতে পারি। একধরনের নোড হলো যাদের কোন চাইল্ড নোড নেই। অর্থাৎ লিফ নোড। আরেক ধরনের নোড হলো যাদের একটি চাইল্ড নোড আছে হয় ডানে নাহয় বামে। এবং তৃতীয় ধরনের নোড হলো এদের ডান এবং বাম উভয় দিকেই চাইল্ড নোড আছে। তাই আমাদের ডিলিট ফাংশন কে ৩ ধরনের কেস মেনেজ করা লাগবে। এখন চলুন আমরা দেখি যাদের শুন্য চাইল্ড রয়েছে তাদের কিভাবে ডিলিট করা লাগবে।

নোড, যাদের শুন্য চাইল্ড রয়েছে।

এই ধরনের নোড ডিলিট করা সব থেকে সহজ। আমরা সার্চ করে ওই নোডে পোঁছাবো। তারপর ওই নোডটা কে ডিলিট করে দিয়ে তার প্যারেন্ট নোডে NULL বসিয়ে দিবো। এই কাজটি রিকার্সিভ ভাবে করা হবে।

নোড যাদের ১ টি চাইল্ড রয়েছে ডানে অথবা বামে।

এই ধরনের নোড ডিলিট করার পদ্ধতি আর লিঙ্কড লিস্ট এ ডিলিট করার পদ্ধতি একই ধরনের। আমরা নিচের ছবিটি দেখি।

Binary search tree delete list

এখানে ধরা যাক আমদেরকে লাল রঙ করা নড 47 ডিলিট করতে বলা হয়েছে। এখন 47 এমন একটি নোড যার মাত্র একটি ডাইরেক্ট চাইল্ড রয়েছে। তাই 47 কে ডিলিট করার সময় আমদের 45 নোডের right_node ভারিয়েবল এ 46 নোডের এড্রেস বা 47 নোডের লেফট চাইল্ড বসাতে হবে। তাহলেই খেল তামাম 🙂 ।

এমন নোড যাদের দুইটি চাইল্ড ই বিদ্যমান আছে

এমন নোড ডিলিট আমরা সরাসরি করতে পারবো না। কেন? ধরা যাক আমাদের নোড 50 ডিলিট করতে বলা হয়েছে। আমরা যদি নোড 50 ডিলিট করে দেই তাহলে তার জায়গায় কি বসাবো? 45 না 55? যদি 45 বসাই তবে এর সাব ট্রি কে আমরা কি করবো? 55 কেউ আমরা একই কারণে 50 এর জায়গায় আনতে পারবো না। এর জন্য আমরা যা করতে পারি তাহলো, 50 রাইট সাব-ট্রির যে মিনিমাম আছে, তাকে আমরা ওই পজিশনে বসিয়ে দিতে পারি।

তো আমাদের যা করতে হবে তা নিম্নরূপ

  • আমরা যেই নোড ডিলিট করবো সেই নোডের রাইট সাবট্রির মিনিমাম বের করতে হবে।
  • মিনিমাম ভাল্যু দ্বারা আমরা যেই নোড ডিলিট করবো তার ভাল্যু রিপ্লেস করতে হবে।
  • মিনিমাম ভাল্যু যুক্ত নোড ডিলিট করতে হবে ডুপ্লিকেট এড়ানোর জন্য।

এই কাজটি করলে আমাদের বাইনারি সার্চ ট্রি এর বৈশিষ্ট্য অক্ষুণ্ণ থাকবে। এখন আমরা যদি ট্রি থেকে রুট নোডটাই ডিলিট করে দেই কেমন হবে? আসলে কিছুই হবে না। উপরের প্রসেস অনুযায়ী ডিলিট করলে নিচের মতো একটি ট্রি পাবো।

Binary search tree delete

এখানে রুট নোডটা ডিলিট করেছি এবং X থেকে 44 কে নিয়ে রুটের জায়গায় বসিয়ে দিয়েছি। এতে করে আমাদের বাইনারি সার্চ ট্রি এর সমস্ত বৈশিষ্ট্য অক্ষুণ্ণ রয়েছে। বকবকানি তো অনেক দিলাম এবার আমরা ডিলিট করার কোড করতে মাঠে নামবো।

বাইনারি সার্চ ট্রি এর কমপ্লেক্সিটি এনালাইসিস

ধরা যাক n হলো আমাদের ট্রিতে কি পরিমাণ নোড আছে তার সংখ্যা। যেহেতু বাইনারি ট্রি হওয়ার জন্য , তাই আমরা এখানে অপারেশন গুলো বেস কেসে O(log n) এই করতে পারি। তবে আমরা বাইনারি সার্চ ট্রির বাজে কেস কমপ্লেক্সিটি হলো O(n)। কেন? আমরা একটা সিচুয়েশন কল্পনা করি। যেখানে আমাদের ইনপুট দেয়া হবে ছোট থেকে বড় আকারে। ধরা যাক আমাদের 1,2,3,4,5 ইনপুট দেয়া হলো। তবে আমরা যদি বাইনারি সার্চ ট্রির নিয়ম অনুযায়ী ইনসার্ট করি তবে নিচের মতো একটি ট্রি পাবো।

BST worst case

এই ট্রি তে দেখা যাচ্ছে আমাদের সকল নোড ডানে গিয়েছে। এখন আমরা যদি নোড ৫ খুঁজতে যাই তবে আমাদের সকল ৫ টি নোডই পরীক্ষা করে দেখতে হবে। তাই n=5, হলে O(n), হলো এক্ষেত্রে সার্চ, ইনসার্ট এবং ডিলিট কমপ্লেইটি।

অপারেশন বেস কমপ্লিক্সিটিগড় কমপ্লেক্সিটিবাজে কেসে কমপ্লেক্সিটি
সার্চO(log n)O(log n)O(n)
ইনসার্টO(log n)O(log n)O(n)
ডিলিটO(log n)O(log n)O(n)
বাইনারি সার্চ ট্রি এর টাইম কমপ্লেক্সিটি

আজকের লিখা এই পর্যন্তই। BST এর সম্পুর্ন কোডটি এখানে পাবেন। আগামী লিখায় আমরা বাইনারি সার্চ ট্রি নিয়ে আরও জানার করবো। Bye. #Happy_Coding

ডাটা স্ট্রাকচার নিয়ে আরও পোস্ট

লেখাটি কেমন লেগেছে আপনার?

রেটিং দিতে হার্টের উপর ক্লিক করুন।

গড় রেটিং / 5. মোট ভোট:

আপনি প্রথম ভোটদাতা.

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

2 টি মন্তব্য

  1. Vaiya, Last tree er sobi tar ager tai jodi 55 dlt korte chai, ki kora lagbe ? tahole 55 er jaigai ki er right child er 57 boshai dile hbe?

    1. হ্যা, 55 কে ডি‌লিট করার সময় আমা‌দের‌কে রাইট সাব‌ট্রির মি‌নিমাম 57 কে কে 55 এর জায়গায় বসা‌তে হ‌বে এবং রাইট সাব‌ট্রির 57 ডি‌লিট ক‌রে দি‌তে হ‌বে।

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to top button