আমার এই পোস্টে বাইনারি সার্চ ট্রি এর প্রতিটি সাব-ট্রির উচ্চতা নির্ণয় এবং ব্যাল্যান্স ফ্যাক্টর (Balance factor) নির্ণয়ের প্রয়োজনীয় অ্যালগরিদম নিয়ে বিস্তারিত আলোচনা করা হবে। এই লিখটাতে যা আছে আগের AVL Tree তে সবই আছে। তবে ঐ পোস্টটি বেশি বড় হয়ে যাওয়ায় এইখানে উচ্চতার নির্ণয়ের অংশ আলাদা করে দিচ্ছি। যারা পোস্টটি দেখেছেন এবং বুঝেছেন তারা এই পোস্ট টি স্কিপ করতে পারেন। কিন্তু যদি আরও বিস্তারিত বুঝতে চান তবে অবশ্যই লিখাটি পরবেন।
এই পোস্টটি পড়ার জন্য আপনাকে অবশ্যই Binary search tree নিয়ে জানতে হবে।
বাইনারি ট্রি – ব্যাল্যান্স ফ্যাক্টর কি?
বাইনারি ট্রি তে ব্যাল্যান্স ফ্যাক্টর হলো একটি নোডের দুইটি সাব-ট্রির মধ্যকার উচতার পার্থক্য। ব্যাল্যান্স ফ্যাক্টর বের করার সূত্র হলো,
অর্থাৎ আমরা দেখতে পাচ্ছি যদি ব্যাল্যান্স ফ্যাক্টর ধনাত্মক হয় তবে আমাদের ট্রি ট্রি বাম দিকে ভারি হয়ে থাকবে। আর ঋণাত্মক হলে ডান দিকে ভারি হয়ে থাকবে।
বাইনারি সার্চ ট্রিয়ের উচ্চতা নির্ণয়
সকল বাইনারি ট্রি তে ব্যাল্যান্স ফ্যাক্টর বের করতে হলে আমাদের অবশ্যই ডান এবং বাম সাব-ট্রির উচ্চতা জানতে হবে। এর জন্য আমরা রিকার্সিভ ভাবে বাইনারি ট্রিয়ের উচ্চতা বের করার প্রোগ্রাম করতে পারি। তবে আমরা আজকে তা দেখছি না। আমাদের টার্গেট যেহেতু বাইনারি সার্চ ট্রি নিয়ে তাই আমরা insert অপারেশন এর মাধ্যমেই এ ট্রি এর উচ্চতা পেতে পারি। এর জন্য আমাদের দুইটা জিনিস মাথায় রাখতে হবে।
- সকল null বা খালি নোডের উচ্চতা -1।
- সকল লিফ নোডের উচ্চতা 0।
আপনাদের জানার জন্য বলে রাখছি যে Node হলো একটি স্ট্রাকচার (struct) যেখানে নিম্নরূপ ফিল্ড গুলো থাকবে ডেটা রাখার জন্য।
- int value: নোডের value রাখার জন্য।
- int height: সাব-ট্রির উচ্চতা রাখার জন্য।
- Node *left_node: বাম চাইল্ড এর পয়েন্টার রাখার জন্য ।
- Node *right_node: ডান চাইল্ড এর পয়েন্টার রাখার জন্য।
তাহলে শুরুতেই Node গঠনটি দেখে নেই। (C language)
| 1 2 3 4 5 6 | struct Node{ int value; // এখানে ভ্যালু রাখা হবে Node *left_node=NULL; // বামের নোড রাখা হবে এখানে Node *right_node=NULL; // ডানের নোড রাখা হবে এখানে int height=0; //আমাদের ট্রি এর উচ্চতা এখানে জমা রাখা হবে }; |
একটা সাধারণ struct। আশা করি দেখেই বুঝা যাচ্ছে কি করেছি।
এখন আমরা একটি ফাংশন তৈরি করবো। ফাংশনটি একটি নোডের পয়েন্টার নিবে এবং ঐ নোড খালি (null) না হলে সে নোডের উচ্চতা রিটার্ন করবে। নতুবা -1 রিটার্ন করবে। ফাংশনটির কোড নিম্নরূপ।
| 1 2 3 4 5 6 7 | int height(Node *node){ if(node==NULL){ return -1; }else{ return node->height; } } |
এখানে node==null হলে -1 রিটার্ন করা হচ্ছে এবং তা না হলে node->height রিটার্ন করা হচ্ছে। আশা করি কোডটি বুঝা যাচ্ছে।
বাইনারি সার্চ ট্রি insert() function এবং উচ্চতা বের করা
এখন আমরা ইনসার্ট ফাংশনটি লিখবো। insert এর কোড বাইনারি সার্চ ট্রি থেকে বেশি পার্থক্য নেই। কয়েকটা লাইন যুক্ত করে দিতে হবে উচ্চতা বের করার জন্য। তাই আপনারা আগে যারা বাইনারি সার্চ ট্রি এর লেখাটা পরেন নি তারা এখানে দেখে আসুন।
উপরের চিত্রের মতো বাইনারি সার্চট্রি গুলোতে insert() এর কোডটি লিখে ফেলবো। এই ফাংশনটি একটি integer value এবং একটি পয়েন্টার নিবে। integer value টি আমরা যা ইনসার্ট করবো তার মান এবং পয়েন্টার (Pointer) টি একটি Node পয়েন্টার নিবে, যেটা কোন না কোন সাব-ট্রি এর রুট (রিকার্সিভ ফাংশন)।
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | Node *insert(int num,Node *node){ if(node==NULL){ //if node==null হলে আমরা বুঝতে পারবো আমরা বাম, ডান করতে করতে সবার শেষে পৌঁছেছি। রুট নোডের ক্ষেত্রেও এই শর্ত সত্য Node *temp=new Node(); // নতুন একটা নোড তৈরি করি temp->value=num; temp->height=0; return temp; }else if(num<=node->value){ //আমরা বামে যাবো, কারণ আমাদের num এর মান বর্তমান নোডের থেকে কম node->left_node=insert(num,node->left_node); }else{ //আমরা ডানে যাবো, কারণ আমাদের num এর মান বর্তমান নোডের থেকে বেশি node->right_node=insert(num,node->right_node); } //বর্তমান নোড (node) এর ডান এবং বাম সাব-ট্রি এর মধ্যে যার উচ্চতা সব থেকে বেশি, আমাদের বর্তমান নোডের উচ্চতা হবে তার থেকে ১ বেশি। node->height=max(height(node->left_node),height(node->right_node))+1; return node; } |
লক্ষ করি, height() কিন্তু কোন রিকার্সিভ ফাংশন না। এই ফাংশনটি বানানো হয়েছে শুধু null নোড হান্ডেল করার জন্য।
বাইনারি সার্চ ট্রি এর নিয়ম অনুসারে আমরা জানি, ট্রি তে যা কিছুই নতুন ইনসার্ট (insert) করা হবে তা অবশ্যই লিফ নোডে যাবে। আমরা শুরুতেই বলেছি লিফ নোডের উচ্চতা শুন্য (0)। তাই আমরা ৫ নং লাইনে উচ্চতা শুন্য করে দিয়েছি যেহেতু এটা আমাদের রিকার্সিভ ফাংশনের বেস কেসে হচ্ছে আর এর মাধ্যমে একটি লিফ নোড তৈরি হচ্ছে। নিচের চিত্রে আমরা একটি নোডকে ইনসার্ট করেছি যার মান ৬ (গোলাপি নোড)। আমরা দেখতে পাচ্ছি নতুন নোডের উচ্চতা শুন্য। আমরা নিচের চিত্রে কোন ধরনের উচ্চতার আপডেট করি নি। শুধু বেস কেস পর্যন্ত গিয়েছি।
এবার আমাদের insert function বেস কেস (Base case) এর পরে আর কোন রিকার্সিভ কল করবে না।
আমরা উপর থেকে নিচে রিকার্শনের মাধ্যমে ফাংশন কল করতে করতে পৌঁছেছি এবং null নোডের জায়গায় গোলাপি নোডটি ইনসার্ট করেছি। কিন্তু এ পর্যন্ত ট্রিতে নোড সমূহের উচ্চতার কোন ধরনের আপডেট ঘটে নি। কারণ আমরা নিচ থেকে উপরে উঠার সময় (রিটার্ন করার আগে) উচ্চতার আপডেট করে নিবো।
এই কাজটি করা হয়েছে ২৫ নং লাইনে। ২৫ নং লাইনে আমরা আরেকটা অংশ যুক্ত করেছি যা আগের সাধারণ বাইনারি সার্চ ট্রিয়ের ইনসার্ট ফাংশনে ছিলো না।
| 25 | node->height=max(height(node->left_node),height(node->right_node))+1; |
এখানে আমরা রিকার্সিভ ভাবে একটি নোডের উচ্চতা আপডেট করেছি। একটি নোড x এর উচ্চতা আপডেট করার সূত্র হলো,
যেহেতু বাম এবং ডান নোডের মধ্যে তাদের নিজেদের সাব-ট্রি উচ্চতা আগের হিসাব করা হয়েছে (যেহেতু রিকার্সিভ ভাবে কল হয়েছে) তাই আমরা এই সূত্র প্রয়োগ করে খুব সহজেই তার এক লেভেল উপরের নোডের উচ্চতা পাবো।
আমরা গোলাপি নোড ইনসার্ট করার সময় যথাক্রমে ৩,২,১ মার্ক করা নোড গুলো বেয়ে এসেছি। সুতরাং রিকার্শনের নিয়ম অনুযায়ী বলতে পারছি উচ্চতার আপডেট যথাক্রমে ১,২,৩ পথেই হবে। এখানে max() এর ভিতরে -1 এসেছে কারণ পাশের null নোডের উচ্চতা -1 আগেই বলা হয়েছে এবং এই অনুসারেই height() ফাংশন রিটার্ন করে।
| 1 2 3 4 5 | int main(){ Node *root=NULL; root=insert(10,root); root=insert(5,root); } |
উপরের মেইন ফাংশনটুকুতে শুধু দেখানো হয়েছে কিভাবে মেইন থেকে insert() কে কল করতে হবে। আপনারা চাইলে BST এর লিখাটা থেকে সার্চ করার পদ্ধতি দেখে সার্চ করতে পারেন এবং সব ঠিক আছে কিনা পরীক্ষা করতে পারেন।
তো এইটুকুই আমাদের উচ্চতার কথা বার্তা। আমরা এখন ইচ্ছে করলেই ব্যাল্যান্স ফ্যাক্টর হিসাব করে নিতে পারবো সাধারণ বিয়োগ করার মাধ্যমে এবং ব্যাল্যান্স ফ্যাক্টর বের করার সূত্র ব্যবহার করে।
আরও পরুন: বাইনারি হিপ (Binary Heap) বা প্রায়োরিটি কিউ (Priority Queue)
