বিএসটি ব্যালান্সিং (BST Balancing)
বাইনারি সার্চ ট্রির (BST) সবচেয়ে বড় গ্যারান্টি হলো এর O(log n) স্পিড। কিন্তু এই স্পিডটা তখনই পাওয়া যায় যখন ট্রি-টা ঠিকমতো ব্যালান্সড (balanced) বা গোছানো থাকে। একটা আনব্যালান্সড (unbalanced) ট্রি একটা সাধারণ লিংকড লিস্টের (linked list) মতোই স্লো হতে পারে। কেন এই ব্যালান্স থাকাটা এত জরুরি, সেটা বুঝতে পারলেই আপনি এভিএল (AVL) ট্রি, রেড-ব্ল্যাক ট্রি সহ দুনিয়ার সব সেলফ-ব্যালান্সিং ডেটা স্ট্রাকচারের আসল মর্ম বুঝতে পারবেন।
'ব্যালান্সড' (Balanced) মানে কী?
একটা ট্রিকে তখনই ব্যালান্সড বলা হয়, যখন তার প্রতিটা নোডের বাঁ দিকের আর ডান দিকের ডালপালার উচ্চতার পার্থক্য খুব সামান্য (সাধারণত ১-এর বেশি নয়) থাকে। এর মূল লক্ষ্য হলো: পুরো ট্রির উচ্চতা যেন সবসময় log₂(n)-এর কাছাকাছি থাকে, যেখানে n হলো মোট ডেটার সংখ্যা।
ধরুন আপনার কাছে ১০ লাখ (1,000,000) ডেটার একটা পারফেক্ট ব্যালান্সড ট্রি আছে। এর উচ্চতা হবে মাত্র প্রায় ২০! তার মানে ১০ লাখ ডেটার মধ্যে থেকে যেকোনো কিছু খুঁজতে আপনাকে বড়জোর ২০ বার চেক করতে হবে।
← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন
সবচেয়ে খারাপ অবস্থা (Degenerate case): একটা ছদ্মবেশী লিংকড লিস্ট
ধরুন আপনি একটা খালি বিএসটিতে (BST) পরপর ১, ২, ৩, ৪, ৫ — এই সংখ্যাগুলো ঢোকালেন। যেহেতু প্রতিটা নতুন সংখ্যা আগেরটার চেয়ে বড়, তাই এরা সবসময় আগের নোডের ডান দিকে গিয়ে বসবে। শেষমেশ আপনার ট্রি-টা দেখতে এমন হবে:
এ ধরনের ট্রিকে বলা হয় ডিজেনারেট বিএসটি (degenerate BST)। এর উচ্চতা অপটিমাল ২ (log₂5 ≈ 2.3) হওয়ার কথা থাকলেও, হয়ে গেছে ৪ (n-1)। এখন যদি আপনি ৫-কে খুঁজতে যান, তবে আপনাকে একদম ওপর থেকে শুরু করে প্রতিটা নোড চেক করে করে নিচে নামতে হবে — অর্থাৎ স্পিড হয়ে যাবে একদম লিংকড লিস্টের মতো স্লো, বা O(n)।
ডেটা ঢোকানোর সিরিয়াল কেন এত ইম্পর্ট্যান্ট?
একটা বিএসটি (BST) দেখতে কেমন হবে, সেটা পুরোপুরি নির্ভর করে আপনি কোন সিরিয়ালে ডেটা ঢোকাচ্ছেন তার ওপর। একই ডেটা দিয়ে আপনি দারুণ ফাস্ট একটা ট্রিও বানাতে পারেন, আবার চরম স্লো একটা ট্রিও বানাতে পারেন:
- যদি ঢোকান [৪, ২, ৬, ১, ৩, ৫, ৭] → তাহলে পাবেন একদম পারফেক্ট ব্যালান্সড ট্রি, যার উচ্চতা ২।
- যদি ঢোকান [১, ২, ৩, ৪, ৫, ৬, ৭] → তাহলে পাবেন বাঁশের মতো একটা ডিজেনারেট চেইন, যার উচ্চতা ৬।
বাস্তব দুনিয়ায়, আপনি কোন সিরিয়ালে ডেটা পাবেন সেটা আপনার হাতে থাকে না (অনেক সময় আগে থেকেই সর্ট করা ডেটা আসে)। আর ঠিক এই কারণেই আমাদের সেলফ-ব্যালান্সিং (Self-balancing) বা নিজে নিজে গোছানো ট্রির দরকার পড়ে।
ব্যালান্স মাপা হয় কীভাবে?
যেকোনো নোডের ব্যালান্স ফ্যাক্টর (balance factor) বের করা হয় ঠিক এইভাবে:
একটা ব্যালান্সড ট্রিতে প্রতিটা নোডের ব্যালান্স ফ্যাক্টর অবশ্যই -১, ০, অথবা +১ হতে হবে। যদি কোনো নোডের ফ্যাক্টর +২ বা তার চেয়ে বেশি (প্লাস বা মাইনাস যাই হোক) হয়ে যায়, তার মানে ট্রি-টা আনব্যালান্সড হয়ে গেছে। তখন রোটেশন (rotation) বা ঘুরিয়ে পেঁচিয়ে তাকে আবার ঠিক করতে হয়।
সেলফ-ব্যালান্সিং ট্রির হিট দুটো সমাধান
দুনিয়ায় সবচেয়ে বেশি ব্যবহৃত সেলফ-ব্যালান্সিং বিএসটি (BST) হলো এই দুটো:
- এভিএল ট্রি (AVL Trees): এরা খুবই কড়া ধাচের। প্রতিবার ডেটা ঢোকানো বা মোছার সাথে সাথে এরা ব্যালান্স ফ্যাক্টরকে গুনে গুনে {-1, 0, 1}-এর ভেতরে রাখে। এতে খোঁজার স্পিড খুব ফাস্ট হয়, কিন্তু ডেটা লেখায় অনেকবার রোটেট করতে হয়।
- রেড-ব্ল্যাক ট্রি (Red-Black Trees): এরা ব্যালান্সের ব্যাপারে আরেকটু ছাড় দেয়। এতে ডেটা লেখায় বা ইনসার্ট করতে সময় কম লাগে। আপনি জাভা (Java) বা সি++ (C++)-এ যে ম্যাপ (Map) ব্যবহার করেন, সেগুলো ভেতরে ভেতরে এই রেড-ব্ল্যাক ট্রি দিয়েই বানানো।
Complexity
ছোট কুইজ
পড়া চালিয়ে যান